Slowest-Descent Search

Slowest-Descent Search

The basic idea of the slowest-descent search method is to choose the candidate points in W such that they are closest to a line (q + mg) in , originating from q and along a direction g, where the likelihood function p (y|b) drops at the slowest rate. Given any line in , there are at most K points where the line intersects the coordinate hyperplanes (e.g., q¹ and q² in Fig. 3.10 for K = 2). The set of intersection points corresponding to a line defined by q and g can be expressed as

Equation 3.105

Any point on the line except for an intersection point has a unique closest candidate point in {+1, –1}^K. An intersection point is of equal distance from its two neighboring candidate points [e.g., q¹ is equidistant to b¹ and b² in Fig. 3.10(a)].

Two neighboring intersection points share a unique closest candidate point [e.g., q¹ and q² share the nearest candidate point b² in Fig. 3.10(a)]. Define

Equation 3.106

Equation 3.107

It is seen that (3.107) assigns to each intersection point qⁱ a closest candidate point bⁱ that is on the opposite side of the ith coordinate hyperplane from b^* [cf. Fig. 3.10(a) and (b)]. We next show that the K points in (3.107) are distinct. To see this, we use proof by contradiction. Suppose that otherwise the set in (3.107) contains two identical candidate points, say b¹ = b². It then follows from the definitions in (3.105) and (3.107) that

Equation 3.108

Equation 3.109

Consider the case q₁ > 0 and q₂ > 0. By (3.108) and (3.109) we have

Equation 3.110

Equation 3.111

Hence, (3.110) and (3.111) contradict each other. The same contradiction arises for the other three choices of polarities for q₁ and q₂.

In general, the slowest-descent search method chooses the candidate set W in (3.104) as follows:

Equation 3.112

where q_k and denote the kth elements of the respective vectors q and g^q. Hence, {b^q,m}_m contains the K closest neighbors of q in {–1, +1}^K along the direction of g^q. Note that represents the Q mutually orthogonal directions where the likelihood function p(y|b) drops most slowly from the peak point q. Intuitively, the maximum-likelihood solution in (3.101) is probably in this neighborhood. The multiuser detection algorithm based on the slowest-descent-search method is summarized as follows (assuming that the signature waveforms S and the complex amplitudes A of all users are known).

Algorithm 3.3: [Slowest-descent-search multiuser detector]

• Compute the Hessian matrix given by (3.103) and its Q smallest eigen-vectors g¹, . . . , g^Q.

• Compute the stationary point q given by (3.102).

• Solve the discrete optimization problem defined by (3.104) and (3.112) by an exhaustive search [over (KQ + 1) points].

The first step involves calculating the eigenvectors of a K x K symmetric matrix, the second step involves inverting a K xK matrix, and the third step involves evaluating the likelihood values at KQ + 1 points. Note that the first two steps need to be performed only once if a block of M data bits need to be demodulated. Hence the dominant computational complexity of the algorithm above is (KQ) per bit for K users.

For simulations, we assume a processing gain N = 15, the number of users K = 8, and equal amplitudes of user signals (i.e., |A_k| =1, k =1, . . ., K). The signature matrix S and the user phase offsets {A_k} are chosen at random and kept fixed throughout the simulations. Figure 3.11 demonstrates that the slowest-descent method with only one search direction (Q = 1) offers a significant performance gain over the linear decorrelator. Searching one more direction (Q = 2) results in some additional performance improvement. Further increase in the number of search directions only results in a diminishing improvement in performance.