Published: 30 September 2014

Detecting phase synchronization in coupled oscillators by combining multivariate singular spectrum analysis and fast factorization of structured matrices

Kazimieras Pukenas1
1Lithuanian Sports University, Kaunas, Lithuania
Views 104
Reads 50
Downloads 1144

Abstract

It is shown that a fast reliable block Fourier algorithm for the factorization of structured matrices improves computational efficiency of known method for detecting phase synchronization in a large system of coupled oscillators, based on multivariate singular spectrum analysis. In this paper, a novel algorithm for the detection of cluster synchronization in a system of coupled oscillators is proposed. The block Toeplitz covariance matrix of the total trajectory matrix is efficiently block-diagonalized by means of the Fast Fourier Transform by embedding it first into a block circulant matrix. The synchronization structure of the underlying multivariate data set is defined based on the 2D spatiotemporal eigenvalue spectrum. The benefits of the proposed method are illustrated by simulations of the phase synchronization effects in a chain of coupled chaotic Rössler oscillators and using multichannel electroencephalogram (EEG) recordings from epilepsy patients.

1. Introduction

During the past two decades, singular spectrum analysis (SSA) and multivariate SSA (M-SSA) have proven their usefulness in the temporal and spatiotemporal analysis of short and noisy time series in several fields of geosciences [1, 2], biomedical sciences [3, 4] and other disciplines [5]. M-SSA, which is a natural extension of SSA and which relies on a classical Karhunen-Loeve spectral decomposition of a stochastic process, provides insight into the unknown or partially known dynamics of the underlying system by decomposing the delay-coordinate phase space of a given multivariate time series into a set of data-adaptive orthonormal components. As a robust means of analyzing the spatiotemporal behaviour of short and noisy time series, it has been applied for the identification of oscillatory modes and helps greatly in the study of phase synchronization in a large system of coupled oscillators, in the presence of high observational noise levels [6]. Groth and Ghil [6] have proven that M-SSA can automatically identify multiple oscillatory modes and detect whether these modes are shared by clusters of phase- and frequency-locked oscillators. To achieve the full potential of M-SSA in this respect, the authors have solved the problem of degenerate eigenvectors by introducing a modified variance-maximization (varimax) rotation of the M-SSA eigenvectors. However, M-SSA operates on a covariance matrix, which is computed from the full augmented trajectory matrix. The size of this matrix is equal to the product of the number of channels and the embedding dimension of the reconstructed phase space. In some cases this covariance matrix can be huge, and as a result, M-SSA becomes computationally expensive [3], especially in a moving-window analysis of non-stationary data. Because a properly constructed covariance matrix has a block Toeplitz approximation and can be embedded into a block-circulant matrix of double size, this difficulty can be overcome using a Fourier transformed factorization of the block-circulant matrix [7-11] to accelerate the singular value decomposition (SVD) procedure and to gain computational efficiency when solving these systems. In accordance with this approach, a fully diagonalized representation of the covariance matrix is derived in two consecutive steps: (1) block-diagonalization by exploiting the block Toeplitz structure of the matrix (temporal decoupling) and (2) full-diagonalization by applying a unitary transform (spatial decoupling). In the present paper, it is shown that a 2D matrix of eigenvalues explores the spatiotemporal structure of the underlying multivariate dataset and that the oscillatory modes can be identified based on the eigenvalues of the spatial dimension of the dominant temporal component. Our simulation results show that for the analysis of the phase synchronization, the block-Fourier method has much less computational complexity, but adequate simulation accuracy, similar to that of the classical M-SSA method.

2. Preliminaries

Let x=xdn:d=1,,D,n=1,,N be a multivariate time series with D channels of length N. It is assumed that each channel has been centred and normalized. Each channel can be transformed to an M-dimensional phase space by selecting the embedding dimension M and time delay τ. Each phase point in the phase space is thus defined by [12]:

1
xdn=xdn,xdn+τ,,xdn+M-1τT,

where n=1,2,,N-M-1τ, and T denotes the transpose of a real matrix. At τ=1, the reconstructed phase space matrix Xd with M rows and L=N-M+1 columns (called a trajectory matrix) is defined by:

2
Xd=xd(1)xdN-M+1xdMxdN,

and encompasses M delayed versions of each channel. The total trajectory matrix of the set X will be a concatenation of the component trajectory matrices Xd computed for each channel, i.e., X=X1,X2,,XDT. This full augmented trajectory matrix, which has DM rows of length L=N-M+1 can be used for M-SSA [1, 2, 6]. However, as mentioned above, the eigen decomposition of a large DM×DM covariance matrix R=1/LXXT in a moving-window analysis of non-stationary data becomes computationally expensive.

3. Spatio-temporal decoupling

The covariance matrix R=1/LXXT can be rewritten as a block matrix:

3
R=R11R12R1DR21R22R2DRD1RD2RDD,

with cross-covariance matrix M×M for all pairs of trajectory matrix Xd in blocks, i.e., Rij=1/LXiXjT, i=1,,D, j=1,,D. For LMτ, the matrices Rij are the M×M Toeplitz (but not symmetric for ij) matrices. The main diagonal of Rij contains the estimate of the zero-lag covariance of channels i and j. The diagonals in the lower left triangle of Rij contain the lag covariance of channels i and j, with j leading i, while the diagonals in the upper right triangle contain the covariances with i leading j [2]. Define the DM×DM permutation operator PD,M [13] such that vec AD×M=PD,Mvec AT for D×M matrix A, where vec A denotes the vectorized form of A (concatenation of columns of A into a column vector). In essence, permutation operator PD,M is the identity matrix with reordered rows. Then the following holds [14]:

4
R^=PD,MRPD,MT,

where R^ is the following block Toeplitz matrix:

5
R^=T11T12T1,M-1T1MT21T11T1,M-2T1,M-1TM-1,1TM-2,1T11T12TM1TM-1,1T21T11.

Note that the D×D matrix Tp,q is no longer a Toeplitz matrix, and nor is R^ symmetric. The block Toeplitz covariance matrix R^ can also be obtained simply by rearranging the total trajectory matrix X, such that the delayed versions of all D channels follow one another, i.e., X=XD1,XD2,,XDMT. The M×M (blocks) block Toeplitz matrix can be embedded into a 2M×2M block circulant matrix G^ of double size [8, 10], of which the upper-left quarter submatrix is the unmodified block Toeplitz matrix R^ and the first block column is given by T11 T21 TM-1,1 TM1 0 T1M T1,M-1 T12T. As a first step (temporal decoupling) towards the desired diagonalization, the resulting block matrix of eigenvalues can be calculated by applying the block Fourier transform to the first block column of G^, i.e, [10]:

6
S1S2S2M=F2MIDT11T21T12,

where F2M is a 2M×2M discrete Fourier transform (DFT) matrix with ω=exp-2πi/n, n=2M:

7
F2M=1n11111ω1ω2ωn-11ω2ω4ω2n-11ωn-1ω2n-1ωn-1n-1,

ID is the identity matrix of size D and denotes the Kronecker product. Due to their interpretation as power spectral densities, the elements of Sk, k=1,, 2M exhibit the specific symmetry property i.e. sk,sr is conjugate with sk,rs. Spatial decoupling is achieved upon SVD of the spectrum Sk at each frequency bin k=1, , 2M [8, 10]:

8
Sk=VkΛkVkH,

where Vk denotes a D×D unitary matrix composed from the singular vectors of Sk and matrix Λk denotes a diagonal matrix constructed from the singular values λj,k of Sk:

9
Λk=diagλ1,k, λ2,k, , λD,k.

Composed from the spatio-temporal eigenvalues λj,k, j=1, , D, k=1, , 2M a two-dimensional D×2M matrix reflects the spatiotemporal relationships in a multivariate time series. As the calculated eigenvalue spectrum is symmetric, the single-sided format for further analysis is used, i.e., as a D×M matrix. We suppose that the frequency mismatch between channels is low. Therefore, at reasonable FFT length (which is equal to double the embedding dimension in our case and chosen to be the power of two in order to use the FFT of radix 2), the dominant eigenvalues in the temporal direction fall within the same frequency bin. Thus, we need only the eigenvalue spectrum D×1 in the spatial direction at the dominant frequency in the temporal direction for phase synchronization analysis. When dealing with broadband signals (e.g., biosignals) the summation of eigenvalue spectrum over all frequencies must be performed. To obtain sharp and robust results in the phase synchronization analysis and to follow the recommendations of [6], we perform a classical varimax rotation (Matlab routine rotatefactors) of the Vk eigenvectors, where index k denotes the dominant frequency. Prior to varimax, each eigenvector vj,k is multiplied by the appropriate singular value λj,k1/2 in order to stabilize the rotation results. After the varimax rotation, the diagonal matrix of the eigenvalue spectrum is defined by:

10
Λk*=TTΛkT,

where T is the rotation matrix and the diagonal elements λk* are called the modified variances [6].

4. Simulation results

We consider a chain of diffusively coupled Rössler oscillators [6, 15]:

11
x˙j=-ωjyj-zj,
y˙j=ωjxj+αyj+cyj+1-2yj+yj-1,
z˙j=0.1+zjxj-8.5.

The position in the chain is given by the index j=1, , J; ωj=ω1+0.02j-1 are the associated natural frequencies, with ω1=1, and we assume free boundary conditions x0n=x1n and xJ+1n=xJn. The frequency mismatch Δjkω between oscillators j and k is given by Δjkω=0.02j-k. The parameter α=0.15 and c0 is the coupling strength. We consider a chain of J=8 Rössler oscillators and generate a time series using the ODE45 integrator of Matlab. The solution is sampled at time intervals t=0.1 and the observed time series x has D=3J=24 channels of length N=2500. The first 200 transient samples are discarded. The embedding dimension M=64 is chosen in order to cover more than one oscillation period (about 40 data points) and in order to use the FFT of radix 2. All data processing and analyses were performed using Matlab software (The MathWorks, Natick, MA).

M-SSA is able to provide considerable insight into the mechanisms of rhythm adjustment on the road to phase synchronization [6]. When the frequency mismatch in the model equations is sufficiently large, it is known that the transition in the observed mismatch is no longer smooth as coupling strength c increases and instead, it occurs in abrupt jumps. The oscillators form clusters within which the observed frequency is the same but the differences between these common cluster frequencies are even larger. As c increases further, the number of clusters decreases and the successive clustering of oscillators is also reflected in a decreasing number of significant eigenvalues λk*. Fig. 1(a) shows the modified variances λk* calculated by the proposed algorithm for noiseless signals and Fig. 1(b) – for noisy signals, contaminated by additive zero-mean white Gaussian noise at a signal-to-noise ratio (SNR) –10 dB. For comparison, Fig. 1(c) shows variances λk* calculated by the M-SSA algorithm with modified varimax rotation of the M-SSA eigenvectors [6].

The distribution of λk* in Fig. 1(a) and 1(b) reflects the transition to phase synchronization with sharp jumps at the bifurcation points. As can be seen, the algorithm provides a robust reconstruction of oscillatory behavior; visually the results for the noiseless case largely coincide with the results for the noise-perturbed case. The most important thing is that the results of the proposed algorithm coincide with the results of M-SSA algorithm based on the modified varimax rotation of the eigenvectors (Fig. 1(c)). However, in contrast to the M-SSA algorithm, each line in the spectrum of λk* consists now of single values rather than the superposition of two practically identical values – referred to as an oscillatory pair – and thus, represents one oscillatory mode. This is because we use a one-sided Fourier spectrum. Fig. 2(a) shows the ability of the proposed algorithm to identify correctly the distinct oscillatory modes.

Fig. 1Synchronization for a chain of J=8 coupled Rössler oscillators: (a) modified variances λk* from the noiseless case; (b) modified variances λk* of the noise-perturbed case – at SNR = –10 dB; (c) modified variances λk* from the noiseless case, calculated by classical M-SSA algorithm with varimax rotation of the M-SSA eigenvectors

Synchronization for a chain of J=8 coupled Rössler oscillators:  (a) modified variances λk* from the noiseless case; (b) modified variances λk* of the noise-perturbed case – at SNR = –10 dB; (c) modified variances λk* from the noiseless case, calculated by classical M-SSA algorithm with varimax rotation of the M-SSA eigenvectors

a)

Synchronization for a chain of J=8 coupled Rössler oscillators:  (a) modified variances λk* from the noiseless case; (b) modified variances λk* of the noise-perturbed case – at SNR = –10 dB; (c) modified variances λk* from the noiseless case, calculated by classical M-SSA algorithm with varimax rotation of the M-SSA eigenvectors

b)

Synchronization for a chain of J=8 coupled Rössler oscillators:  (a) modified variances λk* from the noiseless case; (b) modified variances λk* of the noise-perturbed case – at SNR = –10 dB; (c) modified variances λk* from the noiseless case, calculated by classical M-SSA algorithm with varimax rotation of the M-SSA eigenvectors

c)

Fig. 2Eigenvalue spectrum for eight uncoupled and detuned Rössler oscillators with c=0 in Eq. (11) and contaminated by the Gaussian noise at SNR = –10 dB: (a) modified variances λk*, calculated by proposed algorithm; (b) modified variances λk*, calculated by classical M-SSA algorithm with varimax rotation of the M-SSA eigenvectors

Eigenvalue spectrum for eight uncoupled and detuned Rössler oscillators with c=0 in Eq. (11) and contaminated by the Gaussian noise at SNR = –10 dB: (a) modified variances λk*, calculated by proposed algorithm; (b) modified variances λk*, calculated by classical M-SSA algorithm with varimax rotation of the M-SSA eigenvectors

a)

Eigenvalue spectrum for eight uncoupled and detuned Rössler oscillators with c=0 in Eq. (11) and contaminated by the Gaussian noise at SNR = –10 dB: (a) modified variances λk*, calculated by proposed algorithm; (b) modified variances λk*, calculated by classical M-SSA algorithm with varimax rotation of the M-SSA eigenvectors

b)

Eight uncoupled and detuned Rössler oscillators with c=0, were contaminated by additive zero-mean white Gaussian noise at SNR = –10 dB and ten repeated trials were performed. The leading eight modified variances λk* are clearly significant. Thus, the modified variances λk* spectrum indicates that the algorithm, based on SVD of a block-circulant covariance matrix, has identified correctly the eight uncoupled oscillators in Eq. (11) in a manner analogous to the classical M-SSA algorithm based on modified varimax rotation of the eigenvectors (Fig. 2(b)). However, as the remarks above show, for M-SSA, the leading 16 eigenvalues are clearly significant; M-SSA has identified correctly the 8 uncoupled oscillators and each is described by an oscillatory pair.

To demonstrate the performance of the proposed algorithm in detecting globally changing of the synchronization structure in an experimental data set, we have applied the algorithm to multi-channel EEG recordings from epilepsy patients. The EEG data are taken from the CHB-MIT Scalp EEG Database (http://www.physionet.org/physiobank/database/chbmit/). We analyzed 23 contacts of 1-minute raw (non-filtered) scalp EEG recordings (from record, numbered chb01/chb01_04.edf). It is known that during epileptic seizures EEG time series displays oscillations of comparatively large amplitude and well defined frequency [18]. Fig. 3 shows the eigenvalue spectrum for EEG time series for interictal and ictal states. We can clearly see that for ictal state the distribution of the eigenvalue spectrum tends to concentrate on a narrow range indicating to increase in synchrony.

Fig. 3Eigenvalue spectrum for multi-channel EEG data from epilepsy patients

Eigenvalue spectrum for multi-channel EEG data from epilepsy patients

Application of high performance algorithms [16, 17] based on circulant embedding and the FFT for block Toeplitz matrices contribute to a significant reduction in the computational costs of the M-SSA. In the present simulations, the ratio of the process time (CPU time) between proposed algorithm based on SVD of a block-circulant system matrix and conventional M-SSA was approximately 1:12.

5. Conclusions

A simulation involving a chain of locally coupled chaotic Rössler oscillators shows that in the classical case of phase and frequency locking of spiral chaotic systems, the M-SSA approach, based on fast algorithms that exploit the structure of Toeplitz-like matrices, preserves reliable and consistent information about the synchronization mechanism and contributes to a significant reduction in computational costs. As a real world application we demonstrated the performance of the proposed algorithm in detecting globally changing of the synchronization structure using clinical EEG dataset. In accordance with this approach, the computationally intensive task of decomposing a large DM×DM covariance matrix, obtained from a full augmented trajectory matrix, can be replaced by two consecutive and less computationally intensive steps: (1) block-diagonalization (using a Fourier transformed factorization) by exploiting the block Toeplitz/circulant structure of a covariance matrix and (2) full-diagonalization by applying SVD procedures on the 2M smaller D×D matrices. The resulting D×2M matrix of eigenvalues explores the spatiotemporal structure of the underlying multivariate dataset, i.e., it defines the dominant 2M temporal components across D dominant spatial components and thus, the oscillatory modes can be identified based on the D×1 eigenvalues of the spatial dimension at the dominant temporal component (or across all temporal components for broadband signals). Furthermore, the eigenvalues are corrected by applying variance-maximization (varimax) rotation to the eigenvectors of the dominant D×D temporal component (frequency bin).

References

  • Plaut G., Vautard R. Spells of low-frequency oscillations and weather regimes in the northern hemisphere. Journal of the Atmospheric Sciences, Vol. 51, Issue 2, 1994, p. 210-236.
  • Ghil M., Allen M. R., Dettinger M. D., Ide K., Kondrashov D., Mann M. E., et al. Advanced spectral methods for climatic time series. Reviews of Geophysics, Vol. 40, 2002, p. 1-41.
  • Ghaderi F., Mohseni H. R., and Sanei S. Localizing heart sounds in respiratory signals using singular spectrum analysis. IEEE Transactions on Biomedical Engineering, Vol. 58, Issue 12, 2011, p. 3360-3367.
  • Sanei S., Lee T. K. M., Abolghasemi V. A new adaptive line enhancer based on singular spectrum analysis. IEEE Transactions on Biomedical Engineering, Vol. 59, Issue 2, 2012, p. 428-434.
  • Golyandina N., Korobeynikov A., Shlemov A., Usevich K. Multivariate and 2D Extensions of Singular Spectrum Analysis with the Rssa Package, 2013, p. 1-74.
  • Groth A., Ghil M. Multivariate singular spectrum analysis and the road to phase synchronization. Physical Review E, Vol. 84, 2011, p. 036206-1-036206-10.
  • Turnes C. K., Balcan D., Romberg J. Superfast Tikhonov regularization of Toeplitz systems. IEEE Transactions on Signal Processing, Vol. 62, Issue 15, 2014, p. 3809-3821.
  • Acolatse K., Abdi A. Efficient simulation of space-time correlated MIMO mobile fading channels. In Proceedings, IEEE Vehicle Technology Conference, 2003, p. 652-656.
  • Leroux J.-D., Selivanov V., Fontaine R., Lecomte R. Fast 3D image reconstruction method based on SVD decomposition of a block-circulant system matrix. IEEE Nuclear Science Symposium Conference Record, 2007, p. 3038-3045.
  • Omar S.-M., Slock D. T. M. Singular block Toeplitz matrix approximation and application to multi-microphone speech dereverberation. In Proceedings of IEEE International Workshop Multimedia Signal Processing, 2008, p. 52-57.
  • Pukenas K. Algorithm for the characterization of the cross-correlation structure in multivariate time series. Circuits, Systems, and Signal Processing, Vol. 33, 2014, p. 1289-1297.
  • Broomhead D. S., King G. P. Extracting qualitative dynamics from experimental data. Physica D, Vol. 20, Issue 2-3, 1986, p. 217-236.
  • Henderson H. V., Searle S. R. The vec-permutation matrix, the vec operator and Kronecker products: A review. Linear and Multilinear Algebra, Vol. 9, Issue 4, 1981, p. 271-288.
  • Gazzah H., Regalia P. A., Delmas J.-P. Asymptotic eigenvalue distribution of block Toeplitz matrices and application to blind SIMO channel identification. IEEE Transactions on Information Theory, Vol. 47, Issue 3, 2001, p. 1243-1251.
  • Osipov G. V., Pikovsky A. S., Rosenblum M. G., Kurths J. Phase synchronization effects in a lattice of nonidentical Roessler oscillators. Physical Review E, Vol. 55, 1997, p. 2353-2631.
  • Alonso P., Badia J. M, Vidal A. M. An efficient parallel algorithm to solve block–Toeplitz Systems. The Journal of Supercomputing, Vol. 32, Issue 3, 2005, p. 251-278.
  • Chan R. H., Ng M. K. Conjugate gradient methods for Toeplitz systems. Society for Industrial and Applied Mathematics Review, Vol. 38, Issue 3, 1996, p. 427-482.
  • Müller M., Baier G. Detection and characterization of changes of the correlation structure in multivariate time series. Physical Review E, Vol. 71, 2005, p. 046116-1-046116-16.

About this article

Received
08 July 2014
Accepted
10 September 2014
Published
30 September 2014
Keywords
phase space
multivariate singular spectrum analysis
eigenvalue spectrum
block Toeplitz matrix
block circulant matrix
fast Fourier transform