Lossless Size Reduction for Integer Least Squares with Application to Sphere Decoding

Minimum achievable complexity (MAC) for a maximum likelihood (ML) performance-achieving detection algorithm is derived. Using the derived MAC, we prove that the conventional sphere decoding (SD) algorithms suffer from an inherent weakness at low SNRs. To find a solution for the low SNR deficiency, we analyze the effect of zero-forcing (ZF) and minimum mean square error (MMSE) detected symbols on the MAC and demonstrate that although they both improve the SD algorithm in terms of the computational complexity, the MMSE point has a vital difference at low SNRs. By exploiting the information provided by the MMSE method, we prove the existence of a lossless size reduction which can be interpreted as the feasibility of a detection method which is capable of detecting the ML symbol without visiting any nodes at low and high SNRs. We also propose a lossless size reduction-aided detection method which achieves the promised complexity bounds marginally and reduces the overall computational complexity significantly, while obtaining the ML performance. The theoretical analysis is corroborated with numerical simulations.


I. INTRODUCTION
W HEN the transmitted symbols are from a finite set, the problem of optimal detection is an integer least-squares (ILS) problem. It arises in many applications such as code division multiple access (CDMA) systems [1], Vertical Bell Labs Layered Space-Time (V-BLAST) structure [2], linear dispersion space-time block coding (LD-STBC) [3] and generalized spatial modulation (GSM) schemes [4] to name just a few most frequent and established applications. The maximum likelihood (ML) detector results in an optimum solution of the ILS problem. However, the ML detection problem can be solved by a brute-force search which is computationally infeasible [5]. Thus, sphere-decoding (SD) was proposed as an efficient tree-search based method to obtain the ML solution [6]. Unlike the brute force search, the SD algorithm searches over the lattice points that lie within a hyper sphere of radius R around the received signal. The SD algorithm was first introduced by Fincke and Pohst (FP) in [7]. Later, a more efficient variation of the SD algorithm known as Schnor-Euchner (SE) refinement was presented in [8]. Based on FP and SE algorithms, two improvements of these variations of the SD algorithm were proposed in [9], and shown to offer a M. Neinavaie  computational complexity reduction compared to the SE and FP variations.
The computational complexity of the SD algorithm was studied in [10]- [12]. In [10] and [11], the expected number of operations required by the algorithm was derived over the Rayleigh fading channel, realization of the noise and transmitted symbols. It was shown that the expected complexity has a polynomial behavior at a wide range of signal-to-noise ratios (SNRs). Contrasted with this claim, the main result of [12] is that the expected complexity of the SD is exponential for a fixed SNR, and the complexity exponent behavior shows that the SD algorithm is not efficient for the systems which operate under low-SNR conditions or have a large size. In [13], the complexity distribution for random infinite lattices for the SD algorithm was also analyzed. With a focus on the spacetime codes (STC) and diversity-multiplexing tradeoff (DMT) optimality, the minimum complexity for the SD algorithm, which achieves a vanishing gap to the ML performance at high SNRs, was derived in [14]. This minimum complexity is described via introducing the SD complexity exponent. Aiming for reducing the computational complexity, there are a number of other variants of the SD algorithm which can be divided according to the error performance into optimal and suboptimal SD algorithms [15]- [23].
At the opposite extreme, linear detection (LD) schemes including the zero-forcing (ZF) and minimum mean square error (MMSE), perform linear operations which incur a much lower complexity compared to the SD algorithm [5]. This polynomial complexity comes at the cost of a dramatic performance loss [24]. As an example of auxiliary/initial, low cost information, the LD method sometimes results in a reduced search space for the SD algorithm [25]- [28]. Most of these schemes achieve either a sub-optimal performance to reduce the computational complexity, e.g., [27], or have exponential computational complexity to achieve the ML performance, e.g., [29]. In [30], an ML performance-achieving method which is as complex as the ZF method with probability one, at high SNRs was proposed. In other words, at a high SNR regime, this method meets both complexity and performance extremes with probability one. However, this method does not achieve the optimal performance at a low SNR regime and only operates in a V-BLAST system with the Rayleigh fading channel.
A fundamental question for SD algorithms is the minimum possible search space to achieve the optimal ML performance when auxiliary low cost information, such as the detected symbol by the LD method or an initial radius, is available. In this paper, we address this question by presenting the minimum achievable complexity (MAC) of an SD algorithm. Moreover, the exponential behavior of the SD algorithm at low SNRs and large number of input symbols is, arguably, the most significant drawbacks of SD algorithm [12]. In this paper, theoretical study and possible solutions to overcome these drawbacks are given.

A. Main Contributions
1) Using the law of large numbers, we obtain the minimum feasible complexity, i.e., MAC of the SD algorithm for a given set of initial information. This set may solely contain the classic initial information of the conventional SD algorithms, e.g., the initial radius and the channel matrix, or it may involve more information, such as the initial point detected by an LD method, hereafter denoted by s LD . This complexity bound can be used as a bench mark to determine how well a particular SD algorithm exploits the initial information. The proposed complexity bound, MAC, is distinct from the complexity exponent in [14] in some important respects. Unlike the complexity exponent, which only considers the high SNR optimal performance achieving SD, the MAC is the minimum complexity bound for the SD algorithms which achieve the exact ML performance at all SNRs. Moreover, our bound describes the complexity behavior in a more general sense. Indeed, it is not limited to a specific setting or a type of fading channel.
2) The proposed MAC reveals an inherent limitation of some conventional SD algorithms at a low SNR regime. More precisely, we prove that the results obtained in [12] about the weakness of the SD algorithm at small SNRs are natural and the auxiliary information of these SD algorithms is not effective at low SNRs.
3) Although, the size reduction notion, in the sense that SD algorithms can search over a reduced search space with a performance loss, already exists in the literature, e.g., [27], it is in this paper that the concept of a lossless size reduction in SD algorithms is introduced as the capability of reducing the effective size without any performance loss. Along with introducing the concept of a lossless size reduction, the derived MAC allows us to prove that by adding appropriate low cost auxiliary information, a solution for the low SNR deficiency problem of conventional SD algorithms is attainable. Specifically, we show that, unlike the ZF detected symbol, adding the MMSE detected symbol to the information set helps to overcome the weakness of conventional SD algorithms at low SNRs.
4) In addition to capabilities and bounds, an ML performance-achieving SD algorithm which follows the lossless size reduction concept is proposed. We prove that this algorithm intelligently deploys the initial information to reduce the effective problem size without any performance loss. It is also capable of operating under any type of fading channels. By defining marginal optimality as achieving the optimal error performance without any tree-search at low and high SNRs, we prove that the proposed algorithm is marginally optimal. The distinct characteristics of the proposed algorithm which, to the best of our knowledge, are not met in any other SD algorithms are as follows: providing a lossless size reduction, i.e., reducing the effective size while being optimal in the sense of error performance; an exemption from the tree-search at a range of SNRs, especially low SNRs.
The remainder of the paper is organized as follows. After reviewing the basic SD algorithm and its computational complexity in Section II, we derive the MAC of SD algorithms in Section III. We present the lossless size reduction concept in Section IV and propose the marginally optimal SD algorithm in Section V. Section VI explores the validity of theoretical results via simulations. Finally, Section VII concludes the paper.

B. Notations
Throughout the paper boldface small letters denote vectors and boldface capital letters denote matrices. A superscript (·) T denotes the transpose of a matrix, |x| stands for the absolute value of x and x stands for the Euclidean norm, [X] mn denotes the element in the mth row and the nth column of matrix X and [x] i is the ith element of vector x. The probability of event A is denoted as P(A). Mathematical expectation of X over variable Y is denoted by E Y {X}, while f (X) is the probability density function (pdf) of the random variable X and f (X|Y ) is the conditional pdf of the random variable X given Y . We also use the notation= to denote the asymptotic exponential equality, i.e., f (ρ)=g(ρ) means that lim log ρ . Finally, C denotes the field of complex numbers and |S| is the cardinality of set S.

Consider the system model
where H is the L × K channel matrix, the K × 1 vector s ∈ C K consists of the information symbols drawn from an arbitrary M -ary quadrature amplitude modulation (QAM) or pulse amplitude modulation (PAM) constellation, y denotes the L × 1 received vector, and n is the independent and identically distributed (i.i.d.) additive complex Gaussian noise with variance σ 2 , and the SNR is defined as ρ 1 σ 2 . The channel H is general enough to capture a number of applications such as, uncoded V-BLAST and STC MIMO systems, precoded orthogonal frequency-division multiplexing (OFDM) systems [31], and multiuser systems [32].
The ML solution for the information symbol decoding is which is the closest lattice point search problem. Unlike the brute-force ML detector, the SD algorithm reduces the computational complexity by searching over the lattice points inside a sphere with radius R. The essence of any SD-based method is the FP algorithm and its refinements, such as the SE enumeration [6]. The computational complexity of the SD algorithm is a function of the number of visited nodes in the tree-search [10]. In this paper, as in [12] and [13], we consider the number of visited nodes itself as the complexity measure. The number of visited nodes in the SD algorithm is equal to the sum of visited lattice points at the kth layer, k = 1, . . . , K. If we denote the number of lattices, in a k dimensional hypersphere with radius R, by N k , the number of visited nodes of the SD algorithm is [13] where N k = s k ∈ C k ỹ k − R k s k 2 ≤ R . Indeed, N k depends on the information set, denoted by I, which is fed to the algorithm. This initial information is mostly embedded in the preprocessing stage and the initial choice of R. The preprocessing stage is comprised of the QR decomposition of the channel matrix H, and for some variants of the SD algorithm, also an LD detected symbol, e.g., the ZF or MMSE points, and sometimes an ordering stage. The ordering can be a natural back-substitution or a more sophisticated one which is topically based on the channel matrix realization H. For example, see the ordering algorithms in [9]. For the initial radius R, the two most well-known choices are latticeindependent and lattice-dependent radii [13]. The FP variant of the SD method primarily adopts a lattice-independent radius, and the SE refinement is a lattice-dependent based SD algorithm. A powerful choice for a lattice-independent radius is proposed in [10,Section 4]. The information set for the SD algorithm presented in [10] is the channel matrix and an initial radius, i.e., I li = {H, R H }. The initial radius presented in [10], denoted by R H , guarantees the existence of at least one lattice point inside the sphere with a high probability. In the lattice-dependent variants of the SD algorithm, such as the SE refinement, the provided information set is I ld = {H, R B }, where R B is the initial lattice-dependent radius obtained by R B = y − Hs B 2 , and s B is the Babai point or the zero forcing-decision feedback (ZF-DF) estimate [8].
It is worth mentioning that the ZF-DF point can be modified to the other points, such as the MMSE detected symbol. Intuitively, the more information the additional point gives us about the ML detected symbol, the more effective the initial information set becomes. Therefore, if we add a point which is very likely to be the ML detected symbol, the set I plays a more important role in reducing the computational complexity. Nevertheless, this additional auxiliary point should not impose a high computational complexity to the SD algorithm itself. This is the reason that traditional SD algorithms commonly deploy LD methods which incur an acceptably low, often polynomial, complexity.

III. MAC IN AN SD ALGORITHM
As it was mentioned previously, the initial information, I, can potentially reduce the computational complexity of the SD algorithm. In other words, the initial information may make it unnecessary to search over all the lattice points inside the sphere. As an extreme example, assume that I = {s B } and we know that s B is the ML detected symbol with probability one. Therefore, we lose nothing, with probability one, if we only visit the nodes corresponding to s B . Thus, in general, according to this information, some of the lattice points become probable or typical. The typical set, or equivalently, the set of minimum possible lattice points, can be determined using the asymptotic equipartition property (AEP) and the law of large numbers [33]. If the typical set of lattice points is provided, the SD algorithm only needs to perform the search over this set. The typical set concept allows us to obtain the minimum necessary and possible number of lattice points. Then, an algorithm which searches over the typical set is able to find the ML solution with the minimum possible number of visited nodes. Hereafter, this minimum possible number of visited nodes is referred to as the MAC of an SD algorithm which can be interpreted as a complexity bound for an SD algorithm. Achieving this bound for the number of visited nodes is realizable by constructing the typical set and searching over it, and can be considered as a benchmark for how efficient a variant of an SD algorithm is, in terms of computational complexity. By a marginal analysis of this bound, we investigate the inherent drawback of the conventional variants of the SD algorithm which appear primarily at the low SNR regime. The basic difference between this type of analysis and the lower bounds obtained in the literature, for instance [12], should be noticed carefully.
In the SD complexity analysis presented in [12], the lower bounds are derived for a specific SD method and show the limitations of those methods, exclusively, with a certain radius, body search strategy, and preprocessing method. Nonetheless, the MAC, obtained by the law of large numbers, reveals the smallest possible search space for any given variant of the SD algorithm and, therefore, the inherent limitations of the SD algorithm with a given set of information is clarified. Indeed, the MAC is the ultimate potential of an SD algorithm.
To obtain this lower bound, we consider a sequence of N ML search candidates as where s k ML [n] is the k dimensional ML search candidate at the nth time slot. To obtain the possible sequences S k ML or the typical sets, the probability P(s k ML |I) needs to be calculated. By looking at large sequences of these symbols and using the law of large numbers, these probabilities reflect on which possible sequences of the ML search candidates s k ML 's are more likely to happen. As in Shannon's AEP, the set of these probable sequences for a large number of observations N is referred to as the typical set [33]. According to the law of large numbers, if the typical set has to be available, we can find the ML solution by searching over the typical set. We also know that the sequences of the typical set are equiprobable, which means that if we search over a smaller set than the typical set, we will miss s ML with a considerable probability. Therefore, in order to find the ML point, the typical set has to be the minimum sufficient and necessary search space. In the following lemma, we present the MAC, denoted by C min SD , for a given information set I.
Lemma 1: The MAC of a given SD algorithm with the initial information set I is Proof: See Appendix A.
In (5), −E s k ML log P s k ML |I is the entropy of s k ML given the set I. Designing a method which solely searches over the typical set, and hence achieves the MAC, is attainable, yet seems to be a challenging problem. Nonetheless, the MAC can be considered as a computational complexity bench mark. It should be noted that the MAC is only a function of the initial information set, i.e., I. As it was mentioned previously, according to the AEP and for a given initial information set, no matter which radius, body search strategy or preprocessing is adopted, if the number of visited nodes is smaller than C min SD , the ML performance is not achieved.
The following theorem reveals a fundamental low SNR limitation of the conventional SD methods with latticeindependent and lattice-dependent radii. It should be noted that in the proofs concerning the lattice-independent radii, we have considered an FP method with the lattice-independent radius in [10] which is also adopted as the radius of the SD algorithm in many other FP algorithms, e.g., [13]. Also, for the lattice-dependent based SD algorithm, we have considered an SD method which applies the lattice-dependent radius R B = y − Hs LD 2 . Moreover, regimes with ρ → 0 and ρ → ∞ are sometimes referred to as the low and high SNR regimes, respectively.

Theorem 1:
The MAC of a lattice-independent and latticedependent conventional SD algorithm satisfies the following inequality C min SD ≥ 2 2 K − 1 , at low SNRs and the equality C min SD = K at high SNRs. Proof: In order to calculate C min SD of a lattice-dependent based SD method, at a low SNR regime, we have to find P s k ML |I ld , where I ld = {H, R B } and R B = y − Hs B 2 . Note that at zero SNR, we have y = n and, consequently, where Γ s k ML is the ML decision region, that is Voronoi region, for the symbol s k ML . Using the independence of H and n, we have In [34], it is shown that f (n | n = ν ) = 1 SK δ ( n − ν) where δ(·) is the Dirac delta function and S K = 2π .
For an M -ary modulation scheme, the integral (7) should be calculated over M k Voronoi regions corresponding to each s k ML . In the following, we show that the integral (7) over the Voronoi regions corresponding to s k ML and its rotated versions k ML = Ts k ML both lead to the same result, where the orthogonal matrix T is the rotation matrix.
We have We can change the variable as n = T Hn to get The above equality holds since n = n . Therefore, According to the symmetrical properties of the constellation, each s k ML in each hyperoctant 1 is a rotated version of an s k ML in the first hyperoctant. Thus, according to (10), it is sufficient to solely calculate the integral (7) over the Veronoi regions in the first hyperoctant. For the binary modulation case, we denote the Voronoi region corresponding to the point Therefore, in order to calculate (7), we can change the variable as dn = r k−1 drdΩ to obtain Since, S K is the volume of a K-dimensional hypersphere and for a k dimensional lattice with binary entries, the 2 k possible Voronoi regions have equal volumes, we obtain Consequently, we have lim Therefore, the MAC of a lattice-dependent radius based SD algorithm is lower bounded by Now, we focus on a lattice-independent radius based SD method. The SD presented in [10] considers the FP algorithm, with a proposed radius that tends to infinity as ρ → 0. Therefore, the radius does not contain any information about s ML at low SNRs, or equivalently, I li = {H} and When ρ → 0, we have y = n and using the independence of n and H we have Therefore, since the volume of the Voronoi regions corresponding to inner lattices tends to zero at low SNRs, according to (17), we obtain where the inner and outer sets, correspondingly, are the inner and outer modulation points in the constellation set. Consequently, Consider now the high SNR regime. In a lattice-dependent radius based SD method, the initial radius is R B = y − Hs 2 , and when the SNR tends to infinity, s B = s ML = s, that means that only one point, merely s ML , exists in the sphere, with a probability one. In other words, for the given information set, i.e., I ld = {R B , H}, no uncertainty remains on s ML when the SNR tends to infinity. Therefore, we have −E s k ML log P s k ML |R B = 0 and lim ρ→∞ C min SD = K. On the other hand, the proposed lattice independent radius in [10] is R li = αK ρ , where α is determined such that we find a lattice point inside the sphere with probability 1 − ǫ [10], i.e., where F χ 2 K (·) is the cumulative distribution function (CDF) of a chi-squared random variable and Γ(·) is the gamma function. For instance, if α = √ ρ, at high SNRs, ǫ tends to zero and at the same time R li approaches zero. Therefore, with probability one, only one lattice is inside the sphere at high SNRs which is s ML . Hence, having the information set I which is d li at high SNRs does not leave any uncertainty on s ML and, therefore, −E s k ML log P s k ML |d li = 0. Theorem 1 claims that for the lattice-dependent and independent based variants of the SD algorithm, such as the FP algorithm in [10] and the SE refinement in [9], we have C min SD = K when the SNR tends to infinity. The complexity analysis of the SD in [10] at high SNRs, for the FP algorithm shows that the number of visited nodes of the FP algorithm with the proposed radius tends to K at high SNRs. This means that these methods are effective in the sense that they achieve the minimum possible complexity at high SNRs with the information set I = {H, R li } fed to the SD algorithm.
The main weakness of these methods shows, indeed, at the low SNRs. The weakness of the classic FP and SE algorithms is because of the information fed to these methods which leads to an exponential complexity with respect to the problem size. Analyses of the complexity of the FP based SD algorithm in [12] also shows that this method suffers from a high computational complexity at low SNRs. This theory shows that even if the best body search strategy, preprocessing or ordering techniques are applied to the SD algorithm, for the given lattice-independent and dependent radii, an exponential computational complexity occurs at low SNRs.
Remark 1: Clearly, for an SD algorithm which searches over the lattice points inside a sphere of radius R, the best, yet infeasible, radius which contains merely one lattice point is The proof of Theorem 1 conveys that, even with R ML , the idea of searching inside a sphere leads to an exponential computational complexity at low SNRs. In other words, the initial radius R is ineffective at low SNRs.
A fundamental question arises here: is it possible to unravel this exponential behavior at low SNRs without any performance loss? It is known that, unlike the ZF, the MMSE method declares the ML solution at low SNRs, i.e., s MMSE = s ML , when ρ → 0 [5]. Therefore, there is a prospect of the existence of a method which finds the ML solution at low SNRs without visiting any nodes but just by, intelligently, relying on s MMSE . Theorem 1 claims that, regardless of the fact that s MMSE = s ML at low SNRs, deploying the MMSE detected symbol only as the initial radius will not be successful as far as the computational complexity is concerned. In other words, a lattice-dependent based SD algorithm is not able to benefit from the information provided by the MMSE algorithm perfectly. Indeed, the initial point obtained by the MMSE method, i.e., s MMSE , has more information to be exploited.
Presumably, adding the MMSE detected symbol to the information set I, not only in R B but as a separate initial point, may able to compensate for this exponential behavior of C min SD at low SNRs. Along with the evidence we have for the existence of a lossless method which relies on the s MMSE and, consequently, detects the s ML without visiting any nodes, there is also an expectation of existence of an algorithm which is capable of relying on some or all of the detected symbols of the MMSE method at all SNRs which reduces the overall effective problem size without any performance loss. A method which is capable of relying on some or all of the symbols of the initial point without any performance loss is referred to as a lossless size reduction (LSR) aided method. The concept of an LSR-aided SD is addressed in the next section.

IV. MAC IN A LSR-AIDED SD
The information set of the lattice-independent and dependent algorithms can be enriched by adding a separate initial point to set I. In addition, having this point in the initial information set can be interpreted as a separate processing block in the preprocessing stage which enables obtaining the ML solution without visiting any nodes. The combination of a decoder that comprises this block and an SD algorithm is referred to as an LSR-aided SD algorithm. By partially, or completely, relying on the initial point, e.g., s MMSE , this separate block makes a decision for some, or all, of the transmitted symbols. These symbols are already declared to be detected and do not play any role in the SD search; thus, the problem size is changed. Taking into account the LSR in an SD algorithm, the problem size of the SD algorithm, K, becomes a random variable. This random problem size depends on the number of symbols of the initial point on which the LSR-aided algorithm relies.
Assuming that the effective problem size after applying the LSR reduces to K r , the MAC for a given K r and I LSR is obtained by where I LSR = {H, s B }. Therefore, the MAC for an LSRaided SD is The event when K r = k can be interpreted as relying on K − k of the initial point. For example P(K r = 0) = 1, at a given SNR, implies that we have trusted the initial point entirely, with probability one at that SNR, and consequently, C min SD = 0. Along with considering the optimal error performance, the following definition takes into account the complexity to provide a more general view of the concept of optimality in the class of ML performance achieving algorithms.
Definition 1: An initial information set is said to obey the zero-complexity achievable (ZCA) property at a given SNR, if at that SNR C min LSR = 0, and an SD algorithm which exploits the ZCA property at zero and infinity SNRs, is considered to have the marginal complexity optimality, i.e., achieves the ML performance without visiting any nodes at ρ → 0 and ρ → ∞.
Based on Definition 1, the following lemma analyzes the capability of an information set containing the MMSE or ZF points in terms of ZCA.
Lemma 2: The initial information set corresponding to an MMSE-based LSR algorithm, i.e., I LSR = {s MMSE , H}, is ZCA at ρ = 0 and ρ → ∞ and the information set of a ZFbased LSR, i.e., I LSR = {s MMSE , H}, is only guaranteed to be ZCA at ρ → ∞.
Proof: See Appendix B.
Analyzing the MAC, we have been looking for a low computational complexity point to be added to the information set to compensate for the low SNR weakness. This lemma shows that if we add s MMSE to the information set, i.e., I = {s MMSE , H}, the inherent deficiency of the conventional SD algorithms at low SNRs is resolved. These results are summarized in Table I, and it can be seen that the conventional SD algorithms with lattice-dependent or independent radii, are not able to achieve the ML performance without visiting any nodes at zero and infinity SNRs. On the other hand, an algorithm which is fed with I = {s MMSE , H}, i.e., MMSE based LSR-aided SD, is capable of achieving the ML performance without visiting any nodes at zero and infinity V. A LOSSLESS SIZE REDUCTION-AIDED SD So far, we have described the capabilities of an LSR-aided SD in terms of MAC. More precisely, we have evaluated the effect of adding the initial point s LD to the information set I in Lemma 2. In the detection process, adding this information, can be translated to adopting a separate preprocessing step to determine the status of the symbols of the initial lattice point beforehand. This notion has been considered in some existing works, as an approach to reduce the computational complexity, e.g., [26], [27], and [30]. However, this point of view usually arrives at a sub-optimum, near ML, error performance. By focusing on the LSR property, our aim is to derive a detector which partially or entirely relies on the initial lattice point without a performance loss. From the LSR perspective, achieving the ML performance with a reduced problem size and, even sometimes without visiting any nodes, is feasible. In this section, we propose an LSR-aided SD algorithm.
In the detection problem (2), the equalized vectorỹ can be written asỹ = W p y, where W p is the preprocessing equalization matrix. The joint detection problem can be decoupled into a single detection problem which often has a lower performance compared to the ML detector. The LSRaided SD either relies on the detected symbols of the initial point or preserves the symbol in a set, hereafter denoted by S, to be searched by the SD algorithm.
The kth element ofỹ, is where k = 1, . . . , K. Assuming that E{|[s] k | 2 } = 1, the kth received SNR depends on the underlying LD method. The proposed algorithm uses the instantaneous SNR to assess the reliability of each symbol. For instance, when the ZF equalizer is adopted, then SNR k = ρ [(HH) −1 ] kk , and for the MMSE equalizer, we have In order to perform a lossless size reduction, we need to find the reliable symbols of the initial point. The indices of the reliable detected symbols form a set denoted by G. Indeed, the proposed detection method relies on the detected symbols whose indices are in G, and the rest of the symbols construct the setḠ. In Theorem 2, we determine G such that the proposed method guaranties the ML performance. The set G is constructed as where η k is obtained from the following equation where E k LD and E k ML are the kth symbol error events of the LD and ML detection methods, respectively.
It should be noted that finding η k from (26) is an offline process. Indeed, using (26), a lookup table can be provided to find η k at each SNR. More details about finding η k will be discussed later. The reduced search space is where [s LD ] i = arg min s∈C |[ỹ] i − s| denotes the ith symbol of the initial point s LD .
The following theorem provides the sufficient reduced search space which relies on some or all of the initial point symbols and leads to achieving the exact ML performance.
Theorem 2: An algorithm which relies on the initial point symbols whose indices are in G, and searches over the remaining symbols in the set S , where |S| = M K−|G| , achieves the optimal ML performance.
Proof: In order for the algorithm to achieve the ML performance, η k should be selected such that P ( The kth symbol error probability of the proposed method can be expanded as where D k is defined in (27), s andŝ are the transmitted symbol and the detected symbol by the proposed algorithm, respectively. The first term of the right hand side of (28) can also be expanded as According to the proposed detection method, in the first term on the right hand side of (29), the event Now, we focus on the second term on the right hand side of (29). It should be noted that the event {|D k | = M } means that all the modulation points exist in the set D k and, therefore, the event Note that the proposed algorithm performs the ML search over the set S. The error event in the detection of the kth symbol occurs when all the search candidates, in S, sharing the same kth symbol with the transmitted vector, do not meet the ML minimum distance detection criteria. We denote the set of all vectors sharing the same kth symbol with s by Λ [s] k , that is, It should be noted that we have S ⊆ C K , therefore Next, we focus on the second term on the right hand side of (28). We can write According to the proposed method, joint event Since, the event {|D k | = M } is equivalent to the event SNR k ≤ η k , it follows from (28), (32), (33), and (35) that Therefore, in order to achieve the ML performance it is sufficient to have Since, the kth symbol error probability of the ML detector can be expanded as which are the symbol error events corresponding to the LD and the ML methods, respectively, the sufficient condition for the proposed method to achieve the ML performance is obtained by (26).
We have shown that a threshold which is obtained by (26), guarantees the ML performance. However, in order to prove that the algorithm has the lossless size reduction property, we have to show thatŝ = s ML . It should be noted that the ML decision has the uniqueness property [35]. In other words, an algorithm which achieves the same performance as the ML detector, has also the same decision with probability one, i.e. P(ŝ = s ML ) = 1.
Theorem 2 proposes a fading-type and application independent algorithm. In other words, the derived threshold is general in the sense that it is applicable to different fading types, e.g., Rayleigh, Nakagami, etc, and applications, e.g., coded and uncoded MIMO, OFDM systems, etc. The detection algorithm is summarized in Algorithm 1. It should be noted that regardless of which SD algorithm we use, the lossless size reduction step reduces the overall computational complexity.
As it was mentioned previously finding η k from (26) can be accomplished via a lookup table which is provided off line by Monte Carlo simulations. One way to build the lookup table at a given SNR is to compute the probabilities P E k LD , SNR k > η k and P E k ML , SNR k > η k for different values of η k , and their intersection gives the proposed η k . In the following section we provide a more convenient way to construct the offline lookup table.

A. Constructing the lookup table
In order for a lossless size reduction aided algorithm to achieve the ML performance at a given SNR, it is sufficient to choose an η k , or equivalently η k ρ , which is an answer/root of (26). The smallest root of (26) is, hereafter, denoted by η ⋆ k . It should be noted that at a given ρ, (26) may have multiple roots and an efficient algorithm should choose the smallest η ⋆ k to obtain a lower computational complexity. A trivial answer for (26) is η k ρ = ∞ and, in general, it is not guaranteed that a finite η k ρ exists for all values of ρ. Also, η ⋆ k ρ = ∞, at a given SNR, implies that the initial information is not capable of pruning the search tree at that SNR.
In general, obtaining a closed form solution for (26) may be complicated and depends on the fading type and the adopted LD method. In this section, we provide a general suboptimal answer which is less or equal than the smallest root of (26). Since, η k ρ = ∞ is always a valid answer, it is guaranteed that scaling the suboptimal η k always arrives at a solution for (26). Intuitively, if choose η k ρ larger than η ⋆ k ρ , it means that we have considered more restrictive conditions for relying on an LD detected symbol and, consequently, scaling a suboptimal η k ρ leads to a better performance and a higher computational complexity. By neglecting P ([s ML ] k = [s] k , SNR k < η k ) in (37), we can arrive at the integral (39) In general neglection of this term violates ML achieving property. In other words, the root of (39) is less or equal than η ⋆ k ρ . Yet, since we are seeking a subotimal solutionl, we are not obligated to keep this term. However, later in this section, we show that this term is negligible at high SNR regime and this approximation leads to the ML performance when ρ → ∞. This implies that the root of (39) at ρ → ∞, is We can rewrite the integral in (39) as is the error probability of a detected symbol by the LD method given x k and it is bounded as Using (41) in (39), results in an η k which is smaller than or equal to η ⋆ k . Therefore, it is a suboptimal solution. According to (39), (40) and (41) we can write Denoting the root of the above inequality as η sub k , we have η sub where

B. Marginal Complexity Optimality of an MMSE-based LSRaided SD
As it was mentioned in Section IV, the initial information set of an MMSE based LSR-aided SD, has the ZCA property, i.e., the potential of achieving the ML performance without visiting any nodes at zero and infinity SNRs. Now, we examine the computational complexity of the proposed algorithm to see if the algorithm is marginally optimal, i.e., if it is capable of exploiting the ZCA property. As it was mentioned previously, if a method obeys the marginal complexity optimality, it does not need to tolerate any complexity more than the LD computational complexity at zero and infinity SNRs, and while achieving the ML performance, it does not need to visit any nodes. The following theorem addresses this property for the proposed algorithm.
Theorem 3: The proposed MMSE based LSR-aided SD algorithm is marginally optimal.
Proof: Assume that the effective problem size is K r . If for the proposed method at a given SNR, we can show that P(K r = 0) = 1, then the number of visited nodes becomes zero with probability one at that SNR. In order to prove that the proposed method is marginally optimal, we need to show that P(K r = 0) = 1 at ρ → 0 and ρ → ∞. We have where the last inequality follows from the union bound. Hence, since SNR k = ρx k , the sufficient condition for marginal optimality is Therefore, in order to prove the marginal optimality, it is sufficient to show that for the given η k obtained from (26), we have lim ρ→0,∞ η k ρ = 0. It follows from Appendix B that the events E k ML and E k LD are equivalent when ρ → 0. Therefore, when ρ → 0, (26) holds for all values of η k ρ , including η k ρ = 0. Now, we consider the case when ρ → ∞. It should be noted that (37), similar to (26), results in an ML performance achieving η k . At high SNR regime, for the ML method, we have P ([ where d ML is the diversity gain of the ML method. We show that if η k satisfies where ǫ is an arbitrary small number, then (37) holds. The reason is that if (46) is satisfied, the first term of (37) becomes negligible at high SNR since The conditional symbol error probability of M -ary QAM is [33] where α = 3 M−1 and β = 2 1 − 1 √ M . For linear equalizers, the problem turns into some single symbol detection problem, and for a conditional SNR and channel realization, (49) holds as far as square QAM is adopted. Invoking the fact that Q(·) is a decreasing function of its argument, the upper bound Q( √ y) ≤ 1 2 exp(− y 2 ), holds. Moreover, since Consequently, using (46) and (50) we obtain lim ρ→∞ η k = 2 α ln βρ dML+ǫ , and, therefore, lim ρ→∞ η k ρ = 0. The proposed method is as complex as the MMSE method at zero and infinity SNRs with probability one. However, the theory does not imply that the algorithm deterministically adopts the LD method at these SNRs, and there is always a probability that the proposed method performs as an ML search.

C. High SNR Approximation for the Threshold
A finite η k that is capable of achieving the ML performance and exploiting the ZCA property can be obtained by (37) or (26). Using some approximations, we propose a threshold that can be used in a near ML method that does not need a lookup table. In the simulation section, the approximated method will be shown to have a near ML performance while achieving a very low computational complexity. As it was stated previously, according to (47), the term P ([s ML ] k = [s] k , SNR k < η k ) can be neglected in (37). Therefore, we can write .
Using (52) as an approximation of the solution of (26) will result in a suboptimal performance and a dramatically reduced computational complexity. As it was previously stated, since η k ρ = ∞ is a trivial solution of (26). By scaling η k , we can come arbitrary closer to the ML performance without a lookup table. In the simulation section, we show that scaled η k yields a performance which is very close to that of the ML detector with a significantly lower computational complexity.
VI. SIMULATION RESULTS In this section, we first compare the computational complexity bounds with the actual simulated number of visited nodes FP Algorithm [21] ((a)) Lattice-independet radius  to examine the ZCA property for different methods. Next, we verify the claimed theoretical results on the performance and the computational complexity of the proposed method in two different channels: flat fading Rayleigh MIMO channel and frequency selective channel. In our simulations, we consider [21] as an FP variant and the SE algorithm of [9] as an SE variant of the SD method. The curves of complexity and symbol error probability are plotted versus the total SNR, ρ T Kρ, and the number of transmit antennas.  SD algorithm where R H is the proposed radius in [10] and s B is the Babai point. It can be seen in Figs. 1(a) and 1(b), that at low SNR regime, the MAC of both FP and SE variants of the SD algorithm demonstrates a high computational complexity. It should be noted that the gap between the MAC and the actual number of visited nodes decreases with increase of the SNR. Figs 1(d) and 1(c) depict the behavior of the MAC for an MMSE-based LSR and ZF-based LSR with I = {s MMSE , H} and I = {s ZF , H}, respectively. This behavior confirms the ZCA property of the MMSE-based LSR at low and high SNR regimes. Nonetheless, it can be seen that adding the ZF detected symbol to the information set does not lead to ZCA property at low SNRs. In other words, as it can be seen in Lemma 2, the ZF detected point is not able to resolve the low SNR deficiency of the SD algorithm. This confirms the fact that the ZF-based LSR-aided SD does not obey marginal complexity optimality.

B. Frequency flat Rayleigh Fading MIMO Channel
In this simulation example, the MIMO channels are considered to be i.i.d complex Gaussian with zero mean and unit variance. The performance of the proposed method is evaluated through symbol error probability. The number of visited nodes in the SD algorithm is also calculated in order to compare the complexity of the proposed method with that of some other detection methods.
In Fig. 2, a MIMO system with six transmit and receive antennas and 4-ary QAM is considered, and it can be seen that the proposed method achieves the ML performance. The same configuration is considered in Fig. 3, to compare the complexity of the proposed method with that of the SD algorithm presented in [21] with R H . For comparison, the performance and the computational complexity of the widely linear SD in [23] is also plotted. It can be seen that the proposed algorithm achieves a lower complexity and, unlike the other SD algorithms, is as complex as the MMSE algorithm at low and high SNRs. This result corroborates our claims in Theorems 2 and 3, which means that the proposed algorithm achieves the ML performance at all SNRs and exploits the ZCA property. Moreover, it can be seen that the approximate threshold proposed in (52), with a scaling factor of two, also leads to a performance which is very close to that of the ML detector. It also demonstrates a significantly lower computational complexity. The same results can be observed from Figs. 4 and 5 for 64-ary QAM and four receive and transmit antennas. It can be seen that the performance threshold proposed in (52) is very close to the ML detector while achieving a significantly lower computational complexity.
Figs 6(a)-6(b) and 6(c) demonstrate the effect of increasing the number of antennas on the complexity of the MMSE based LSR-SD algorithm for ρ T = −5, 15, and 25. It can be observed that the LSR in the MMSE based LSR-SD compensates the SD algorithm for its high computational complexity, especially at low SNRs. Although at high SNRs, the SD algorithm has almost a linear complexity increase with the number of antennas, the MMSE-based LSR-SD leads to a dramatic complexity decrease.

C. Frequency Selective Channel
To evaluate the performance of the MMSE based LSR-SD algorithm in another application, in this simulation example, we consider a wireless point to point frequency selective channel with Rayleigh fading. The L c channel coefficients h = [h 0 . . . , h Lc−1 ] are i.i.d distributed with zero mean and unit variance. The channel input-output model is where the additive noise w[n] is i.i.d with zero mean and variance σ 2 . The transmission scheme is considered to be single carrier zero padding (ZP) block transmission [36]. One can reformulate (53) as the system model (1) [36]. In this example, the number of channel coeficients is considered to be L c = 7, the transmit vector lengths is K = 8, and consequently, the receive vector length is L = K + L c − 1. Fig. 7 demonstrates the symbol error probability for a single carrier ZP system which adopts 16-QAM as the modulation scheme. Similar to other simulation examples, it is observed that the proposed algorithm achieves ML performance and outperforms the ZF detector. Also, the approximated threshold (52), with a scaling factor of two, achieves a very close to ML performance. In Fig. 8, we compare the complexity of the proposed scheme with other simulated schemes in terms of the number of visited nodes in the reduced SD method. It can be observed that the MMSE-based LSR-SD algorithm reduces the number of visited nodes in comparison with the SD algorithm and exploits the ZCA property. Moreover, the approximated threshold (52) leads to a significantly low computational complexity.

VII. CONCLUSION
Using the law of large numbers, the minimum achievable complexity has been derived for any arbitrary SD algorithm with a set of auxiliary information. The theoretical reason for a fundamental flaw of the conventional SD algorithms at low SNRs has been analyzed. The lossless size reduction concept has been introduced as a potential solution to the low SNR deficiency of conventional SD algorithms. An ML performance-achieving method which is marginally optimal in the sense of computational complexity has been driven. Along with achieving the exact ML performance and being marginally optimal, the proposed method has been shown to reduce the computational complexity by performing a lossless search over a reduced search space.
where s k ML [n] is the k dimensional ML search candidate at the nth time slot. In order to obtain the possible sequences According to Shannon's AEP, for a given I, the number of typical k dimensional lattice points is M −Es ML {log M P(s k ML |I)} . Therefore, the number of typical k dimensional lattices is obtained as E I M −Es ML {log M P(s k ML |I)} . It should be noted that |T k | is the number of typical k dimensional lattices at the kth stage of the SD algorithm. Hence, the MAC of an SD algorithm given the information set I is According to (60) and according to (23)  Since for a fading channel, this event occurs with zero probability, a ZF based LSR-aided SD is not guaranteed to be ZCA at ρ = 0. Now we consider the high SNR regime. Using the fact that lim ρ→∞ P(s ML = s MMSE ) = 1, we have P(K r = 0) = 1, and according to (23), we obtain lim ρ→∞ C min LSR = 0.