Characterization of the Regions of Convergence of CMA Adapted Blind Fractionally Spaced Equalizer

Wonzoo Chung and C. Richard Johnson, Jr.*
School of Electrical Engineering, Cornell University

Abstract
Introduction
System Model
Regions of Convergence in the System Space
Decomposition of FSE-CM Cost Function into Radial and Spherical Terms
Regions of Convergence in the System Space
Simplified Vector Field Model for FSE-CM on the System Space
Regions of Convergence of FS-CMA
The Relation Between System Space Vector Field and Equalizer Space Vector Field
Regions of Convergence of FSE-CMA—Rotation
Regions of Convergence of FSE-CMA—Dilation
Noise Gain and Regions of Convergence
References

Abstract

The constant modulus algorithm (CMA) is an effective and popular scheme for blind adaptive equalization. Delineation of the regions of convergence of this multimodal algorithm has remained as an unresolved problem in spite of its significance with regard to CMA initialization strategies. In this paper we present a qualitative analysis of convergence regions of the fractionally spaced CMA (FS-CMA) equalizer based on a new geometrical understanding of the constant modulus cost function. We characterize the location and volume of the convergence regions of local minima, and associate the volume of the convergence regions with their MSE performance. The convergence regions of the local minima with low noise gain expand near the origin, while those of the local minima with high noise gain shrink. This explains partly the robustness of FS-CMA and the MSE optimization achieved by the widely used center spike initialization with constrained magnitude.

Introduction

Adaptive equalization based on the constant modulus (CM) criterion, which exploits fourth order source statistics, is perhaps the best well known practical blind adaptive equalizer. The fractionally spaced equalizer adapted to descend the gradient of the CM criterion (FSE-CM) has been widely used and studied intensively [4]. Recent study of the mean squared error (MSE) performance of CM cost minimization applied to a fractionally spaced receiver has emphasized proper initialization of FSE-CM equalizer [6]. Since the knowledge of convergence regions is critical for initialization strategies, a theoretical description of convergence regions of local minima is desired.

We approach this problem with two novel “tricks”. First, we decompose the FSE-CM cost function into a radial component and a spherical component, which correspond to noise gain and inter-symbol-interference (ISI) respectively. This provides a geometric understanding of FSE-CM and an immediate derivation of a closed-form expression of convergence regions in the system space. Second, we apply the system space result to the equalizer space of an arbitrary channel in a qualitative way. Just as with any (stochastic) gradient descent based adaptive equalizer, the FSE-CM cost function induces a gradient dynamic system on the equalizer space. Our analysis is focused on the dynamic system instead of the cost function. The dynamic system in the equalizer space of the given channel is represented by a linear coordinate transformed system (via the channel convolution matrix) from that of the system space. The convergence regions of the equalizer space of the FSE-CM for an arbitrary channel are result from this transformation, which performs rotation and dilation (determined by the singular decomposition of the channel convolution matrix).

The study on the effect of dilation reveals our main result on the convergence regions of FSE-CM: The convergence regions have a “exponential hypercone” structure and, hence, the convergence regions of small noise gain minima are (exponentially) expanded and those of large noise gains are shrunk (exponentially) near the origin (vice versa for far from the origin). The approximation we then use is motivated by an observed result that the spherical deformation of regions of convergence is ignorable in comparison to the radial (exponential) deformation. Thus, we use radial behavior alone to approximate regions of convergence. Although we assume a noise free model throughout our analysis, this trend of convergence regions is still valid for the moderate noise case, since below a certain SNR threshold noise simply causes smoothing effects on the FSE-CM error surface [2]. This result helps explain the asymptotic mean square error (MSE) optimization capabilities of a single spike initialization with constrained magnitude of FSE-CM.

System Model

In Figure 1, we consider a fractionally spaced linear equalization of a time invariant linear channel model c in the absence of noise.

Figure 1. System Model

We utilize the so called perfect equalization assumptions [4] so that the equalizer parameter vector ƒ is determined by the channel convolution matrix and overall system response h [4]

Let H be the space of all system responses (system space) and F be the space of equalizers (equalizer space). Eq (1) induces an isomorphism between two vector spaces

In the next section we develop a full description on the convergence regions of the FS-CMA in the system space, and in "Regions of Convergence in the System Space", we turn to the equalizer space.

Regions of Convergence in the System Space

Decomposition of FSE-CM Cost Function into Radial and Spherical Terms

Fractionally spaced blind equalization using Constant Modulus Algorithm (FSE-CM) provides an adaptive algorithm for finding the equalizer minimizing following cost function

with the update equation

where , the ratio of the fourth moment and the second moment of the source, is called the dispersion constant. The goal of blind equalization in the absence of noise is to obtain pure delays ([0 …1 … 0]) in H-space from the statistical information of the source. To quantify this objective, we define a measure of inter symbol interference (ISI) in H-space.

Definition 1 For any vector is a real valued function on H defined by;

which is nonnegative definite.

Observe that if and only if h is a pure delay.

Lemma 1 In the absence of channel noise, the FSE-CM cost function on the system space H, denoted by , for a ciculary symmetric source (such as QAM) can be expressed [2] as

where is the is defined as the kurtosis deviation of the source from the Gaussian kurtosis (with normalized kurtosis )

Henceforth, we will assume a BPSK source and a real channel. The cost function is simplified to

Figure 2 illustrates an example of this decomposition for 2 dimensional case.

Figure 2. Decomposition of FSE-CM Cost Function

Regions of Convergence in the System Space

Consider the gradient system on the system space defined by the FSE-CM cost function

The simplicity of the radial component, , results in an important property of this vector field that local minima and saddle points under a FSE-CM gradient system are mostly characterized by the spherical term, more precisely, the spherical term restricted to the unit sphere . The local minima consist of pure delays [?] and the regions of convergence are obtained by solving , which can be associated with a set of hyperelipsoids in a geometrical representation.

Theorem 1 (Regions of Convergence on H) Let denote the regions of convergence of a local minima of FSE-CM, . Then is a hypercone

illustrated in Figure 3.

Figure 3. Regions of convergence in the system space

Simplified Vector Field Model for FSE-CM on the System Space

Now we propose a simplified vector field model which extends the idea of decomposing FSE-CM into spherical and radial terms. FSE-CM has a unique radial minima in every direction which is given by

We define the set of radial minima as the radial minima surface [2, 5]. We can interpret the role of the radial term of FSE-CM roughly as bringing the parameter h onto . The final stage of adaptation is often motion “along” Ø. Since is bounded by , we approximate with . The proposed model is

where denotes the vector field on derived from the cost function . Notice that is not itself a vector field. Figure 4 provides a comparison of a) and b) .

Figure 4. Trajectories of FS-CMA and simplified model

Regions of Convergence of FS-CMA

The Relation Between System Space Vector Field and Equalizer Space Vector Field

With C a channel convolution matrix of a T/2-spaced channel c, the relation between the vector field on the system space and the FSE-CM vector field on the equalizer space is obtained from the relation h = Cƒ

From (11), we conclude every stationary point on the equalizer space is a stationary point on the system space. Therefore, the local minima of FSE-CM in equalizer space, denoted by . Notice that the norms of the local minima are distributed corresponding to the eigenvalues of .

In contrast to the stationary points, the regions of convergence of , denoted by , cannot be obtained from simple linear transformation, since the cost function is non-linear. Therefore, we investigate the effects of a linear transformed vector field on the convergence regions.

Let be the singular decomposition of C with . The vector field is rewritten as

Let be a local minimum on F under . Then the region of convergence of , is obtained from through the following process, which will be described in the following subsections.

“Rotate” under by the unitary matrix
“Dilate” by diagonal matrix
“Rotate” again the stretched region of convergence, say S, by the unitary matrix V

The chart below summarizes this process.

Example 1 Consider a T/2-spaced channel c = [0.11, 0.8779, 0.3762, 0.2751]. Then

and the process above unfolds as shown in Figure 5.

Figure 5. Regions of convergence of FSE-CM: equalizer space through system space

In following subsections, each of the steps in Figure 5 will be described in detail.

Regions of Convergence of FSE-CM—Rotation

Lemma 2 (Rotation) Let be a given vector field on F and U be an unitary matrix. Denote as a vector field on F induced by U in the following way

Then, for a local minima ƒ under is a local minima under . Denote the regions of convergence ƒ as R(ƒ) and that of under as . It holds that

Regions of Convergence of FSE-CM—Dilation

Unfortunately, the “dilation” part does not allow any closed form expression. We are limited to sketching a general trend by using an approximate model.

Let be the vector field model of FSE-CM on the system space defined in "Simplified Vector Field Model for FSE-CM on the System Space." Let be a U-transformed vector field of (Lemma 2). Let denote the regions of convergence under and denote those on . By Lemma 2, are rotated hyper-cones and equally divide . We assume the rotation U is not so severe that for each i.

Let be a diagonal matrix with denote the vector field model from . Since

where denotes the vector field on induced via from the on . Under this model regions of convergence are determined by the spherical term :

Let be the local minima under and be the convergence region of , and be that of on . Then the convergence region has the following form from (13)

Since every trajectory is an exponential curve and they meet all at the origin, we label this an exponential hyper-cone.

Therefore, it is important to delineate , which is transformed by from . From the view of differential manifolds [1], the effect of on under is characterized by the effect of on the under , where and is a projection map . Let . Then, for a small step size , the trajectory of y under is generated by

The term introduces non-linear deformation, and thus does not agree with in general. However, the deformation does not cause significant difference between volumes of and , though it causes a “convexing” effect on the shape as Example 2 shows. Hence, we approximate with by ignoring this less significant deformation.

Example 2 Let

We consider the nonlinear deformation due to . When is a rotated projection of the convergence region in Figure 3 in "Regions of Convergence in the System Space (Figure 6 a). As increases the non-linear deformation starts (Figure 6 b). In the asymptotic case, when , we have a polygon shape of which vertices consist of local minima and maxima (Figure 6 c).

Figure 6. Deformation of Convergence on by various

Noise Gain and Regions of Convergence

We are interested in the volume of near the origin. Let be the convergence region of on sphere , i.e.,

First we consider the projections of on via straight rays

Then, for . From a comparison of two trajectories

for t < 0, we can observe that is exponentially expanded from in all axises, while is shrunk from in all axises. is exponentially expanded from in all k (> i)-th axises and shrunk in all k (< i)-th axises (Figure 7).

Figure 7. Comparison between , and

Furthermore . Therefore, we have

Theorem 2 (Regions of Convergence of FS-CMA) Let be the local minima of FS-CMA for a T/2-spaced channel c and let C be the channel convolution matrix. Denote as the convergence region of .

I. are exponential hyper-cones centered on

II. Let

Notice that if we initialize CMA near the origin with single or double spike (i.e, ƒ = [0 … 0 1 (1) 0 … 0]), it is likely that the initialization lies in a region of convergence of a CM local minima with small noise gain by theorem 2.

Conclusion

We characterized the regions of convergence of FSE-CM corresponding to the different system delays. The regions of convergence are exponential hyper-cones. Near the origin, the CM solutions of small noise gain has an exponentially large region of convergence. This result suggests that a spike initialization with constrained magnitude would lie in the ROC of a small noise gain with a high probability. The implication of this result for noisy and undermodelled systems is yet to be studied.

References

W.M. Boothby, “An Introduction to Differentiable Manifolds and Riemannian Geometry,” Academic Press, Inc., 1986.
W. Chung, J.P. LeBlanc, “The local minima of fractionally-spaced CMA blind equalizer cost function in the presence of channel noise,” Proc. of IEEE Conf. Acoust., Speech, Signal Processing, May 1998.
I. Fijalkow, A. Touzni, and J.R. Treichler, “Fractionally spaced equalization using CMA: robustness to channel noise and lack of disparity,” IEEE transactions on Signal Processing, vol. 45, no. 1, pp. 55–66, Jan. 1997.
C.R. Johnson, Jr., P.B. Schniter, T.S. Endres, J.M. Behm, D.R. Brown, and R.A. Casas, “Blind Equalization Using the Constant Modulus Criterion: A Review,” Proc. IEEE, 1998.
J.P. LeBlanc, C.R. Johnson, Jr., “Global CMA Error Surface Characteristics, Source Statistics Effects: Polytopes and Manifolds,” 13th Int. Conf. on DSP (Santorini, Greece), Jul. 1997.
H.H. Zeng, L. Tong and C.R. Johnson, Jr., “Relationships between the constant modulus and Wiener receivers,” IEEE Trans. Info. Theory, 1998.

Footnote

*Supported by NSF grants MIP-9509011 and ECS-9528363, and Applied Signal Technology.