 Research
 Open Access
 Published:
Regularization property of linear interference cancellation detectors
EURASIP Journal on Advances in Signal Processing volume 2012, Article number: 145 (2012)
Abstract
In this article, we unveil a new property of linear interference cancellation detectors. Particularly, we focus in this study on the linear parallel interference cancellation (LPIC) detector and show that it exhibits a semiconvergence property. The roots of the semiconvergence behavior of the LPIC detector are clarified and the necessary conditions for its occurrence are determined. In addition, we show that the LPIC detector is in fact a regularization scheme and that the stage index and the weighting factor are the regularization parameters. Consequently, a stopping criterion based on the Morozov discrepancy rule is investigated and tested. Simulation results are presented to support our theoretical findings.
Introduction
Multi access interference (MAI) is the main limiting factor for the capacity of the third generation cellular system employing Code Division Multiple Access (CDMA) scheme [1]. Similarly, MAI is also limiting the capacity of optical networks using optical CDMA (OCDMA) technology. Other types of interference exist in other systems and may reduce capacity if not mitigated properly, i.e., the intercarrier interference (ICI) in orthogonal frequency division multiple access (OFDMA) and interantenna interference (IAI) in multi input multi output (MIMO) systems, just to name a few [1].
The effect of interference on wireless systems such as 4G and beyond is expected to be more severe due to the fact that the cells are expected to become more condensed (i.e.,femtocells) and the dimension of wireless technologies keeps increasing from one generation to another. For example, large MIMO systems with tens to hundreds of transmit/receive antennas are proposed for 4G and beyond in order to achieve high spectral efficiencies [2, 3]. To combat these different types of interferences, multiuser detectors (MUDs) have been developed [1]. MUDs are used mainly to reduce the effect of interference in wireless/wired systems and hence to increase system capacity and throughput. A large variety of MUDs was developed in the literature [1]. Typically, they range from simple but poor performance MUDs to complex but excellent performance MUDs. The challenge is usually to devise MUDs that tradeoff between low complexity and good performance. Applications of MUDs are diverse and in fact they have been applied to various wireless/wired systems such as MIMOOFDM, SFBCOFDM, OCDMA, just to name a few [4–6].
The decorrelating and the linear minimum mean square error (LMMSE) detectors are effective MUDs to eliminate MAI. They are also important for nonlinear multistage detectors (decorrelating decision feedback detector, LMMSE decision feedback detector, etc.) because the latter usually take their initial estimates from the decorrelator/LMMSE detector. Hence, reducing the computational complexity of the decorrelator/LMMSE detector reduces the total computational complexity of these nonlinear multistage detectors.
One constraint that limits the implementation of the decorrelator/LMMSE detector is its computational complexity which is in the order of O(N^{3}) [1], where N is the dimension of the system’s crosscorrelation matrix. For example, N in mobile WIMAX (IEEE 802.16Wireless MAN standard) [7] can reach up to 2048,and therefore to implement the decorrelator or the LMMSE detector, an inversion of a 2048by2048 system’s crosscorrelation matrix is needed which imposes real challenges for its practical implementation. To overcome this problem, linear interference cancellation (IC) structures such as the linear successive interference cancellation (LSIC) and the linear parallel interference cancellation (LPIC) detectors, are introduced to approximate the decorrelator/LMMSE detector but with much less computational complexity O(N^{2}) [8–10].
An important phenomenon that was noticed in the literature of linear IC detectors is their semiconvergence behavior, i.e., the best Bit Error Rate (BER) is obtained prior to convergence. This phenomenon was noticed first in [11–15], and recently in [16], and it seems to be a common feature in most linear IC’s if some conditions are met. However, no study has been yet carried out to explain the roots of this phenomenon and to devise necessary conditions for its occurrence. This study is needed to facilitate the development of appropriate stopping rules for terminating the linear IC detector’s iterations at the best BER performance before noise enhancement gets pronounced due to convergence to the decorrelator detector’s solution.
The contributions of this study are twofold: first we explain the rationale behind the semiconvergence behavior of the LPIC detector and derive necessary conditions for the occurrence of such a behavior. Specifically, we show that the LPIC detector exhibits a spectral filtering property where it attenuates solution components pertaining to small singular values of the system matrix and retains solution components pertaining to large singular values of the system matrix. Second, we exploit this property for the purpose of avoiding noise enhancement by early stopping the LPIC detector’s iterations. Towards that objective, we investigate a stopping rule based on the Morozov discrepancy principle [17]. The effectiveness of the proposed stopping rule is examined and extensively tested through simulations.
This article is organized as follows: in Section 2, the system model used in this study is briefly described. In Section 3, the naïve solution is analyzed and the common approaches used to overcome the effect of noise enhancement are detailed. Section 4 describes the structure of the LPIC detector, presents the proof for its spectral filtering property, analyzes its semiconvergence behavior and finally details the Morozov discrepancy rule for early stopping of its iterations. Finally, Section 5 supports the theoretical findings by a number of simulations and Section 6 concludes the article with some recommendations and possible future extensions of this study.
Notations
Throughout this article, the following notations are used.

∘ denotes the Schur product.

⊗ denotes the Kronecker product.

${\mathbf{1}}_{N}$ denotes a 1byN vector of ones.

diag. denotes the diagonal operator.

${.}^{T}$ denotes the transpose operator.

${.}^{H}$ denotes the hermitian operator.

${\Vert .\Vert}_{2}$ denotes the norm2 operator.

. denotes the absolute value.

${.}^{\u2020}$ denotes the pseudo inverse.

lim. denotes the limit operator.

tr. denotes the trace operator.

max. denotes the maximum operator.
System model
A generic communication system is expressed in vector–matrix form as
where r is the received signal vector and $\tilde{\tilde{\mathbf{\Psi}}}$ is the system matrix and b is the vector of transmitted data symbols, and finally n is the vector of independently and identicallydistributed additive white Gaussian noise (AWGN) samples with zeromean and variance ρ^{2}.
The system matrix $\tilde{\tilde{\mathbf{\Psi}}}$ differs from one communication system to another, i.e., in a CDMA system it represents the matrix of the spreading codes whereas in a MIMOOFDM system, the matrix $\tilde{\tilde{\mathbf{\Psi}}}$ is in fact a combination of two matrices: the matrix of channel coefficients and the matrix of orthogonal IFFT subcarriers.
For illustration purposes, we consider the LPIC detector in the context of mitigating the ICI due to the misalignment of the carrier frequencies and the Doppler shifts of different users in an OFDMA system. Specifically, we consider a scenario of an uplink OFDMA system where K users transmit simultaneously over a synchronous Rayleigh fading channel using Quadrature Phase Shift Keying. We consider in this study the effect of ICI due to the misalignment of the carrier frequencies and the Doppler shifts of different users and we neglect the effect of ICI due to intersymbol interference and interblock interference. This is justified by assuming a flat fading channel for each subcarrier of each user and assuming that the users transmit synchronously; therefore, it is reasonable to omit the cyclic prefix operation. This is illustrated in Figure 1.
Two main subcarrier allocation schemes are commonly used in the literature. In the first one, known as the block subcarrier allocation scheme, each user is assigned a block of adjacent subcarriers whereas in the second one, known as interleaved subcarrier allocation scheme, the total subcarriers are uniformly interleaved across all users. In this study, and since we are dealing with ICI, we consider the interleaved subcarrier allocation scheme because it is well known that this scheme suffers more from ICI compared to the block subcarrier allocation scheme [18].
An OFDM symbol consisting of N_{ u } samples with sampling time T_{ u } where N_{ u } is the total number of data samples is transmitted using N orthogonal subcarriers. Without loss of generality, we assume that the total number of subcarriers of the IFFT matrix Ψ with elements ${\mathbf{\Psi}}_{{n}_{u},n}=\frac{1}{\sqrt{{N}_{u}}}{e}^{\frac{j2\pi {n}_{u}n}{{N}_{u}}}$, 1 ≤ n_{ u } ≤ N_{ u } and 1 ≤ n ≤ N is divided equally among all users; therefore, the total number of subcarriers per user is N_{ k } = N/K.
The received signal is expressed in vector–matrix form as
where$\tilde{\mathbf{\Psi}}$ isa combination of the IFFT and normalized carrier frequency offset (NCFO) matrices as follows: $\tilde{\mathbf{\Psi}}=\mathbf{\Psi}\circ \left({\mathbf{1}}_{{N}_{k}}\otimes \mathbf{{\rm E}}\right)$ where Ε is the NCFO matrix. The NCFO matrix is obtained as $\mathbf{{\rm E}}=\left[\begin{array}{cccc}\hfill {\mathbf{\varepsilon}}_{1}\hfill & \hfill {\mathbf{\varepsilon}}_{2}\hfill & \hfill \cdots \hfill & \hfill \begin{array}{cc}\hfill {\mathbf{\varepsilon}}_{k}\hfill & \hfill \begin{array}{cc}\hfill \cdots \hfill & \hfill {\mathbf{\varepsilon}}_{K}\hfill \end{array}\hfill \end{array}\hfill \end{array}\right]$where ${\mathbf{\varepsilon}}_{k}$ is given by ${\mathbf{\varepsilon}}_{k}={\left[\begin{array}{cccc}\hfill {e}^{\frac{j2\pi {\varepsilon}_{k}}{{N}_{u}}}\hfill & \hfill {e}^{\frac{j2\pi 2{\varepsilon}_{k}}{{N}_{u}}}\hfill & \hfill \cdots \hfill & \hfill \begin{array}{ccc}\hfill {e}^{\frac{j2\pi {n}_{u}{\varepsilon}_{k}}{{N}_{u}}}\hfill & \hfill \cdots \hfill & \hfill {e}^{\frac{j2\pi {N}_{u}{\varepsilon}_{k}}{{N}_{u}}}\hfill \end{array}\hfill \end{array}\right]}^{T}$ and ɛ_{ k } is the NCFO of user k obtained as ${\varepsilon}_{k}=\Delta {f}_{k}/\mathit{\Delta f}$ where $\mathit{\Delta f}$is the subcarrier spacing. H(m) is the matrix of Rayleigh fading coefficients at the m thOFDM symbol where 1 < m < M, and it is given by$\mathbf{H}\left(m\right)=\mathit{d}\mathit{i}\mathit{a}\mathit{g}\left(\begin{array}{cccc}\hfill {\mathbf{H}}_{1}\left(m\right)\hfill & \hfill {\mathbf{H}}_{2}\left(m\right)\hfill & \hfill \cdots \hfill & \hfill \begin{array}{ccc}\hfill {\mathbf{H}}_{{n}_{k}}\left(m\right)\hfill & \hfill \cdots \hfill & \hfill {\mathbf{H}}_{{N}_{k}}\left(m\right)\hfill \end{array}\hfill \end{array}\right)$ where ${\mathbf{H}}_{{n}_{k}}\left(m\right)=\mathit{d}\mathit{i}\mathit{a}\mathit{g}\left(\begin{array}{cccc}\hfill {h}_{1,{n}_{k}}\left(m\right)\hfill & \hfill {h}_{2,{n}_{k}}\left(m\right)\hfill & \hfill \cdots \hfill & \hfill \begin{array}{ccc}\hfill {h}_{k,{n}_{k}}\left(m\right)\hfill & \hfill \cdots \hfill & \hfill {h}_{K,{n}_{k}}\left(m\right)\hfill \end{array}\hfill \end{array}\right)$. Channel fading coefficients are obtained in practice through channel estimation. Without loss of generality, we assume throughout this article perfect knowledge of the channel state information. A is the power weighting matrix and it is used to scale the signals of different users with different powers to simulate near–far scenarios. It can be even used to weight the subcarriers of the same user differently if needed. This matrix is given by $\mathbf{A}=\mathit{d}\mathit{i}\mathit{a}\mathit{g}\left(\begin{array}{cccc}\hfill {\mathbf{A}}_{1}\hfill & \hfill {\mathbf{A}}_{2}\hfill & \hfill \cdots \hfill & \hfill \begin{array}{ccc}\hfill {\mathbf{A}}_{{n}_{k}}\hfill & \hfill \cdots \hfill & \hfill {\mathbf{A}}_{{N}_{k}}\hfill \end{array}\hfill \end{array}\right)$where${\mathbf{A}}_{{n}_{k}}=\mathit{d}\mathit{i}\mathit{a}\mathit{g}\left(\begin{array}{cccc}\hfill {a}_{1,{n}_{k}}\hfill & \hfill {a}_{2,{n}_{k}}\hfill & \hfill \cdots \hfill & \hfill \begin{array}{ccc}\hfill {a}_{k,{n}_{k}}\hfill & \hfill \cdots \hfill & \hfill {a}_{K,{n}_{k}}\hfill \end{array}\hfill \end{array}\right)$.b(m) is the vector of transmitted symbols and it is formed as $\mathbf{b}\left(m\right)={\left[\begin{array}{cccc}\hfill {\mathbf{b}}_{1}\left(m\right)\hfill & \hfill {\mathbf{b}}_{2}\left(m\right)\hfill & \hfill \cdots \hfill & \hfill \begin{array}{ccc}\hfill {\mathbf{b}}_{{n}_{k}}\left(m\right)\hfill & \hfill \cdots \hfill & \hfill {\mathbf{b}}_{{N}_{k}}\left(m\right)\hfill \end{array}\hfill \end{array}\right]}^{T}$ where ${\mathbf{b}}_{k}\left(m\right)=\left[\begin{array}{cccc}\hfill {b}_{1,{n}_{k}}\left(m\right)\hfill & \hfill {b}_{2,{n}_{k}}\left(m\right)\hfill & \hfill \cdots \hfill & \hfill \begin{array}{ccc}\hfill {b}_{k,{n}_{k}}\left(m\right)\hfill & \hfill \cdots \hfill & \hfill {b}_{K,{n}_{k}}\left(m\right)\hfill \end{array}\hfill \end{array}\right]$. n(m) is an Nlength vector of independently and identically distributed additive white Gaussian distributed samples with zeromean and variance ρ^{2},and finally $\tilde{\tilde{\mathbf{\Psi}}}\left(m\right)=\tilde{\mathbf{\Psi}}H\left(m\right)\mathbf{A}$ is a combination of the IFFT, the NCFO, the channel gain and power weighting matrices, respectively. This matrix can be decomposed as $\tilde{\tilde{\mathbf{\Psi}}}\left(m\right)=\left[\begin{array}{cccc}\hfill {\tilde{\tilde{\mathbf{\Psi}}}}_{1}\left(m\right)\hfill & \hfill {\tilde{\tilde{\mathbf{\Psi}}}}_{2}\left(m\right)\hfill & \hfill \cdots \hfill & \hfill \begin{array}{ccc}\hfill {\tilde{\tilde{\mathbf{\Psi}}}}_{n}\left(m\right)\hfill & \hfill \cdots \hfill & \hfill {\tilde{\tilde{\mathbf{\Psi}}}}_{N}\left(m\right)\hfill \end{array}\hfill \end{array}\right]$ where ${\tilde{\tilde{\mathbf{\Psi}}}}_{n}\left(m\right)$ is the n th column of the matrix $\tilde{\tilde{\mathbf{\Psi}}}\left(m\right)$. For simplicity and conciseness we drop the OFDM symbol index m in all subsequent equations.
The naïve solution and the noise enhancement effect
The naïve solution or the decorrelator detector (sometimes known also as the zero forcing detector) is one of the basic detectors that completely eliminates the interference and it can be formulated as a least square minimization problem:
The solution to this optimization problem is the decorrelator detector’s solution and it is given by
The naïve solution for illconditioned systems tends to amplify noise. To get more insight let us examine the singular value decomposition (SVD) of the decorrelator detector’s solution. Using the SVD, the system matrix $\tilde{\tilde{\mathbf{\Psi}}}$ can be factorized as
where U and V are both the NbyN unitary matrices, respectively, and Σ is an NbyN diagonal matrix with elements ${\sigma}_{n}$, 1 ≤ n ≤ N. The N columns of U represent the left singular vectors of $\tilde{\tilde{\mathbf{\Psi}}}$ and the N columns of V represent the right singular vectors of $\tilde{\tilde{\mathbf{\Psi}}}$ and the N diagonal entries of Σ represent the singular values of $\tilde{\tilde{\mathbf{\Psi}}}$. We assume without loss of generality that the singular values are ordered from the largest to the smallest with indices ranging from 1 to N. Consequently, the decorrelator detector’s solution can be written in terms of the SVD of $\tilde{\tilde{\mathbf{\Psi}}}$ as
and its norm is given by
As it can be seen from the equation above, the norm of y^{DEC} will not be too large as long as $\left{\mathbf{u}}_{n}^{H}\mathbf{r}\right<{\sigma}_{n}$ for large n. This is known as the discrete Picard condition [19].
Discrete picard condition
A meaningful solution is obtained if the Fourier coefficients ${\mathbf{u}}_{n}^{H}\mathbf{r}$ decay to zero on average faster than the singular values ${\sigma}_{n}$.
It can be seen that if the discrete Picard condition is not satisfied, the decorrelator’s solution goes unbounded. This is specifically true for illconditioned system matrices that tend to have many small singular values near zero. Moreover, since the noise tends to reside in the space spanned by singular vectors corresponding to singular values that are equal or less than the noise level, then noise components corresponding to singular values not satisfying the discrete Picard condition are magnified and consequently result in the noise enhancement effect observed in the decorrelator detector’s solution.
A typical scenario where an OFDMA system matrix gets illconditioned is the case of large frequency offsets. To illustrate this, the singular values of a system matrix with 128 subcarriers and 64 users are plotted in Figure 2. It can be seen that due to large values of the NCFO, many singular values are close to zero and therefore, for these singular values, there is a large chance that the discrete Picard condition will not be satisfied. This is illustrated in Figure 2 where the singular values, Fourier coefficients, and their ratio are plotted.
By virtue of Figure 2, it is evident that the norm of the decorrelator’s solution gets amplified if the singular values are below a certain threshold [19] (<0.7 in our case). All singular values below this threshold do not satisfy the discrete Picard condition and therefore contribute to the noise enhancement effect.
To combat this phenomenon, several regularization techniques have been developed. The main idea behind regularization is to filter out solution components pertaining to small singular values, that is
where F is an NbyN diagonal matrix with elements ${f}_{n}$, known as filtering factors and should satisfy
Hence, these factors tend to discard small singular values of the system matrix $\tilde{\tilde{\mathbf{\Psi}}}$ and retain large ones.
Many regularization techniques exist in the literature such as the truncated SVD, Tikhonov, etc.; however, due to space limitation we refer the readers to [20] for more information on these techniques. In the next section, we show after a brief description of the LPIC detector that it can be used as a regularization scheme with two regularization parameters.
The LPICdetector
The LPIC detector is an effective scheme for the approximation of the decorrelator/LMMSE detector and it consists of IC units arranged in a multistage structure as shown in Figure 3. The internal structure of each IC unit is illustrated in Figure 4. The vector of decision variables of the p^{th} stage, n^{th} branch y_{p,n} is first multiplied with ${\tilde{\tilde{\mathbf{\Psi}}}}_{n}$,added to the vectors of decision variables of the other branches, and then subtracted from the received signal r to obtain a cleaned version of the received signal $\left(\mathbf{r}{\sum}_{j=1}^{N}{\tilde{\tilde{\mathbf{\Psi}}}}_{j}{y}_{p,j}\right)$where all users exhibit less mutual interference. The vector of decision variables of the (p + 1)^{th} stage, n^{th} branch y_{p+ 1,n} is obtained by matched filtering the cleaned signal with ${\tilde{\tilde{\mathbf{\Psi}}}}_{n}$, multiplying the result by a weighting factor ω and finally adding the result to the vector of decision variables of the previous stage, that is
The weighting factor ω is used to ensure convergence of the LPIC detector. This process is repeated in a multistage structure as shown in Figure 3.
If all N branches of the LPIC detector are considered, then Equation (10) becomes
where ${\mathbf{e}}_{p}={\tilde{\tilde{\mathbf{\Psi}}}}^{H}\left(\mathbf{r}\tilde{\tilde{\mathbf{\Psi}}}{\mathbf{y}}_{p}\right)$ is the residual error. Therefore, the vector of decision variables and residual error signal can be written in closed form as [21]
and
respectively, where ${\mathbf{e}}_{0}={\tilde{\tilde{\mathbf{\Psi}}}}^{H}\mathbf{r}$and ${\mathbf{G}}_{p}=\left[{\mathbf{g}}_{p,1}\phantom{\rule{0.5em}{0ex}}{\mathbf{g}}_{p,2}\cdots \cdots {\mathbf{g}}_{p,n}\cdots {\mathbf{g}}_{p,N}\right]$. This allows obtaining the average BER at the p^{th} stage as [21]
where Q(.) denotes the Q function. Moreover, the LPIC detector converges if
which translates to the following condition
where λ_{ n } is the n^{th} eigenvalue of the system crosscorrelation matrix ${\tilde{\tilde{\mathbf{\Psi}}}}^{H}\tilde{\tilde{\mathbf{\Psi}}}$.
Furthermore, it is easy to show that as the number of stages tends to infinity the LPIC detector converges to the decorrelator detector’s solution, that is
Therefore, if the LPIC detector converges, it converges to the decorrelator detector’s solution that suffers from noise enhancement.
Spectral filtering property of the LPIC detector
In the following, we show that the LPIC detector exhibits a spectral filtering property in the sense that it filters some components of the solution while it retains others. This important property can be exploited to develop a new regularization scheme. To get more insight, we use the SVD of the system matrix $\tilde{\tilde{\mathbf{\Psi}}}$ to analyze the convergence behavior of the LPIC detector. After some algebraic manipulations, Equation (12) can be written as (see the Appendix for the proof):
where F(p + 1,ω) is a KbyK diagonal matrix with elements f_{ n }(p + 1,ω), known as filtering factors and are given by
These factors tend to attenuate small singular values of the matrix $\tilde{\tilde{\mathbf{\Psi}}}$ and retain large ones. Moreover, it is clear from Equation (19) that the amount of filtering introduced by the filtering matrix F(p + 1,ω) can be controlled through the stage index p and the weighting factor ω; thus, the stage index and the weighting factor act as regularization parameters for the LPIC detector. Figure 5 depicts the filtering factor f_{ n }(p + 1,ω) as a function of the singular value σ_{ n } for different values of ω and p.
It is clear that as the number of stages p gets larger, more small singular values are included in the reconstruction of the solution y_{p+1}. However, if small singular values that are below the noise level are involved and the discrete Picard condition is not satisfied, the noise enhancement effect starts dominating the solution. Therefore, the performance of the LPIC detector is expected to improve at early stages but after a certain number of stages the noise starts dominating the solution and deteriorating the performance of the LPIC detector. This explains the phenomenon pointed out in [11–16], which we call here the semiconvergence property of the LPIC detector.
Similar to the stage index p, the weighting factor ω also acts as a regularization factor where the performance of the LPIC detector is expected to improve for small values of ω, but after a certain threshold the noise enhancement effect starts taking place and the performance of the LPIC detector worsens. However, in addition to its regularization effect, the weighting factor ω controls the convergence speed of the LPIC detector, and therefore, the optimal value for this parameter has to balance between high convergence speed and low noise enhancement.
Nevertheless, in practice, the role of the weighting factor is confined to maximize the convergence speed and not to control the amount of noise enhancement introduced into the solution. Consequently, we also restrict the role of the weighting factor to maximize the convergence speed of the LPIC detector and use only the stage index p as a regularization parameter.
Semiconvergence property of the LPIC detector
As mentioned earlier, the LPIC detector exhibits a semiconvergence property where it reaches an average BER that is better than that achieved at final convergence. To get more insight, let us consider the error between y_{p+1} and the vector of the transmitted data symbols b, that is
It can be seen that the error between y_{p+1} (which is an estimate of the vector of the transmitted symbols b) and the vector of the transmitted symbols b consists of two components: the data error and the noise error. The data error is caused by using a modified inverse of the system crosscorrelation matrix ${\tilde{\tilde{\mathbf{\Psi}}}}^{H}\tilde{\tilde{\mathbf{\Psi}}}$ instead of the true inverse, whereas the noise error is caused by the magnified/filtered noise. Depending on the filtering matrix F(p + 1,ω), two cases can be distinguished:

If F(p + 1,ω) ⋍ I, the data error is small but the noise error is large due to the noise enhancement effect. The solution y_{p+1} is undersmoothed.

If F(p + 1,ω) ⋍ 0, the noise error is small but the data error is large, and as a result the solution is heavily damped. The solution y_{p+1} is oversmoothed.
So, a proper choice of the filtering matrix F(p + 1,ω)should balance between the data and noise errors. And since the amount of filtering introduced by the filtering matrix is proportional to the stage index p and the weighting factor ω, a proper stopping rule needs to be devised. The semiconvergence behavior of the LPIC detector with respect to the stage index p is illustrated in Figure 6 where the norm of the relative error defined by$\frac{{\Vert \mathbf{b}{\mathbf{y}}_{p+1}\Vert}_{2}}{{\Vert \mathbf{b}\Vert}_{2}}$ is plotted against the stage index p for several values of ω. Since $0<\omega <\frac{2}{max{\lambda}_{n}\left({\tilde{\tilde{\mathbf{\Psi}}}}^{H}\tilde{\tilde{\mathbf{\Psi}}}\right)}$, and $max{\lambda}_{n}\left({\tilde{\tilde{\mathbf{\Psi}}}}^{H}\tilde{\tilde{\mathbf{\Psi}}}\right)\le tr\left({\tilde{\tilde{\mathbf{\Psi}}}}^{H}\tilde{\tilde{\mathbf{\Psi}}}\right)$, we vary ω as$\omega =\beta \frac{2}{tr\left({\tilde{\tilde{\mathbf{\Psi}}}}^{H}\tilde{\tilde{\mathbf{\Psi}}}\right)}$for β = 2, 5, 7, 10, 14.
Similarly, the semiconvergence behavior of the LPIC detector with respect to the weighting factor ω is illustrated in Figure 7 where the norm of the relative error is plotted against the weighting factor ω for several values of p, that is p = 10, 20, 50, 100, and 500.
It is clear from Figure 6 that with increasing values of the weighting factor ω, the convergence speed increases as well and the norm of the relative error exhibits a bowlshaped curve with a sharp curvature towards the minimum. However, with decreasing values of the weighting factor, the convergence speed decreases and more importantly the bowlshaped curve exhibits a flat minimum. Similar conclusion can be derived for Figure 7 for the stage index p.
As it will be shown in the simulation results, the average BER of the LPIC detector exhibits the same semiconvergence behavior as for the norm of the relative error in Figures 6 and 7.
Stopping rule for the LPIC detector
In this section, we investigate the possible use of the Morozov discrepancy rule [17, 22] to develop a proper criterion for stopping the iterations of the LPIC detector before the noise enhancement effect starts dominating the solution.
Morozov discrepancy rule for the LPIC detector
The accuracy of the regularized solution y _{ p } cannot exceed that of the received data vector r .
Therefore, if we have an LPIC detector in which the only regularization parameter is the stage index p (the weighting factor is set to one), the best regularized solution y_{ p } is obtained by iterating till the residual error is equal to the noise level, that is
However, due to the fact that the regularization parameter (stage index p) is an integer, the discrepancy principle defined by Equation (21) may not be satisfied exactly; therefore, we reformulate the definition to
This condition is illustrated in Figure 8 where at each stage the norm of the residual error ‖e_{ p }‖_{2} of the LPIC detector is evaluated and compared to the noise level ρ. If the residual error becomes less than the noise level then the LPIC detector’s iterations should be stopped. The difference between the norm of the residual error and the noise level is termed the discrepancy error δ and it quantifies the amount of discrepancy resulting from using the modified Morozov discrepancy rule of Equation (22) instead of the exact one described by Equation (21).
But since we do not have only one regularization parameter (i.e., the stage index p) but we have two instead, that is, p and ω, direct application of Equation (22) is not possible. Therefore, the Morozov discrepancy rule of Equation (22) is modified using the following theorem.
Theorem:
The optimal stage index for the linear PIC detector with regularization parameters p and ω using the Morozov discrepancy rule can be approximated as
Proof:
Two regularization schemes are equivalent if they have the same filter factors. Therefore, an LPIC scheme with only one regularization parameter p is equivalent to another LPIC scheme with two regularization parameters p′ and ω if their filter factors are equal, that is${f}_{n}\left(p\prime ,\omega \right)={f}_{n}\left(p\right)\text{,}\phantom{\rule{1em}{0ex}}1\phantom{\rule{0.25em}{0ex}}\le n\le N\phantom{\rule{0.25em}{0ex}}$. As shown in[20, 23], the following approximation can be made
Thus, $p\prime \omega {\sigma}_{n}^{2}=p{\sigma}_{n}^{2}$ and consequently $p=p\prime \omega $ . Hence, Equation ( 23 ) is obtained.
Lemma
Proof:
Since${\sigma}_{n}^{2}$is upper bounded by$max\left({\sigma}_{n}^{2}\right)$and$tr\left({\tilde{\tilde{\mathbf{\Psi}}}}^{H}\tilde{\tilde{\mathbf{\Psi}}}\right)$, that is${\sigma}_{n}^{2}\le max\left({\sigma}_{n}^{2}\right)\le tr\left({\tilde{\tilde{\mathbf{\Psi}}}}^{H}\tilde{\tilde{\mathbf{\Psi}}}\right)$, hence Equation ( 24 ) is obtained.
Moreover, the discrepancy error δ due to not satisfying the Morozov discrepancy rule is given by
As shown in Figure 8, the discrepancy error δ is a function of two parameters: the initial residual error e_{ 0 } and the weighting factor ω. Obviously, in order to minimize the discrepancy error δ, one should better estimate the noise level ρ using the residual error e_{ p }, that is, making ${\Vert {\mathbf{e}}_{{p}_{\mathit{o}\mathit{p}\mathit{t}}}\Vert}_{2}$ as close as possible to ρ. This can be realized by reducing the difference between the successive residual errors ${\Vert {\mathbf{e}}_{p}\Vert}_{2}{\Vert {\mathbf{e}}_{p+1}\Vert}_{2}$ through employing smaller values of the weighting factor ω[15]. But, unfortunately this will lead to slower convergence of the LPIC detector. Therefore, the weighting factor should be adjusted to realize two conflicting goals: fast convergence and low discrepancy error. A possible solution is to use a stagedependent weighting factor that exhibits large values in the initial stages where the main goal is improving the convergence speed and small values at later stages where the main goal is reducing the discrepancy error. This subject is outside the scope of this study and it is a research topic by itself and therefore will be treated independently in future study.
Simulation results
This section presents results illustrating the semiconvergence behavior of the linear PIC detector and showing the performance of the LPIC detector equipped with the Morozov discrepancy principle. Figures 9 and 10 depict the average BER of the LPIC detector plotted against the stage index p and the weighting factor ω at SNR = 10 and 20 dB, respectively, with N = 32, K = 4 and the frequency offsets of the four users set to (ɛ_{1} = –0.35, ɛ_{2} = 0.38, ɛ_{3} = 0.36, ɛ_{4} = –0.39). The following remarks can be stated.

It can be seen that the average BER for both cases (a) and (b) with increasing values of both/either p and/or ω starts initially large, decreases until it reaches the LMMSE detector’s performance and then increases again resulting in an Lshaped valley that illustrates clearly the semiconvergence behavior of the LPIC detector.

For varying p, the smaller the value of ω, the more the average BER curve becomes flat around its minimum, and hence the less the sensitivity of the solution to the accuracy of the stopping criterion employed. Note that this reduction in sensitivity is achieved at the expense of slow convergence speed. However, larger values of the weighting factor are needed for faster convergence, but unfortunately this requires a highly reliable stopping criterion to determine the stage index minimizing the average BER. Therefore, the challenge is to develop efficient stopping rules that can be used with high values of the weighting factor so that we can gain both high convergence speed and low average BER.
In the following, we evaluate the performance of the LPIC detector equipped with the Morozov discrepancy principle, that we call here MorozovLPIC detector for brevity. First, we evaluate its convergence behavior by varying the stage index p and assessing its average BER performance for different values of $\omega =\beta \frac{2}{tr\left({\tilde{\tilde{\mathbf{\Psi}}}}^{H}\tilde{\tilde{\mathbf{\Psi}}}\right)}$.We set β to 2, 4, 5, 7, 10, SNR = 20 dB, N = 32 and K = 4 with frequency offsets of the four user set to (ɛ_{1} = –0.35, ɛ_{2} = 0.38, ɛ_{3} = 0.36, ɛ_{4} = –0.39). Figure 11 shows the results for the four detectors: MorozovLPIC, LMMSE, Matched Filter (MF), and Decorrelator (DEC).
As expected, it is clear that the average BER of the MorozovLPIC detector gets better and closer to that of the LMMSE detector for smaller values of the weighting factor ω at the expense of slower convergence. Larger values of the weighting factor ω result in faster convergence but unfortunately, with a larger discrepancy error and bad average BER as well.
In Figure 12, the average stopping stage index for each MorozovLPIC stage is obtained simply by summing up the stopping stage indices determined by the Morozov discrepancy rule for M OFDM symbols and then dividing by M. The average stopping stage index is plotted versus the number of MorozovLPIC stages. Obviously, as the weighting factor gets smaller (i.e., β = 2) the residual error decreases slower as well and therefore needs more stages to satisfy the Morozov discrepancy rule and hence the average stopping stage index increases with decreasing values of ω as depicted in Figure 12.
Figure 13 illustrates the average BER performance versus the SNR of the MorozovLPIC and the other three detectors for different values of the weighting factor ω. The maximum number of stages P is fixed to 1000, we set β to 2, 4, 5, 7, 10, N to 32 and K to 4 with frequency offsets as follows (ɛ_{1} = –0.35, ɛ_{2} = 0.38, ɛ_{3} = 0.36, ɛ_{4} = –0.39).
As expected, the MorozovLPIC detector exhibits the best average BER performance for small values of the weighting factor (β = 2). This is clear at high SNRs where the radius of the circle determined by the noise level in Figure 8 gets smaller with increasing SNRs. Hence, for large values of the weighting factor the discrepancy error becomes large as well and consequently the average BER of the MorozovLPIC detector becomes large too.
In Figure 14, the average stopping stage index for each SNR is obtained simply by summing up the stopping stage indices determined by the Morozov discrepancy rule for M OFDM symbols and then dividing by M. The averaged stopping stage index is plotted versus the SNR.
Obviously, the average stopping stage index increases with the SNR because high SNRs translates into smaller noiselevel circles as illustrated in Figure 8; therefore, the MorozovLPIC detector needs more stages to satisfy the Morozov discrepancy rule.
Figure 15 depicts the condition number of the system crosscorrelation matrix ${\tilde{\tilde{\mathbf{\Psi}}}}^{H}\tilde{\tilde{\mathbf{\Psi}}}$ for both AWGN channel and Rayleigh fading channels. The different simulation parameters for the AWGN case are set to: N = 32 and K = 4 with frequency offsets set to (ɛ_{1} = –0.35,_{2} = 0.38, ɛ_{3} = 0.36, ɛ_{4} = –0.39). For the Rayleigh fading channel case, in addition to the aforementioned simulation parameters, we set the carrier frequency to 3.5 GHz and the speed of different users to, 80, 120, 90, and 100 km/h, respectively. The main difference between the two cases is that the system matrix in a Rayleigh fading channel is time variant and severely illconditioned due to the nature of the timevarying fading channel. This imposes some challenges to the performance of the MorozovLPIC detector where due to the time varying nature of the condition number a fixed weighting factor that might be optimal for one ODFM symbol might result in bad performance for another symbol. In order to overcome this problem, a reasonably small value of the weighting factor should be selected to achieve good performance at the expense of slow convergence rate.
The average BER performance versus the SNR for a Rayleigh fading channel of the MorozovLPIC detector for different values of the weighting factor ω is plotted in Figure 16. The figure also shows the performance of the DEC, LMMSE, and MF. The maximum number of stages P is fixed to 1000. The remaining parameters are set as follows: β to 2, 4, 6, 12, N to 32, and K to 4 with frequency offsets of the four users are set to (ɛ_{1} = –0.35,_{2} = 0.38, ɛ_{3} = 0.36, ɛ_{4} = –0.39). The carrier frequency is set to 3.5 GHz and the speed of different users is set to, 80, 120, 90, and 100 km/h, respectively. Similar to the AWGN channel, using relatively small values of the weighting factor enhances the performance of the MorozovLPIC detector, however, this results in a very slow convergence rate. For this case, the best performance is achieved for β = 2, and it is expected that for smaller values of β the performance of the MorozovLPIC detector would improve further.
In Figure 17, the average stopping stage index is plotted versus the SNR. Similar to Figure 14, the average stopping stage index increases with the SNR and the rate of increase becomes larger for decreasing values of β.
Conclusion
In this study,we unveiled a new property of linear IC detectors. Specifically, we proved that the LPIC detector exhibits a semiconvergence behavior if the discrete Picard condition is not satisfied. Moreover, we showed that this phenomenon can be circumvented if the iterations are stopped before final convergence using a suitable stopping rule. Consequently, we investigated the possible use of the Morozov discrepancy principle to derive a proper stopping condition for the LPIC iterations. Performance analyzes of the LPIC detector using the Morozov discrepancy principle showed that the value of the weighting factor should tradeoff between two conflicting goals: convergence speed and small discrepancy error. Simulation results coincide well with our theoretical findings. Future study includes extending these results to other linear IC detectors such as the SIC, hybrid SIC/PIC, etc., use of stagedependent weighting factors to compromise between convergence speed and small discrepancy error and finally exploring other stopping rules.
Appendix
Recall that the vector of decision variables is given by
By expanding the summation in (26) we obtain
Multiplying both terms by $\left(\mathbf{I}\omega {\tilde{\tilde{\mathbf{\Psi}}}}^{H}\tilde{\tilde{\mathbf{\Psi}}}\right)$ and adding the identity matrix I, we obtain:
Therefore, the summation in (27) can be expressed as
Hence,
Using the SVD of H defined in (4), Equation (30) can be expressed as
which finally can be written as
where ${\mathbf{F}}_{p+1}=\mathbf{I}{\left(\mathbf{I}\omega {\mathbf{\Sigma}}^{H}\mathbf{\Sigma}\right)}^{p+1}$.
This concludes the proof.
References
 1.
Honig ML: Advances in Multiuser Detection Wiley Series in Telecommunications and Signal Processing. 2009. ISBN: 9780470473801
 2.
Vardhan VK, Mohammed SK, Chockalingam A, Rajan BS: A lowcomplexity detector for large MIMO systems and multicarrier CDMA systems. IEEE J. Sel. Areas Commun. 2008, 26(3):473485.
 3.
Mohammed SK, Zaki A, Chockalingam A, Rajan BS: Highrate spacetime coded largeMIMO systems: lowcomplexity detection and channel estimation. IEEE J. Sel. Topics Signal Process. 2009, 3(6):958974.
 4.
Hou SW, Ko CC: Intercarrier interference suppression for OFDMA uplink in time and frequencyselective fading channels. IEEE Trans. Veh. Technol. 2009, 58(6):27412754.
 5.
Sreedhar D, Chockalingam A: Interference mitigation in cooperative SFBCOFDM. EURASIP J. Adv. Signal Process 2008., 11: Article ID 125735, 11
 6.
Mrabet H, Dayoub I, Attia R, Haxha S: Performance improving of OCDMA system using 2D optical codes with optical SIC receiver. J. Lightw. Technol. 2009, 27(21):47444753.
 7.
IEEE Standard for Local and Metropolitan area networks Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems Amendment 2: Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed Bands. The Institute of Electrical and Electronics Engineering, Inc 2005. Std. IEEE 802.16E2005
 8.
Buehrer RM, CorrealMendoza NS, Woerner BD: A simulation comparison of multiuser receivers for cellular CDMA. IEEE Trans. Veh. Technol. 2000, 49(4):10651085. 10.1109/25.875213
 9.
Molisch AF, Toeltsch M, Vermani S: Iterative methods for cancellation of intercarrier interference in OFDM systems. IEEE Trans. Veh. Technol. 2007, 56(4):21582167.
 10.
Ancora A, Montalbano G, Slock DTM: Preconditioned iterative intercarrier interference cancellation for OFDM reception in rapidly varying channels. in Proc. ICASSP 2010, 30663069.
 11.
Juntti MJ, Aazhang B, Lilleberg JO: Iterative implementation of linear multiuser detection for dynamic asynchronous CDMA systems. IEEE Trans. Commun. 1998, 46: 503508. 10.1109/26.664306
 12.
Johansson AL, Rasmussen LK: in Proceedings of the IEEE Int. Symp. Spread Spectrum Techniques and Appl, Sun City, South Africa 1998, 1: 121126.
 13.
Sun S, Rasmussen LK, Lim TJ, Sugimoto H: A matrixalgebraic approach to linear hybrid interference canceller in CDMA. Proceedings of the IEEE Int. Conf. Univ. Personal Commun. Florence, Italy 1998, 2: 13191323.
 14.
Rasmussen LK, Lim TJ, Johansson AL: A matrixalgebraic approach to successive interference cancellation in CDMA. IEEE Trans. Commun. 2000, 48(1):145151. 10.1109/26.818882
 15.
Rasmussen LK, Oppermann IJ: Pingpong effects in linear parallel interference cancellation for CDMA. IEEE Trans. Wirel. Commun. 2003, 2: 357363. 10.1109/TWC.2003.809122
 16.
Bentrcia A, Zerguine A: A new approach to the analysis of the linear groupwise parallel interference cancellation detector. inPIMRC 2008, Canne, France; 2008:15.
 17.
Samarskii AA, Vabishchevich PN: Numerical Methods for Solving Inverse Problems of Mathematical Physics. Walter de Gruyter, Berlin; 2007. ISBN 9783110196665
 18.
Hashemizadeh SK, SaeediSourck H, Omidi MJ: Sensitivity analysis of interleaved OFDMA system uplink to carrier frequency offset. in IEEE 22nd International Symposium on Personal Indoor and Mobile Radio Communications 2011, 16311635.
 19.
ThambanNair M: Linear Operator Equations. Approximation and Regularization World Scientific Publishing Company, Singapore; 2009. ISBN 9812835644
 20.
Hansen PC: RankDeficient and Discrete IllPosed Problems. Numerical Aspects of Linear Inversion(Society for Industrial and Applied Mathematics, Philadelphia, PA; 1998. ISBN: 0898714036
 21.
Bentrcia A, Zerguine A: A new linear groupwise parallel interference cancellation detector. Wirel. Personal Commun. 2009, 49(1):2334. 10.1007/s1127700895537
 22.
Bertero M, Boccacci P: Introduction to Inverse Problems in Imaging. IOP Publishing Ltd, Bristol; 1998.
 23.
Hamarik U, Palm R: On rules for stopping the conjugate gradient type methods in illposed problems. Math. Model. Anal. 2007, 12(1):6170. 10.3846/13926292.2007.12.6170
Acknowledgment
The authors acknowledge the support of KSU. The study was supported by the KACST under project number ARP 2955.
Author information
Affiliations
Corresponding author
Additional information
Competing interests
The authors declare that they have no competing interests.
Authors’ original submitted files for images
Below are the links to the authors’ original submitted files for images.
Rights and permissions
Open Access This 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.
About this article
Cite this article
Bentrcia, A., Alshebeili, S.A. Regularization property of linear interference cancellation detectors. EURASIP J. Adv. Signal Process. 2012, 145 (2012). https://doi.org/10.1186/168761802012145
Received:
Accepted:
Published:
Keywords
 Linear
 PIC
 Regularization
 Semiconvergence
 LMMSE
 Interference cancellation