# Slowing and Loss of Complexity in Alzheimer's EEG: Two Sides of the Same Coin?

Authors: Justin Dauwels; K. Srinivasan; M. Ramasubba Reddy; Toshimitsu Musha; François-Benoît Vialatte; Charles  Latchoumane; Jaeseung Jeong; Andrzej Cichocki
Journal: International Journal of Alzheimer's Disease
 (2011)

---

## Abstract

Medical studies have shown that EEG of
Alzheimer's disease (AD) patients is “slower” (i.e., contains
more low-frequency power) and is less complex compared to
age-matched healthy subjects. The relation between those two
phenomena has not yet been studied, and they are often silently
assumed to be independent. In this paper, it is shown that
both phenomena are strongly related. Strong correlation between
slowing and loss of complexity is observed in two independent
EEG datasets: (1) EEG of predementia patients (a.k.a. Mild
Cognitive Impairment; MCI) and control subjects; (2) EEG of
mild AD patients and control subjects. The two data sets are
from different patients, different hospitals and obtained through
different recording systems. The paper also investigates the potential of EEG slowing and
loss of EEG complexity as indicators of AD onset. In particular,
relative power and complexity measures are used as features to
classify the MCI and MiAD patients versus age-matched control
subjects. When combined with two synchrony measures (Granger causality and stochastic event
synchrony), classification rates of 83% (MCI) and 98% (MiAD)
are obtained. By including the compression ratios as features,
slightly better classification rates are obtained than with relative
power and synchrony measures alone.


---

## Body

## 1. Introduction

Alzheimer's disease (AD) is the most common form of dementia; it is the sixth leading cause of death in the United States. More than 10% of Americans over age 65 suffer from AD, and it is predicted that the prevalence of AD will triple within next 50 years [1–3]. Currently, no known medicine exists for curing AD, but a number of medications are believed to delay the symptoms and the causes of the disease.The progression of AD can be categorized into three different stages: mild, moderate, and severe AD; there is also a stage known as Mild Cognitive Impairment (MCI) or predementia, that characterizes a population of elderly subjects who are not compromised in their daily living, but have a subclinical and isolated cognitive deficit and are potentially at risk of developing Alzheimer's disease [4–6]. Around 6% to 25% of people affected by MCI progress to AD. MCI may develop into mild AD and next moderate AD; in those stages, cognitive deficits become more severe, and the patients become more dependent on caregivers. In the final stage known as severe AD, the personality of patients may change dramatically, and patients are entirely dependent on caregivers [7].Diagnosing MCI and Mild Alzheimer’s disease is hard, because most symptoms are often dismissed as normal consequences of aging. To diagnose MCI or mild AD, extensive testing is required, to eliminate all possible alternative causes. Tests include psychological evaluations such as Mini-Mental State Examination (MMSE), blood tests, spinal fluid, neurological examination, and imaging techniques [8, 9].Several research groups have investigated the potential of electroencephalograms (EEGs) for diagnosing AD in recent years. Since EEG recording systems are nowadays relatively inexpensive and mobile, EEG may potentially be used in the future as a tool to screen a large population for the risk of AD, before proceeding to any expensive imaging or invasive procedures. To date, however, EEG does not have sufficiently high specificity and sensitivity to assume the role of reliable and reproducible method of screening AD.In recent years, several studies have shown that AD has at least three major effects on EEG (see [10, 11] for an in-depth review): slowing, reduced complexity, and loss of synchrony. However, these effects tend to vary across patients, which makes diagnosis of AD a difficult task. Many recent studies are devoted to improving the sensitivity of EEG for diagnosing AD. We refer to [11] for a detailed review on various EEG statistics that have been used in this context.In this paper, we investigate the relation between slowing and reduced complexity in AD EEG. Those two phenomena are often silently assumed to be independent. However, since low-frequency signals are more regular than signals with high-frequency components, one would expect that slowing and reduced complexity in AD EEG are strongly related to each other. Nevertheless no study so far has analyzed the relation between both phenomena on a statistical basis though.In order to investigate the slowing effect in AD EEG, we compute relative power in the standard EEG frequency bands (see Table1). When relative power is larger than usual in low-frequency bands (delta and/or theta), it is said that the EEG is “slower” and that “EEG slowing” occurs. We quantify the irregularity of EEG by a standard measure, that is, Lempel-Ziv complexity (see Table 1). We also apply several lossless compression algorithms to the EEG, and we use the resulting compression ratios (reduction in data size after compression) as regularity measures (see Table 1). Regular signals are more compressible than irregular signals, and therefore, they result in larger compression ratios; as a consequence, compression ratios are a measure of the regularity of signals.Table 1
Overview of statistical measures: relative power, Lempel-Ziv complexity, and lossless compression ratio.
MeasureDescriptionReferencesRelative powerPower within specific EEG frequency band normalized by total power[12]Frequency bands: 0.5–4 Hz (delta), 4–8 Hz (theta), 8–10 Hz (alpha 1), 10–12 Hz (alpha 2), 12–30 Hz (beta)Lempel-Ziv complexityNumber of different patterns present in an EEG signal (complexity measure)[13]Lossless compression ratioReduction of the size of EEG data after lossless compression (regularity measure)[14, 15]Compression algorithms considered here: 1D SPIHT, 2D SPIHT, and 2D SPIHT followed by arithmetic codingWe consider two EEG datasets: (1) EEG of predementia patients (a.k.a. Mild Cognitive Impairment; MCI) and control subjects; (2) EEG of mild AD patients and control subjects. The two datasets are from different patients, different hospitals and obtained through different recording systems.We will show that the theta band (θ) relative power is significantly larger in both groups of patients compared to age-matched control subjects and that the lossless compression ratios are significantly larger in MiAD patients than in the age-matched control subjects; however, no significant perturbation of Lempel-Ziv complexity and the lossless compression ratios is observed for the MCI patients. Interestingly, our numerical analysis will reveal strong correlation between theta relative power on the one hand and Lempel-Ziv complexity and the lossless compression ratios on the other hand; in other words, the effects of slowing and loss of complexity in AD EEG seem to be significantly coupled, at least in the two EEG datasets at hand.The paper is structured as follows. In Section2 we explain how relative power of EEG may be computed. In Section 3, we describe the Lempel-Ziv complexity measure and the lossless compression schemes used in this study. In Section 4 we discuss the two EEG datasets, and in Section 5 we present our results. We provide concluding remarks and topics of future research in Section 6.Readers who are not interested in the technical and mathematical details of our data analysis may skip Sections2 and 3 and may directly proceed to Section 4.


## 2. Relative Power of EEG

The spectrum of EEG is helpful in describing and understanding brain activity. The EEG spectrum is commonly divided in specific frequency bands: 0.5–4 Hz (delta), 4–8 Hz (theta), 8–10 Hz (alpha 1), 10–12 Hz (alpha 2), 12–30 Hz (beta), and 30–100 Hz (gamma) [12]. Neurological diseases, including MCI and AD, often affect the EEG spectrum. Many studies have shown that MCI and AD cause EEG signals to “slow down” (see [11] and references therein), corresponding to an increase of power in low-frequency bands (delta and theta band, 0.5–8 Hz) and a decrease of power in higher-frequency bands (alpha and beta, 8–30 Hz).The EEG spectrum can be computed by means of the Discrete Fourier Transform (DFT) of the EEG [11]. The DFT X(fn) of the sequence x is usually computed at multiples fn of fT=1/T, where T refers to the length of the signal. For computational convenience, the length of the sequence x is often extended to the nearest power of two by zero padding. As in [11], let us consider an example with T=20 s and the sampling frequency 200 Hz, then DFT is computed at 0 Hz, 0.05 Hz, 0.1 Hz,…,200 Hz. The Nyquist theorem states that only one half the spectrum is of interest, while the other half is the mirror image of the first half; hence for the above example, it is enough to retain the DFT values at 0 Hz, 0.05 Hz, 0.1 Hz,…,100 Hz. The DFT values X(fn) are complex, and we are mostly interested in their absolute magnitude |X(f)|. The relative power of a frequency band is computed by summing |X(fn)| over the frequencies fn in that band and next by dividing the resulting intraband sum by the sum of |X(f)| over all DFT frequencies fn.


## 3. Complexity Measures

A variety of complexity measures have been used to quantify EEG complexity, stemming from several areas ranging from statistical physics to information theory. We refer to [11] for more information. Earlier studies have reported that the EEG of MCI and AD patients seems to be more regular (i.e., less complex) than in age-matched control subjects. It is conjectured that due to MCI/AD-induced loss of neurons and perturbed anatomical and/or functional coupling, fewer neurons interact with each other, and the neural activity patterns and dynamics become simpler and more predictable.As mentioned earlier, we quantify EEG complexity by a standard measure, that is, Lempel-Ziv complexity. In addition, we use lossless compression ratios as regularity measures. In the following, we describe Lempel-Ziv complexity, and next we elaborate on lossless compression and its use as measure for regularity.


### 3.1. Lempel-Ziv (LZ) Complexity

The Lempel-Ziv complexity measure (LZ complexity) computes the number of different patterns present in a sequence of symbols [13]; if the number of different patterns is large, the sequence is complex and hence difficult to compress. LZ complexity is obtained by dividing the number of different patterns by the maximum complexity of a sequence of length N. For more details we refer to [16].To compute LZ complexity, the time series is first reduced to a symbol list. For the sake of simplicity, we convert the EEG signals into binary sequencess=s(1),s(2),…,s(N), where s(i)=0 if x(i)<Td and s(i)=1 otherwise; that approach was also followed in [16]. The threshold Td is chosen as the median of x, since the latter is robust to outliers.


### 3.2. Lossless Compression Algorithms

In this section, we briefly explain the lossless compression algorithms applied in this study (see Figure2); we will consider three different algorithms, which were all proposed in [14, 15]. The aim of compression is to reduce the size of a given data source (e.g., EEG data). In lossless compression (e.g., ZIP compression algorithm), no information in the original data source is lost after compression, in contrast to lossy compression, where the original can only approximately be constructed after compression (e.g., JPEG compression algorithm for images).Biomedical signals such as EEG often have adecaying spectrum: the energy is mostly concentrated at low frequencies, and it decays with increasing frequency. Therefore, the spectral components are close to zero at high frequencies; the same holds for coefficients in the time-frequency representation corresponding to high frequencies. To exploit this phenomenon, compression algorithms often subject the given data source to a transform (e.g., time-frequency transform), which results in an alternative representation of the data. The three algorithms used in this study all map the signals into another domain, that is, time-frequency domain; the sparseness of the time-frequency representation is then exploited to form a compact code. We now briefly outline the compression process (see  Figure 2). First the EEG signal is preprocessed, that is, the DC component (average value of EEG signal) is removed by applying backward difference; the resulting zero-mean signal is then arranged as a 1D vector (see  Figure 2(a); Algorithm A) or 2D matrix (see  Figures 2(b) and 2(c); Algorithms B and C). The resulting structure is then decomposed into different frequency bands via integer lifting wavelet transform, which maps the signals to integers on several time scales; at last, a set partitioning coding scheme converts the (integer) wavelet coefficients into a compact representation. In the following sections we describe those different steps in more detail, and then we elaborate on the differences between the three algorithms (Algorithms A, B, and C).


#### 3.2.1. Backward Difference

First the EEG signalx is preprocessed, that is, the DC component (average value of EEG signal) is removed; this is performed via backward difference operation
(1)x̃(n)=x(n)-x(n-1),
where x̃(n) is the signal obtained by applying the backward difference. Next the EEG is arranged as a vector of size N (1D compression) or as a matrix of size N×N (2D compression); the latter matrix is filled starting at the top left-hand side, from left to right on the odd rows, and from right to left on the even rows. In matrices, each entry has 8 nearest neighbors (except for entries in the first/last row/column), compared to two nearest neighbors in vectors (except for first and last entries). In the present application, neighboring entries are adjacent EEG samples, which are highly correlated [14]. By leveraging on the additional nearest neighbors (8 instead of 2), 2D compression often yields better compression ratios than 1D compression [14].


#### 3.2.2. Lifting Wavelet Transform

A wavelet transform decomposes a given signal into different frequency bands; it allows to represent the signal in multiple resolutions (coarse to fine) [17]. Wavelets are usually realized by a set of filters, operating in parallel (“filter banks”). An alternative method of realizing wavelets is alifting scheme [18], which consists of a cascade of simple filters; it may be viewed as the factorization of a filter bank into elementary filters. One such simple filter is depicted in  Figures 1(a) and 1(b)). The former shows the forward lifting transformation; the signal x is first split into oddand even phases xo and xe, respectively, containing the odd and even samples, respectively, of input signal x. The odd and even phases contain adjacent samples; in natural signals such as EEG, adjacent samples are highly correlated. Therefore, the odd phase may be predicted from the even phase (and vice versa). By subtracting the prediction x̂o=p(xe) from the odd phase, we are left with a high-frequency residue signal (HF) of the odd phase. The latter is used in another lifting step, to predict the even phase xe (“update” u); the resulting prediction is subtracted from the even phase xe, which leaves the low-frequency component (LF) of the even phase xe; this also ensures the complete frequency separation between an LF and HF component. The forward transform of  Figure 1(a) is easily invertible by reversing the steps and flipping the signs (see  Figure 1(b)). We implement the prediction p and update u by means of the widely used biorthogonal 5/3 filter [19], as we did in our previous study on EEG compression [15].Wavelet transform realization via lifting scheme (a) Forward transformation. (b) Inverse transformation. The boxes labeled byz-1 stand for delays (over one sample). The boxes ↓2 and ↑2 represent downsampling and upsampling by a factor of two, respectively; in the latter a zero is inserted after every sample, whereas in the former, every second sample is removed. The lifting scheme repeats two primitive steps: prediction p and update u.
(a)(b)Lossless EEG compression algorithms apply wavelet transforms followed by Set Partitioning in Hierarchical Trees (SPIHT).
(a)
Algorithm A: EEG compression using 1D SPIHT(b)
Algorithm B: EEG compression using 2D SPIHT(c)
Algorithm C: EEG compression using 2D SPIHT (at optimal rateRo), followed by arithmetic coding for the residualsIn a lifting scheme, the pair of lifting steps, that is, predictionp and update u, is repeated several times, leading to multiscale representation of the input signal x (“wavelet”); the nature and number of lifting steps p and u depend on the type of wavelets [18]. Integer wavelet transforms can easily be realized by systematic rounding and truncation of the intermediate results, that is, output of p and u [20].The lifting wavelet transform provides a sparse, multiresolution representation, that is well suited for effective compression (e.g., by means of SPIHT, to be explained in next section);integerlifting in particular enables convenient and simple implementations of lossless compression.


#### 3.2.3. Set Partitioning in Hierarchical Trees Algorithm (SPIHT)

As the last step in the process, the wavelet-transformed signals are compressed. We use a widely known wavelet-based compression scheme, that is,Set Partitioning in Hierarchical Trees (SPIHT) [21]. The underlying idea is set partitioning: sets of samples are recursively split, guided by a series of threshold tests. This approach is particularly well suited for wavelet-transformed data, as wavelet coefficients are naturally clustered. In SPIHT the sample sets are non-overlapping, and they are organized by means of a tree each set is rooted in a subset of low-frequency coefficients, and branches successively to subsets of high-frequency coefficients in the same orientation (see  Figure 3). The search for coefficients associated with a particular threshold usually starts at the root node and proceeds successively towards the leaves of the tree, until all significant coefficients are listed. Such tree-based search, starting at coarse resolution at the root and ending with the finest resolution at the leaves, results in output signals of increasing quality and resolution.Figure 3
Wavelet decomposition of the 2D matrix and associated tree-based set originating from the low-frequency band. The root node (black) branches towards horizontal, vertical, and diagonal higher-frequency bands (H, V, D).The integer wavelet transform, in conjunction with SPIHT, yields a quality and resolution scalable bitstream: the quality and resolution of the signal improve as bitstream progresses. This is a very desirable property for real-time applications. Moreover, the output bitstream is embedded: the bitstream can be truncated at any point to approximately reconstruct the signal. When the bitstream is fully decoded, we obtain a lossless representation.Though this coding scheme is specifically developed for images, it can be applied to all data sources with decaying spectrum [22].


#### 3.2.4. Three SPIHT Compression Algorithms

The three compression algorithms are depicted in  Figure2: (1) 1D SPIHT compression, where the EEG is arranged as a vector (Figure 2(a)), (2) 2D SPIHT compression, where the EEG is arranged as a matrix (Figure 2(b)), and (3) 2D SPIHT compression (at optimal rate Ro), followed by arithmetic coding for the residuals (Figure 2(c)). In the 1D SPIHT compression scheme, backward differentiated EEG is subjected to integer wavelet transformation followed by SPIHT coding. The 2D SPIHT compression scheme arranges the EEG as a matrix instead of a vector. In the two-stage 2D SPIHT compression scheme, arithmetic coding is applied to the residuals of 2D SPIHT compression: first SPIHT encodes the wavelet coefficients till the source loses its memory and behaves as independent and identically distributed (corresponding to the optimal bit-rate Ro); next the residuals are encoded by means of single-context arithmetic coding.


## 3.1. Lempel-Ziv (LZ) Complexity

The Lempel-Ziv complexity measure (LZ complexity) computes the number of different patterns present in a sequence of symbols [13]; if the number of different patterns is large, the sequence is complex and hence difficult to compress. LZ complexity is obtained by dividing the number of different patterns by the maximum complexity of a sequence of length N. For more details we refer to [16].To compute LZ complexity, the time series is first reduced to a symbol list. For the sake of simplicity, we convert the EEG signals into binary sequencess=s(1),s(2),…,s(N), where s(i)=0 if x(i)<Td and s(i)=1 otherwise; that approach was also followed in [16]. The threshold Td is chosen as the median of x, since the latter is robust to outliers.


## 3.2. Lossless Compression Algorithms

In this section, we briefly explain the lossless compression algorithms applied in this study (see Figure2); we will consider three different algorithms, which were all proposed in [14, 15]. The aim of compression is to reduce the size of a given data source (e.g., EEG data). In lossless compression (e.g., ZIP compression algorithm), no information in the original data source is lost after compression, in contrast to lossy compression, where the original can only approximately be constructed after compression (e.g., JPEG compression algorithm for images).Biomedical signals such as EEG often have adecaying spectrum: the energy is mostly concentrated at low frequencies, and it decays with increasing frequency. Therefore, the spectral components are close to zero at high frequencies; the same holds for coefficients in the time-frequency representation corresponding to high frequencies. To exploit this phenomenon, compression algorithms often subject the given data source to a transform (e.g., time-frequency transform), which results in an alternative representation of the data. The three algorithms used in this study all map the signals into another domain, that is, time-frequency domain; the sparseness of the time-frequency representation is then exploited to form a compact code. We now briefly outline the compression process (see  Figure 2). First the EEG signal is preprocessed, that is, the DC component (average value of EEG signal) is removed by applying backward difference; the resulting zero-mean signal is then arranged as a 1D vector (see  Figure 2(a); Algorithm A) or 2D matrix (see  Figures 2(b) and 2(c); Algorithms B and C). The resulting structure is then decomposed into different frequency bands via integer lifting wavelet transform, which maps the signals to integers on several time scales; at last, a set partitioning coding scheme converts the (integer) wavelet coefficients into a compact representation. In the following sections we describe those different steps in more detail, and then we elaborate on the differences between the three algorithms (Algorithms A, B, and C).


### 3.2.1. Backward Difference

First the EEG signalx is preprocessed, that is, the DC component (average value of EEG signal) is removed; this is performed via backward difference operation
(1)x̃(n)=x(n)-x(n-1),
where x̃(n) is the signal obtained by applying the backward difference. Next the EEG is arranged as a vector of size N (1D compression) or as a matrix of size N×N (2D compression); the latter matrix is filled starting at the top left-hand side, from left to right on the odd rows, and from right to left on the even rows. In matrices, each entry has 8 nearest neighbors (except for entries in the first/last row/column), compared to two nearest neighbors in vectors (except for first and last entries). In the present application, neighboring entries are adjacent EEG samples, which are highly correlated [14]. By leveraging on the additional nearest neighbors (8 instead of 2), 2D compression often yields better compression ratios than 1D compression [14].


### 3.2.2. Lifting Wavelet Transform

A wavelet transform decomposes a given signal into different frequency bands; it allows to represent the signal in multiple resolutions (coarse to fine) [17]. Wavelets are usually realized by a set of filters, operating in parallel (“filter banks”). An alternative method of realizing wavelets is alifting scheme [18], which consists of a cascade of simple filters; it may be viewed as the factorization of a filter bank into elementary filters. One such simple filter is depicted in  Figures 1(a) and 1(b)). The former shows the forward lifting transformation; the signal x is first split into oddand even phases xo and xe, respectively, containing the odd and even samples, respectively, of input signal x. The odd and even phases contain adjacent samples; in natural signals such as EEG, adjacent samples are highly correlated. Therefore, the odd phase may be predicted from the even phase (and vice versa). By subtracting the prediction x̂o=p(xe) from the odd phase, we are left with a high-frequency residue signal (HF) of the odd phase. The latter is used in another lifting step, to predict the even phase xe (“update” u); the resulting prediction is subtracted from the even phase xe, which leaves the low-frequency component (LF) of the even phase xe; this also ensures the complete frequency separation between an LF and HF component. The forward transform of  Figure 1(a) is easily invertible by reversing the steps and flipping the signs (see  Figure 1(b)). We implement the prediction p and update u by means of the widely used biorthogonal 5/3 filter [19], as we did in our previous study on EEG compression [15].Wavelet transform realization via lifting scheme (a) Forward transformation. (b) Inverse transformation. The boxes labeled byz-1 stand for delays (over one sample). The boxes ↓2 and ↑2 represent downsampling and upsampling by a factor of two, respectively; in the latter a zero is inserted after every sample, whereas in the former, every second sample is removed. The lifting scheme repeats two primitive steps: prediction p and update u.
(a)(b)Lossless EEG compression algorithms apply wavelet transforms followed by Set Partitioning in Hierarchical Trees (SPIHT).
(a)
Algorithm A: EEG compression using 1D SPIHT(b)
Algorithm B: EEG compression using 2D SPIHT(c)
Algorithm C: EEG compression using 2D SPIHT (at optimal rateRo), followed by arithmetic coding for the residualsIn a lifting scheme, the pair of lifting steps, that is, predictionp and update u, is repeated several times, leading to multiscale representation of the input signal x (“wavelet”); the nature and number of lifting steps p and u depend on the type of wavelets [18]. Integer wavelet transforms can easily be realized by systematic rounding and truncation of the intermediate results, that is, output of p and u [20].The lifting wavelet transform provides a sparse, multiresolution representation, that is well suited for effective compression (e.g., by means of SPIHT, to be explained in next section);integerlifting in particular enables convenient and simple implementations of lossless compression.


### 3.2.3. Set Partitioning in Hierarchical Trees Algorithm (SPIHT)

As the last step in the process, the wavelet-transformed signals are compressed. We use a widely known wavelet-based compression scheme, that is,Set Partitioning in Hierarchical Trees (SPIHT) [21]. The underlying idea is set partitioning: sets of samples are recursively split, guided by a series of threshold tests. This approach is particularly well suited for wavelet-transformed data, as wavelet coefficients are naturally clustered. In SPIHT the sample sets are non-overlapping, and they are organized by means of a tree each set is rooted in a subset of low-frequency coefficients, and branches successively to subsets of high-frequency coefficients in the same orientation (see  Figure 3). The search for coefficients associated with a particular threshold usually starts at the root node and proceeds successively towards the leaves of the tree, until all significant coefficients are listed. Such tree-based search, starting at coarse resolution at the root and ending with the finest resolution at the leaves, results in output signals of increasing quality and resolution.Figure 3
Wavelet decomposition of the 2D matrix and associated tree-based set originating from the low-frequency band. The root node (black) branches towards horizontal, vertical, and diagonal higher-frequency bands (H, V, D).The integer wavelet transform, in conjunction with SPIHT, yields a quality and resolution scalable bitstream: the quality and resolution of the signal improve as bitstream progresses. This is a very desirable property for real-time applications. Moreover, the output bitstream is embedded: the bitstream can be truncated at any point to approximately reconstruct the signal. When the bitstream is fully decoded, we obtain a lossless representation.Though this coding scheme is specifically developed for images, it can be applied to all data sources with decaying spectrum [22].


### 3.2.4. Three SPIHT Compression Algorithms

The three compression algorithms are depicted in  Figure2: (1) 1D SPIHT compression, where the EEG is arranged as a vector (Figure 2(a)), (2) 2D SPIHT compression, where the EEG is arranged as a matrix (Figure 2(b)), and (3) 2D SPIHT compression (at optimal rate Ro), followed by arithmetic coding for the residuals (Figure 2(c)). In the 1D SPIHT compression scheme, backward differentiated EEG is subjected to integer wavelet transformation followed by SPIHT coding. The 2D SPIHT compression scheme arranges the EEG as a matrix instead of a vector. In the two-stage 2D SPIHT compression scheme, arithmetic coding is applied to the residuals of 2D SPIHT compression: first SPIHT encodes the wavelet coefficients till the source loses its memory and behaves as independent and identically distributed (corresponding to the optimal bit-rate Ro); next the residuals are encoded by means of single-context arithmetic coding.


## 3.2.1. Backward Difference

First the EEG signalx is preprocessed, that is, the DC component (average value of EEG signal) is removed; this is performed via backward difference operation
(1)x̃(n)=x(n)-x(n-1),
where x̃(n) is the signal obtained by applying the backward difference. Next the EEG is arranged as a vector of size N (1D compression) or as a matrix of size N×N (2D compression); the latter matrix is filled starting at the top left-hand side, from left to right on the odd rows, and from right to left on the even rows. In matrices, each entry has 8 nearest neighbors (except for entries in the first/last row/column), compared to two nearest neighbors in vectors (except for first and last entries). In the present application, neighboring entries are adjacent EEG samples, which are highly correlated [14]. By leveraging on the additional nearest neighbors (8 instead of 2), 2D compression often yields better compression ratios than 1D compression [14].


## 3.2.2. Lifting Wavelet Transform

A wavelet transform decomposes a given signal into different frequency bands; it allows to represent the signal in multiple resolutions (coarse to fine) [17]. Wavelets are usually realized by a set of filters, operating in parallel (“filter banks”). An alternative method of realizing wavelets is alifting scheme [18], which consists of a cascade of simple filters; it may be viewed as the factorization of a filter bank into elementary filters. One such simple filter is depicted in  Figures 1(a) and 1(b)). The former shows the forward lifting transformation; the signal x is first split into oddand even phases xo and xe, respectively, containing the odd and even samples, respectively, of input signal x. The odd and even phases contain adjacent samples; in natural signals such as EEG, adjacent samples are highly correlated. Therefore, the odd phase may be predicted from the even phase (and vice versa). By subtracting the prediction x̂o=p(xe) from the odd phase, we are left with a high-frequency residue signal (HF) of the odd phase. The latter is used in another lifting step, to predict the even phase xe (“update” u); the resulting prediction is subtracted from the even phase xe, which leaves the low-frequency component (LF) of the even phase xe; this also ensures the complete frequency separation between an LF and HF component. The forward transform of  Figure 1(a) is easily invertible by reversing the steps and flipping the signs (see  Figure 1(b)). We implement the prediction p and update u by means of the widely used biorthogonal 5/3 filter [19], as we did in our previous study on EEG compression [15].Wavelet transform realization via lifting scheme (a) Forward transformation. (b) Inverse transformation. The boxes labeled byz-1 stand for delays (over one sample). The boxes ↓2 and ↑2 represent downsampling and upsampling by a factor of two, respectively; in the latter a zero is inserted after every sample, whereas in the former, every second sample is removed. The lifting scheme repeats two primitive steps: prediction p and update u.
(a)(b)Lossless EEG compression algorithms apply wavelet transforms followed by Set Partitioning in Hierarchical Trees (SPIHT).
(a)
Algorithm A: EEG compression using 1D SPIHT(b)
Algorithm B: EEG compression using 2D SPIHT(c)
Algorithm C: EEG compression using 2D SPIHT (at optimal rateRo), followed by arithmetic coding for the residualsIn a lifting scheme, the pair of lifting steps, that is, predictionp and update u, is repeated several times, leading to multiscale representation of the input signal x (“wavelet”); the nature and number of lifting steps p and u depend on the type of wavelets [18]. Integer wavelet transforms can easily be realized by systematic rounding and truncation of the intermediate results, that is, output of p and u [20].The lifting wavelet transform provides a sparse, multiresolution representation, that is well suited for effective compression (e.g., by means of SPIHT, to be explained in next section);integerlifting in particular enables convenient and simple implementations of lossless compression.


## 3.2.3. Set Partitioning in Hierarchical Trees Algorithm (SPIHT)

As the last step in the process, the wavelet-transformed signals are compressed. We use a widely known wavelet-based compression scheme, that is,Set Partitioning in Hierarchical Trees (SPIHT) [21]. The underlying idea is set partitioning: sets of samples are recursively split, guided by a series of threshold tests. This approach is particularly well suited for wavelet-transformed data, as wavelet coefficients are naturally clustered. In SPIHT the sample sets are non-overlapping, and they are organized by means of a tree each set is rooted in a subset of low-frequency coefficients, and branches successively to subsets of high-frequency coefficients in the same orientation (see  Figure 3). The search for coefficients associated with a particular threshold usually starts at the root node and proceeds successively towards the leaves of the tree, until all significant coefficients are listed. Such tree-based search, starting at coarse resolution at the root and ending with the finest resolution at the leaves, results in output signals of increasing quality and resolution.Figure 3
Wavelet decomposition of the 2D matrix and associated tree-based set originating from the low-frequency band. The root node (black) branches towards horizontal, vertical, and diagonal higher-frequency bands (H, V, D).The integer wavelet transform, in conjunction with SPIHT, yields a quality and resolution scalable bitstream: the quality and resolution of the signal improve as bitstream progresses. This is a very desirable property for real-time applications. Moreover, the output bitstream is embedded: the bitstream can be truncated at any point to approximately reconstruct the signal. When the bitstream is fully decoded, we obtain a lossless representation.Though this coding scheme is specifically developed for images, it can be applied to all data sources with decaying spectrum [22].


## 3.2.4. Three SPIHT Compression Algorithms

The three compression algorithms are depicted in  Figure2: (1) 1D SPIHT compression, where the EEG is arranged as a vector (Figure 2(a)), (2) 2D SPIHT compression, where the EEG is arranged as a matrix (Figure 2(b)), and (3) 2D SPIHT compression (at optimal rate Ro), followed by arithmetic coding for the residuals (Figure 2(c)). In the 1D SPIHT compression scheme, backward differentiated EEG is subjected to integer wavelet transformation followed by SPIHT coding. The 2D SPIHT compression scheme arranges the EEG as a matrix instead of a vector. In the two-stage 2D SPIHT compression scheme, arithmetic coding is applied to the residuals of 2D SPIHT compression: first SPIHT encodes the wavelet coefficients till the source loses its memory and behaves as independent and identically distributed (corresponding to the optimal bit-rate Ro); next the residuals are encoded by means of single-context arithmetic coding.


## 4. EEG Datasets

### 4.1. Dataset 1: MCI  versus  Control

The first EEG data set has been analyzed in previous studies concerning early diagnosis of AD [23–27].Ag/AgCl electrodes (disks of diameter 8 mm) were placed on 21 sites according to 10–20 international system, with the reference electrode on the right earlobe. EEG was recorded with Biotop 6R12 (NEC San-ei, Tokyo, Japan) at a sampling rate of 200 Hz, with analog bandpass filtering in the frequency range 0.5–250 Hz and online digital bandpass filtering between 4 and 30 Hz, using a third-order Butterworth filter. We used a common reference for the data analysis (right earlobe) and did not consider other reference schemes (e.g., average or bipolar references).The subjects comprise two study groups. The first consists of 25 patients who had complained of memory problems. These subjects were diagnosed as suffering from mild cognitive impairment (MCI) when the EEG recordings were carried out. Later on, they all developed mild AD, which was verified through autopsy. The criteria for inclusion into the MCI group were a mini-mental state exam (MMSE) score = 24, though the average score in the MCI group was 26 (SD of 1.8). The other group is a control set consisting of 56 age-matched, healthy subjects who had no memory or other cognitive impairments. The average MMSE of this control group is 28.5 (SD of 1.6). The ages of the two groups are 71.9 ± 10.2 and 71.7 ± 8.3, respectively. Finally, it should be noted that the MMSE scores of the MCI subjects studied here are quite high compared to a number of other studies. For example, in [28] the inclusion criterion was MMSE = 20, with a mean value of 23.7, while in [29], the criterion was MMSE = 22 (the mean value was not provided); thus, the disparity in cognitive ability between the MCI and control subjects is comparatively small, making the classification task relatively difficult.


### 4.2. Dataset 2: Mild AD versus Control

The second EEG data set also has been analyzed in previous studies [30, 31]; these data were obtained using a strict protocol from Derriford Hospital, Plymouth, UK, and had been collected using normal hospital practices [31]. EEGs were recorded during a resting period with various states: awake, drowsy, alert, and resting states with eyes closed and open. All recording sessions and experiments proceeded after obtaining the informed consent of the subjects or the caregivers and were approved by local institutional ethics committees. EEG dataset is composed of 24 healthy control subjects (age: 69.4 ± 11.5 years old; 10 males) and 17 patients with mild AD (age: 77.6 ± 10.0 years old; 9 males). The patient group underwent full battery of cognitive tests (Mini-Mental State Examination, Rey Auditory Verbal Learning Test, Benton Visual Retention Test, and memory recall tests). The EEG time series were recorded using 19 electrodes positioned according to Maudsley system, similar to the 10–20 international system, at a sampling frequency of 128 Hz. EEGs were bandpass filtered with digital third-order Butterworth filter (forward and reverse filtering) between 0.5 and 30 Hz.


### 4.3. Recording Conditions Common to Both Datasets

In both datasets, all recording sessions were conducted with the subjects in an awake but resting state with eyes closed, and the length of the EEG recording was about 5 minutes, for each subject. The EEG technicians prevented the subjects from falling asleep (vigilance control). After recording, the EEG data has been carefully inspected. Indeed, EEG recordings are prone to a variety of artifacts, for example, due to electronic smog, head movements, and muscular activity. For each patient, an EEG expert selected one segment of 20 s artifact-free EEG by visual inspection, blinded from the results of the present study. Only those subjects were retained in the analysis whose EEG recordings contained at least 20 s of artifact-free data. Based on this requirement, the number of subjects of EEG Dataset 1 was further reduced to 22 MCI patients and 38 control subjects; in EEG Dataset 2 no such reduction was required. From each subject in the two datasets, one artifact-free EEG segment of 20 s was analyzed.


## 4.1. Dataset 1: MCI  versus  Control

The first EEG data set has been analyzed in previous studies concerning early diagnosis of AD [23–27].Ag/AgCl electrodes (disks of diameter 8 mm) were placed on 21 sites according to 10–20 international system, with the reference electrode on the right earlobe. EEG was recorded with Biotop 6R12 (NEC San-ei, Tokyo, Japan) at a sampling rate of 200 Hz, with analog bandpass filtering in the frequency range 0.5–250 Hz and online digital bandpass filtering between 4 and 30 Hz, using a third-order Butterworth filter. We used a common reference for the data analysis (right earlobe) and did not consider other reference schemes (e.g., average or bipolar references).The subjects comprise two study groups. The first consists of 25 patients who had complained of memory problems. These subjects were diagnosed as suffering from mild cognitive impairment (MCI) when the EEG recordings were carried out. Later on, they all developed mild AD, which was verified through autopsy. The criteria for inclusion into the MCI group were a mini-mental state exam (MMSE) score = 24, though the average score in the MCI group was 26 (SD of 1.8). The other group is a control set consisting of 56 age-matched, healthy subjects who had no memory or other cognitive impairments. The average MMSE of this control group is 28.5 (SD of 1.6). The ages of the two groups are 71.9 ± 10.2 and 71.7 ± 8.3, respectively. Finally, it should be noted that the MMSE scores of the MCI subjects studied here are quite high compared to a number of other studies. For example, in [28] the inclusion criterion was MMSE = 20, with a mean value of 23.7, while in [29], the criterion was MMSE = 22 (the mean value was not provided); thus, the disparity in cognitive ability between the MCI and control subjects is comparatively small, making the classification task relatively difficult.


## 4.2. Dataset 2: Mild AD versus Control

The second EEG data set also has been analyzed in previous studies [30, 31]; these data were obtained using a strict protocol from Derriford Hospital, Plymouth, UK, and had been collected using normal hospital practices [31]. EEGs were recorded during a resting period with various states: awake, drowsy, alert, and resting states with eyes closed and open. All recording sessions and experiments proceeded after obtaining the informed consent of the subjects or the caregivers and were approved by local institutional ethics committees. EEG dataset is composed of 24 healthy control subjects (age: 69.4 ± 11.5 years old; 10 males) and 17 patients with mild AD (age: 77.6 ± 10.0 years old; 9 males). The patient group underwent full battery of cognitive tests (Mini-Mental State Examination, Rey Auditory Verbal Learning Test, Benton Visual Retention Test, and memory recall tests). The EEG time series were recorded using 19 electrodes positioned according to Maudsley system, similar to the 10–20 international system, at a sampling frequency of 128 Hz. EEGs were bandpass filtered with digital third-order Butterworth filter (forward and reverse filtering) between 0.5 and 30 Hz.


## 4.3. Recording Conditions Common to Both Datasets

In both datasets, all recording sessions were conducted with the subjects in an awake but resting state with eyes closed, and the length of the EEG recording was about 5 minutes, for each subject. The EEG technicians prevented the subjects from falling asleep (vigilance control). After recording, the EEG data has been carefully inspected. Indeed, EEG recordings are prone to a variety of artifacts, for example, due to electronic smog, head movements, and muscular activity. For each patient, an EEG expert selected one segment of 20 s artifact-free EEG by visual inspection, blinded from the results of the present study. Only those subjects were retained in the analysis whose EEG recordings contained at least 20 s of artifact-free data. Based on this requirement, the number of subjects of EEG Dataset 1 was further reduced to 22 MCI patients and 38 control subjects; in EEG Dataset 2 no such reduction was required. From each subject in the two datasets, one artifact-free EEG segment of 20 s was analyzed.


## 5. Results and Discussion

We compute relative power, compression ratios, and LZ complexity for the EEG signals of all subjects. More specifically, we calculate those measures for all individual EEG channels, and then the measures are averaged over all channels; this results in average measures for all subjects. Our results are summarized in  Tables2 and 3 and Figures 6 and 7. In the analysis we also include two measures of EEG synchrony: stochastic event synchrony (ρ) [32, 33] and a Granger causality measure, that is, full frequency directed transfer function (ffDTF) [34]; in an earlier hat study we observed that those two measures indicated statistically significant differences between MCI/MiAD and age-matched control subjects, for the datasets described in Section 4 [26, 27, 30, 31]. Since the two datasets (MCI and MiAD) were obtained through different recording systems and at different hospitals, a direct comparison of the results obtained from MCI with those from mild AD is not straightforward.Table 2
Mean and standard deviation values of compression ratio, LZ complexity, relative power, and synchrony measures. Sensitivity of the measures in discriminating between MCI and mild AD is given in last column. UncorrectedP values from Mann-Whitney test, where * and ** indicate P<.05 and P<.005, respectively; † Indicates P values that remain significant after postcorrection (Bonferroni, P<.05).
MCI  versus controlMeasureControlMCIP value1D SPIHT CR1.34±0.041.35±0.03.30772D SPIHT CR1.36±0.041.37±0.03.37782D SPIHT+AC1.36±0.041.37±0.03.4477LZ complexity0.65±0.070.62±0.09.0830ρ0.25±0.070.36±0.10.00044**†ffDTF0.05±0.0030.051±0.003.0012**†delta0.20±0.060.21±0.06.2934theta0.08±0.030.12±0.04.0001**†alpha-10.07±0.030.08±0.03.1698alpha-20.05±0.020.05±0.02.9939beta0.24±0.050.21±0.03.0116
*Mild AD versus controlMeasureControlMild ADP value1D SPIHT CR1.09±0.011.12±0.043.45×10-5**†2D SPIHT CR1.11±0.021.15±0.046.09×10-5**†2D SPIHT+AC1.07±0.021.11±0.044.86×10-5**†LZ complexity0.63±0.060.55±0.08.0024**†ρ0.46±0.040.49±0.03.0024**†ffDTF0.04±0.0040.037±0.009.0001**†delta0.001±0.0040.017±0.01.0029**†theta0.17±0.080.54±0.168×10-7**†alpha-10.32±0.120.18±0.10.0009**†alpha-20.17±0.110.06±0.023.41×10-6**†beta0.33±0.140.18±0.11.0006**†Table 3
Classification rates for discriminant analysis (DA) of the lossless compression ratios, LZ complexity and relative power in theta band.
MCI versus controlMeasureLinear DAQuadratic DASVMtheta76.67%76.67%76.67%ffDTF63.33%71.67%78.33%ρ75%75%76.67%ffDTF +ρ76.67%83.33%80.00%Theta +ρ78.33%83.33%80.00%Mild AD versus controlMeasureLinear DAQuadratic DASVM1D SPIHT CR80.49%80.49%80.49%2D SPIHT CR82.93%82.93%85.37%2D SPIHT+AC CR75.61%80.49%82.93%LZ complexity68.29%68.29%68.29%theta95.12%95.12%95.12%ffDTF58.54%78.05%82.93%ρ56.10%63.41%63.41%ffDTF +ρ65.85%70.73%78.05%theta + ffDTF95.12%92.68%95.12%theta + ffDTF +95.12%92.68%97.56%1D SPIHT CRIn  Table2 we list statistics of the average measures, including the average computed across the entire subject groups and the standard deviation. We apply the Mann-Whitney test for the average measures between MCI and the reference subjects (Dataset 1) and MiAD and reference subjects (Dataset 2). The Mann-Whitney test allows us to investigate whether the statistics at hand (EEG measures) take different values between two subject populations. Low P values indicate large difference in the medians of the two populations. The resulting P values are listed in  Table 2. Since we conduct multiple statistical tests simultaneously, we need to apply statistical postcorrection. We adopt Bonferroni postcorrection [35] and multiply the P values by the number of tests (11). In  Table 2 we indicate which EEG measures remain statistically significant after postcorrection.Theta relative power is significantly larger in MCI patients compared to reference subjects, whereas beta power is significantly smaller. In the MiAD patients the perturbations on EEG relative power are stronger: delta and theta relative power is significantly larger than in the reference subjects, whereas alpha and beta power is significantly smaller. In other words, slowing occurs in both the MCI and MiAD patients, which is in agreement with earlier studies (see [11] for a review). The slowing effect can also readily be seen from the (normalized) EEG spectra, shown in  Figures 4 and 5 for Datasets 1 and 2, respectively. The effect of slowing in the MiAD subjects is very clear from  Figure 5: power is obviously more concentrated in theta band in MiAD patients than in the age-matched control subjects. For the MCI patients (see  Figure 4), no such clear effect can be observed from the spectra; this is no surprise, since MCI is a less severe disease state than MiAD. However, one may notice a slight increase (decrease) in theta (beta) relative power in MCI patients. In both the MCI patients and control subjects, power is concentrated in low-frequency bands (delta and theta band) and in high-frequency band (beta band); high-frequency power (beta band) is much smaller in the MiAD patients. In summary, as in earlier studies (see [11] for a review), we observe slowing in MCI and MiAD EEG.Relative power distribution in various frequency bands for all the datasets. (a) Control group. (b) Mild cognitive impaired subjects.
(a)(b)Relative power distribution in various frequency bands for all the datasets. (a) Control group. (b) Mild Alzheimer’s disease subjects.
(a)(b)Correlation between the lossless compression ratios, LZ complexity, relative power in different bands, Granger causality (ffDTF), and stochastic event synchrony (ρ); red and blue indicate strong correlation and anticorrelation, respectively.
(a)
MCI (Dataset 1)(b)
Mild AD (Dataset 2)Pearson correlation test between the lossless compression ratios, LZ complexity, relative power in different bands, Granger causality (ffDTF), and stochastic event synchrony (ρ). The (uncorrected) P values are shown on a logarithmic scale.
(a)
MCI (Dataset 1)(b)
Mild AD (Dataset 2)No significant effect on the complexity and regularity measures can be observed in MCI patients. On the other hand, the regularity measures and complexity measures are significantly larger and smaller, respectively, for MiAD patients than for control subject; in other words, the EEG signals of MiAD patients are significantly less complex than in healthy subjects. This observation is in agreement with several earlier studies (see [11] for a review).We also try to classify patients versus control subjects by means of the most discriminative EEG measures (P<.05). We test those measures individually and jointly for their discriminative ability. Table 3 shows the resulting classification performance with linear and quadratic discriminant analysis and support vector machine, determined through leaving-one-out cross-validation [36]. Only the best performing combinations of EEG measures are listed. From Table 3 we can see that theta band relative power yields good performance when used separately and results in even better performance when combined with the most discriminative lossless compression ratio and synchrony measure. The other relative power measures are less discriminative, for both datasets (not shown here); this observation is in agreement with the P values listed in  Table 3. The compression ratios and LZ complexity fail to discriminate MCI patients from control subjects (not shown here). However, those measures yield good classification performance for the MiAD patients. Interestingly, the lossless compression ratios result in better classification rates than LZ complexity; this may be explained as follows: LZ complexity is based on binary approximations of the continuous EEG signals, whereas the former are derived from accurate representations of the EEG, associated with lossless compression.In order to gain more insight in the relationship between the different measures, we calculate the correlation between those measures (see  Figure6). The correlation coefficient among each pair of measures is calculated as follows:
(2)rij=1Nsubject∑k=1Nsubjectmi(k)-mi¯σimj(k)-mj¯σj,
where mi(k) and mj(k) the average value of EEG measure i and j, respectively, for subject k, the sum is computed over all subjects, and mi¯, mj¯, σi, and σj are the mean and standard deviation of mi and mj, respectively. The resulting correlation coefficients are displayed in  Figure 6, for Dataset 1 and Dataset 2 separately. We also conduct the Pearson correlation test, to verify whether the correlations or anticorrelations are statistically significant. The resulting P values are shown in  Figure 7 (logarithmic scale). Since we have multiple simultaneous tests, statistical postcorrection is required. Again we adopt Bonferroni postcorrection [35] and multiply the P values by the number of tests (55).As expected, the compression measures are significantly mutually correlated as all the schemes are based on the same principle; they are also significantly anticorrelated with LZ complexity in the MiAD dataset (Dataset 2).Interestingly, the compression ratios are significantly correlated with low-frequency relative power (delta and theta; MiAD) and anticorrelated with high-frequency relative power (beta; both datasets). Likewise LZ complexity is strongly anticorrelated with low-frequency relative power (delta and theta; both datasets) and correlated with high-frequency relative power (beta; MiAD). Taken together, this observation strongly suggests that slowing and loss of complexity in AD EEG arenot independent phenomena but are strongly related; to the best of our knowledge, this observation has not been reported before in the literature.Perhaps surprisingly, Granger causality (ffDTF) [34] is significantly correlated with LZ complexity and high-frequency relative power (MiAD) and significantly anticorrelated with lossless compression ratios (MiAD) and low-frequency relative power (both datasets). We believe that this observation has not been documented yet. We conjecture that the observed statistical (anti)correlation between ffDTF and the other measures is an artefact of the multivariate model underlying Granger causality (and ffDTF in particular). More specifically, Granger causality is derived from a multivariate autoregressive model (MVAR). The order of the latter needs to be kept low, since the coefficients of the MVAR need to be inferred from a short EEG segment; high-order MVARs contain many coefficients, which cannot be reliably inferred from the limited amount of data. Low-order MVARs have short memory and cannot capture low-frequency components in the EEG. Consequently Granger causality may underestimate the correlation among brain signals when the EEG contains strong low-frequency components.Stochastic event synchrony (ρ) [32, 33] seems to be uncorrelated with the other measures (both datasets), and therefore, it may provide complementary information.


## 6. Conclusion

In this study, we investigated the use of relative power, LZ complexity, and lossless compression ratio as EEG markers for MCI and mild AD. Lossless compression ratio is shown to be discriminative for mild AD, whereas it is not discriminative for MCI. On the other hand, theta band relative power was observed to be statistically larger in MCI and mild AD patients than in control subjects. Maximum discrimination is obtained by combining the compression ratio, relative power, and synchrony measures (Granger causality and/or stochastic event synchrony).We would like to reiterate, however, that the two datasets analyzed (MCI and MiAD) were obtained through different recording systems and at different hospitals; a direct comparison of the results obtained from MCI with those from mild AD is therefore difficult. On the other hand, since the datasets are independent, our observations are probably not dependent on particularities of the recording systems and/or procedures at the hospitals.Interestingly, compression ratios were found to be significantly correlated to delta and theta band relative power, showing their strong correlation with relative power at low frequencies; also strong anti-correlation between compression ratios and beta relative power was observed. Therefore, slowing and loss of complexity in the EEG of MCI and MiAD patients may be strongly related phenomena.More generally, this study also underlines the importance of analyzing MCI and AD EEG by means of a variety of statistical measures (relative power, complexity/regularity measures, synchrony measures), in order to detect potential correlations between various observed phenomena associated with MCI and AD.



---

*Source: 539621-2011-04-13.xml*