# Topology Identification of Coupling Map Lattice under Sparsity Condition

Authors: Jiangni Yu; Lixiang Li; Yixian Yang
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Coupling map lattice is an efficient mathematical model for studying complex systems. This paper studies the topology identification of coupled map lattice (CML) under the sparsity condition. We convert the identification problem into the problem of solving the underdetermined linear equations. Thel1 norm method is used to solve the underdetermined equations. The requirement of data characters and sampling times are discussed in detail. We find that the high entropy and small coupling coefficient data are suitable for the identification. When the measurement time is more than 2.86 times sparsity, the accuracy of identification can reach an acceptable level. And when the measurement time reaches 4 times sparsity, we can receive a fairly good accuracy.


---

## Body

## 1. Introduction

The coupled map lattice with nonlocally coupling chaotic characteristic is widely observed and highly involved in many fields, which ranges from complex network [1–3] to neural network, from biological system to ecological system, and from physics to computer science [4–6]. Driven by some practical applications which benefit from the better controlling of CML, a great deal of current research of CML has focused on dynamical analysis, control, and modeling. However, the behavior of CML is largely influenced by the topology of the network which generally is invisible to us. Thus, its identification usually becomes the promise of application.Up to now, various researches focus on identifying the patterns of coupled map lattice models [7, 8], such as the study of the formation and evolution of spatiotemporal patterns based on a reference model [7], and the identification of CML based on the wavelet [8]. However, few researches have discussed the topology identification of CML. There are two problems of topology identification: how we should get the result with less measurement time (M) and what precondition the measured data need.In this paper, as CML is discrete, for the facilitation of identification, we transform the CML equation so that the identification problem can be converted into a problem of solving the linear equationy=Φx. The l1 method is introduced to solve the topology identification of CML. In the process of identification, the relationship between the measurement time (M) and the sparsity (S) of x is taken into consideration. In the experiment, through the analysis of entropy, we discuss the coupling coefficient and the solvability of the equation y=Φx. We find that smaller coupling coefficient benefits the identification. Through further research, we study the influence of the measurement time on the identification precision; that is, when the measurement time M≥2.86S, we can achieve a decent identification result, and when M≥4S, the identification result is very good.


## 2. Analysis of Identification Process

Considering a CML withN elements is as follows: (1)zt+1i=1-εfzti+ε2W∑j=1W‍cijFit,j,where zt(i) is the state of each node, i=1,2,…,N, and t is the discrete time step. ε∈(0,1) is the strength of the coupling. f(z)=4z(1-z) is the standard form of logistic nonlinear function. Also Fi(t,j)=f(zt(i-j))+f(zt(i+j)), where j=1,2,…,W. cij∈RN×(2×W+1) is the weighted topology connection from element i to its neighbor elements i-j and i+j, and the weighted topology connection obeys the periodic boundary condition. The schematic diagram is shown as in Figure 1.Figure 1
Periodic boundary condition of elementi=2 when neighbors W=3.Normally, the weighted topology connections are composed by the known partK and the unknown part X. Our purpose is to identify this unknown part. In order to identify these unknown connections, the dynamical equation (1) can be transformed as the following equation:(2)2Wεzt+1i-1-εfzti=∑j=1W‍cijFit,j.Now, we expand the matrixc∈RN×(2×W+1) to C∈RN×N. In the expanded matrix C, if j>W, Cij=0; if j≤W, Cij=cij. Under these circumstances, (2) can be expressed as (3)2Wεzt+1i-1-εfzti=∑j=1N‍Cij·fztj.We setR(t,i)=(N/ε)(xt+1(i)-(1-ε)f(xt(i))). If we put t=1,2,…,M iterations together, then we get M measurements. Its formula can be expressed as(4)R1,1⋯R1,N⋯RM,1⋯RM,N=f11⋯f1N⋯fM1⋯fMN∗C11⋯CN1⋯C1N⋯CNN.Here,C can be divided into two parts, that is, the known part K and unknown part X, which is C=K+X. Thus, to get the solution X, we have(5)R11⋯R1N⋯RM1⋯RMN-f11⋯f1N⋯fM1⋯fMN∗K=f11⋯f1N⋯fM1⋯fMN∗X.To simplify, the above equation set can be represented as (6)Y=Φ∗X,where Y implies the left side of (5) and Φ implies the left matrix of the right side.Obviously, the elements inY and Φ are decided by ε, W, and the sampled value z. The size of Y and Φ are decided by M and N. Thus, (6) can be expressed as (7)y1,…,yN=Φ∗x1,…,xN,where xi∈RN×1 and yi∈RM×1 are the columns of X and Y, respectively. Without loss of generality, we use x∈RN×1 instead of xi and use y∈RM×1 instead of yi. The equation set finally can be described as (8)y=Φ∗x.Eventually, we transform the topology identification problem into a problem of solving the equation set. The vectorsy and Φ can be computed by the sampled value zt(i) (which is the state value of each element in the tth iteration). The character of solutions x depends on the matrix Φ∈RM×N. When there are at most S unknown connections of each element, which means the nonzero value of x will be less than S, in this case we defined x as S-sparse. In the following section, the influences of Φ and S will be taken into consideration in the identification problem.


## 3. The Analysis ofΦ and U

Normally, whenΦ is full rank, which means Φ is reversible, (5) has a unique solution, which implies that the measurement time M should be larger than the element N. However, when M is smaller than N, the identification of the unknown connections is an interesting problem. On account of the partial unknown connection, namely, x is S-sparse, the solution can be worked out by an underdetermined equation y=Φx when M<N. The solving of y=Φx is related to two aspects: the construction of Φ and the method to work out the solution x.


### 3.1. The Solving Condition forΦ

According to [9], the necessary and sufficient condition for the solution of the underdetermined problem is that, for any vector x sharing the same sparsity s, there exists a δs∈(0,1) such that(9)1-δsx22≤Φx22≤1+δsx22,where δs∈(0,1) implies that the columns of Φ should be linearly independent. The property is generally satisfying the law of random matrix such as i.i.d Gauss and Bernoulli. Recently, owning to the pseudorandom property of chaotic system, the chaos sequence is used for the construction of Φ. It was proved in [10] that when the sampling distance guarantees a certain value, the logistic system satisfies the RIP condition. In [11], a series of chaos systems, such as Lorenz system and Chuan’s circuit, are used to produce Φ. Thus, in the model of this paper, it was promising to identify the unknown connections.


### 3.2. The Solving Process ofx

As illustrated above, the unknown vector isS-sparse; then the resolution problem can be transformed into an optimization problem which is to find the most sparse solution of (8). Thus the l0 norm optimization is taken into consideration. However, to find a x=argmin∥x∥0 to satisfy y=Φx is a NP hard problem that requires an exhaustive enumeration of all C(S,N) possible combinations for the locations of the nonzero entries in x. Then the application of l2 norm optimization is tried, which is to find a x=argmin∥x∥2 to satisfy y=Φx. It is also denied for the lack of precision. After that, l1 norm is considered; it is more efficient than l0 and more precise than l2. The optimization method is expressed as follows: (10)x=argminx1s.t.y=Φx.Thel1 optimization problem can be transformed to a linear programming known as basis pursuit (BP). As [12] illustrated, the matrix Φ can be shown to have the RIP, when the measurement time satisfies the condition as follows: (11)M>cS×logNS,where c is a constant; we can exactly reconstruct S-sparse vector x via the BP method. Plenty of experimental results show that most of S-sparse signals can be worked out when M≥4S [13]. In this paper, we will discuss the relation between M and S in this identification circumstance by experimental analyses.


## 3.1. The Solving Condition forΦ

According to [9], the necessary and sufficient condition for the solution of the underdetermined problem is that, for any vector x sharing the same sparsity s, there exists a δs∈(0,1) such that(9)1-δsx22≤Φx22≤1+δsx22,where δs∈(0,1) implies that the columns of Φ should be linearly independent. The property is generally satisfying the law of random matrix such as i.i.d Gauss and Bernoulli. Recently, owning to the pseudorandom property of chaotic system, the chaos sequence is used for the construction of Φ. It was proved in [10] that when the sampling distance guarantees a certain value, the logistic system satisfies the RIP condition. In [11], a series of chaos systems, such as Lorenz system and Chuan’s circuit, are used to produce Φ. Thus, in the model of this paper, it was promising to identify the unknown connections.


## 3.2. The Solving Process ofx

As illustrated above, the unknown vector isS-sparse; then the resolution problem can be transformed into an optimization problem which is to find the most sparse solution of (8). Thus the l0 norm optimization is taken into consideration. However, to find a x=argmin∥x∥0 to satisfy y=Φx is a NP hard problem that requires an exhaustive enumeration of all C(S,N) possible combinations for the locations of the nonzero entries in x. Then the application of l2 norm optimization is tried, which is to find a x=argmin∥x∥2 to satisfy y=Φx. It is also denied for the lack of precision. After that, l1 norm is considered; it is more efficient than l0 and more precise than l2. The optimization method is expressed as follows: (10)x=argminx1s.t.y=Φx.Thel1 optimization problem can be transformed to a linear programming known as basis pursuit (BP). As [12] illustrated, the matrix Φ can be shown to have the RIP, when the measurement time satisfies the condition as follows: (11)M>cS×logNS,where c is a constant; we can exactly reconstruct S-sparse vector x via the BP method. Plenty of experimental results show that most of S-sparse signals can be worked out when M≥4S [13]. In this paper, we will discuss the relation between M and S in this identification circumstance by experimental analyses.


## 4. Experiments and Discussions

In the simulation, we setN=100, W=40, z0(i)∈[0,1], i=1,2,…,N, ε=0.01. The chaotic state trajectory of (1) by 100 iterations is shown in Figure 2.Figure 2
The state trajectory of CML.The character of random likeness and boundedness of chaotic system can be observed from Figure2, and for a better perceptual intuition the state of the 50th element is shown in Figure 3.Figure 3
The state trajectory of the 50th element of CML.


### 4.1. The Influence ofε on the Identification

The chaotic behavior is obvious whenε is low, while the system may exist in many states, such as chaos, periodicity, and synchronization. To observe the changing of the network state, we use the information entropy to describe the state as illustrated in [14], by which higher value of entropy implies better chaos character of each node and vice versa. The state of CML is influenced by the parameters ε and W. With the changing of these factors, the information entropy is shown as Figure 4.Figure 4
The diagram of entropy influenced byM and ε.Figure4 shows the entropy with different ε and W; it is obvious that the value of ε is the main influence factor to the entropy.(i)
Whenε<0.2, the degree of coupling is low. It shows a high value of entropy, which means the high randomness of the network. CML system is under a nonsynchronous state, and the sampled sequence benefits the identification.(ii)
When0.2<ε<0.4, it shows a low value of entropy, and the CML system is under a complex state between the nonsynchronous state and the synchronous one. Some behavior such as periodicity, which indicates the randomness is weaker, may lead to a low entropy of the sequence. Thus, it is not the favorable condition for identification.(iii)
When0.4<ε, it arrives at a high value of entropy as chaos because of the synchronization of CML. Considering the synchronization of elements, the correlation between the columns of Φ is high and does not conform to the RIP condition. Therefore, despite the high entropy, it is not suitable for identification.Thus, for the requirement of identification, smallerε is better for the identification.


### 4.2. Identification Result of Unknown Connections

Here we setε=0.01, N=100, S=20, M=60, W=50. Figure 5 shows the connections of an element to the others achieve a successful identification with accuracy ∥x-x^∥=1.8153e-007.Figure 5
The identification result of unknown connections of the 50th element.The optimization process is shown in Figure6.Figure 6
The optimization result of each iteration.
(a)
(b)From Figure6, the estimated value x^ converges to the stable state, and the result is correct when ∥x-x^∥ is closed to zero. The experiment is implemented in Matlab 2013 on Windows 8 Service Pack 1 64-bit operation system. We use a desktop which has a 4-core Intel(R) Core (TM) i3-2120 processor running at 3.30 GHz and 2 GB of RAM. It can be observed that with 4 iterations the result can be almost accurate, and it only takes 0.073322 seconds in our experimental simulation.According to the above experiments, the identification process works perfectly whenε=0.01. But does the algorithm work besides this value? As illustrated in Figure 4, higher coupling coefficient leads to a low entropy or a synchronized state as b and c. The algorithm works well when ε<0.1; thus the premise for completing the identification progress smoothly depends on the coupling coefficient of the network. The result just corresponds with the conclusion that smaller ε benefits the identification.


### 4.3. The Influence of Measurement Time and Sparsity

As we discussed above, to solve the underdetermined equation, the measurement time and the solution sparsity should fulfill a certain condition. For a more detailed understanding of these correlations, the three-dimensional diagram was drawn and is shown in Figure7.Figure 7
The correlations among the measurement time, sparsity, and the identification accuracy.From Figure7 we discover that with smaller measurement time and bigger sparsity the solution turns bad and vice versa. To be more detailed, we showed the aerial view in Figure 8.Figure 8
The aerial view of Figure7, which is divided into 4 areas.For Figure8, we can divide the areas into four parts a, b, c, and d by the distribution of solution effect. The red line y=0.35 means the ratio M/S=2.86 and the green line y=0.25 means the ratio M/S=4.(i)
For area a, whenM<S, it does not meet the solution conditions.(ii)
For area b, whenS<M<2.86S, x almost cannot be calculated by Φ accurately.(iii)
For area c, when2.86S<M<4S, x can be calculated out with acceptable accuracy.(iv)
For area d, whenM>4S, x can be calculated out exactly.The area d corresponds with the traditional conditionM>4S discussed above. However, from the experiment we learn that the area c is regarded as the acceptable one. Such result may have a guiding significance in the identification process.


## 4.1. The Influence ofε on the Identification

The chaotic behavior is obvious whenε is low, while the system may exist in many states, such as chaos, periodicity, and synchronization. To observe the changing of the network state, we use the information entropy to describe the state as illustrated in [14], by which higher value of entropy implies better chaos character of each node and vice versa. The state of CML is influenced by the parameters ε and W. With the changing of these factors, the information entropy is shown as Figure 4.Figure 4
The diagram of entropy influenced byM and ε.Figure4 shows the entropy with different ε and W; it is obvious that the value of ε is the main influence factor to the entropy.(i)
Whenε<0.2, the degree of coupling is low. It shows a high value of entropy, which means the high randomness of the network. CML system is under a nonsynchronous state, and the sampled sequence benefits the identification.(ii)
When0.2<ε<0.4, it shows a low value of entropy, and the CML system is under a complex state between the nonsynchronous state and the synchronous one. Some behavior such as periodicity, which indicates the randomness is weaker, may lead to a low entropy of the sequence. Thus, it is not the favorable condition for identification.(iii)
When0.4<ε, it arrives at a high value of entropy as chaos because of the synchronization of CML. Considering the synchronization of elements, the correlation between the columns of Φ is high and does not conform to the RIP condition. Therefore, despite the high entropy, it is not suitable for identification.Thus, for the requirement of identification, smallerε is better for the identification.


## 4.2. Identification Result of Unknown Connections

Here we setε=0.01, N=100, S=20, M=60, W=50. Figure 5 shows the connections of an element to the others achieve a successful identification with accuracy ∥x-x^∥=1.8153e-007.Figure 5
The identification result of unknown connections of the 50th element.The optimization process is shown in Figure6.Figure 6
The optimization result of each iteration.
(a)
(b)From Figure6, the estimated value x^ converges to the stable state, and the result is correct when ∥x-x^∥ is closed to zero. The experiment is implemented in Matlab 2013 on Windows 8 Service Pack 1 64-bit operation system. We use a desktop which has a 4-core Intel(R) Core (TM) i3-2120 processor running at 3.30 GHz and 2 GB of RAM. It can be observed that with 4 iterations the result can be almost accurate, and it only takes 0.073322 seconds in our experimental simulation.According to the above experiments, the identification process works perfectly whenε=0.01. But does the algorithm work besides this value? As illustrated in Figure 4, higher coupling coefficient leads to a low entropy or a synchronized state as b and c. The algorithm works well when ε<0.1; thus the premise for completing the identification progress smoothly depends on the coupling coefficient of the network. The result just corresponds with the conclusion that smaller ε benefits the identification.


## 4.3. The Influence of Measurement Time and Sparsity

As we discussed above, to solve the underdetermined equation, the measurement time and the solution sparsity should fulfill a certain condition. For a more detailed understanding of these correlations, the three-dimensional diagram was drawn and is shown in Figure7.Figure 7
The correlations among the measurement time, sparsity, and the identification accuracy.From Figure7 we discover that with smaller measurement time and bigger sparsity the solution turns bad and vice versa. To be more detailed, we showed the aerial view in Figure 8.Figure 8
The aerial view of Figure7, which is divided into 4 areas.For Figure8, we can divide the areas into four parts a, b, c, and d by the distribution of solution effect. The red line y=0.35 means the ratio M/S=2.86 and the green line y=0.25 means the ratio M/S=4.(i)
For area a, whenM<S, it does not meet the solution conditions.(ii)
For area b, whenS<M<2.86S, x almost cannot be calculated by Φ accurately.(iii)
For area c, when2.86S<M<4S, x can be calculated out with acceptable accuracy.(iv)
For area d, whenM>4S, x can be calculated out exactly.The area d corresponds with the traditional conditionM>4S discussed above. However, from the experiment we learn that the area c is regarded as the acceptable one. Such result may have a guiding significance in the identification process.


## 5. Conclusion and Future Work

In this paper, we propose a new approach for the identification of CML. We work out the unknown connections vector through thel1 method. The requirement of sampling time and data characters are discussed in detail in this paper, and the identification result meets the precision of the experiment. Moreover, also some possibility of further researches exists.On one side, assuming there is an undirected network, besides all the values of the nodes’ state, we only know the total sparsity of all the connections (some nodes may have sparse connections, while some nodes’ connections may be not sparse); how can we get the correct identification result? This problem may be solved by the following steps. Firstly, we should find the connections between two nodes with sparse unknown connections and estimate them. Secondly, owning to the symmetry characteristic of undirected network, with more and more unknown connections being identified, some of the connections of nodes which were not sparse become sparse; thus we should find these nodes and estimate the connections. Thirdly, continue the second step until we know that remaining nodes’ connections cannot be estimated.On the other side, comparing with traditional method of topology identification,l1 method can finish the process of identification with lesser sampling time, but it requires knowing the whole states of the network. Its applications may be limited in the network which are able to know all the states of the nodes. Thus, in the future work, the topology identification with the deficiency of a part of nodes’ state value may be discussed.



---

*Source: 303454-2015-07-05.xml*