# Identification of Coupled Map Lattice Based on Compressed Sensing

Authors: Dong Xie; Lixiang Li; Xinxin Niu; Yixian Yang
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

A novel approach for the parameter identification of coupled map lattice (CML) based on compressed sensing is presented in this paper. We establish a meaningful connection between these two seemingly unrelated study topics and identify the weighted parameters using the relevant recovery algorithms in compressed sensing. Specifically, we first transform the parameter identification problem of CML into the sparse recovery problem of underdetermined linear system. In fact, compressed sensing provides a feasible method to solve underdetermined linear system if the sensing matrix satisfies some suitable conditions, such as restricted isometry property (RIP) and mutual coherence. Then we give a low bound on the mutual coherence of the coefficient matrix generated by the observed values of CML and also prove that it satisfies the RIP from a theoretical point of view. If the weighted vector of each element is sparse in the CML system, our proposed approach can recover all the weighted parameters using only aboutM samplings, which is far less than the number of the lattice elements N. Another important and significant advantage is that if the observed data are contaminated with some types of noises, our approach is still effective. In the simulations, we mainly show the effects of coupling parameter and noise on the recovery rate.


---

## Body

## 1. Introduction

Coupled map lattice (CML), developed by Kaneko [1–3], is a dynamical system that can be described as an array of smaller finite-dimensional subsystems endowed with local interactions. The evolution of the subsystem at one lattice element depends not only on the states of the element itself, but also on the state of the other elements. If the coupling interaction is a function of all the elements, then the CML is called globally coupled map lattice. So far, a very large number of remarkable results about this topic were obtained by researchers working in different areas of physics, biology, mathematics, and engineering. However, most of the papers mainly concentrated on analysing the evolutionary behaviours and properties of CML [4–6]. And the topic about the parameter identification or reconstruction of CML from measured data has received relatively little attention. Over the past fifteen years, several methods for the identification problem have been presented [7–11]. Billings and Coca [8] introduced a novel approach to the identification of CML and the method exploited the regularity of the CML model. Subsequently, Billings et al. [10] pointed out some drawbacks of the method [7, 9] and presented a multiresolution approximation for the underlying spatiotemporal dynamics using B-spline wavelet and scaling functions. Ning et al. [11] first transformed the nonlinear spatiotemporal system into a class of multi-input-multi-output (MIMO) partially linear systems and then proposed an effective online identification algorithm for this nonlinear spatiotemporal system. Subsequently, Ning et al. [12] proposed a novel kernel-based learning algorithm and it can be used to effectively achieve accurate derivative estimation for nonlinear functions in the time domain. Kohar et al. [13] studied the usefulness of coupled redundancy as a mechanism for reduction in local noise in coupled map lattices and investigated the role of network topology, coupling strength, and iteration number in this mechanism. But sometimes in order to improve the efficiency of parameter identification, we need to reduce the number of observations or samplings under the condition of accurate identification. In addition, from an engineering perspective, we cannot ensure that the received data are truly generated by the CML system because our sampled data may be contaminated with noise when we perform some indispensable tasks (e.g., data sampling and data transmission). To the best of our knowledge, most of papers about this topic (including the papers mentioned above) did not consider the above two fascinating and significant problems. And the parameter identification of CML using a very few number of observations or samplings is still regarded as a very intractable problem. Another challenging problem is that if the observed data are contaminated with noise, how can we accurately identify all the weighted parameters?The compressed sensing theory, introduced in [14–17], breaks the limitation of Nyquist-Shannon sampling theorem and is widely used in various fields, such as information theory, medical imaging, earth sciences, and astronomy. The standard model of compressed sensing is an underdetermined linear system y
=
A
x, where A
∈
R
M
×
N, x
∈
R
N, y
∈
R
M, and M
<
N. It is clear that, given a coefficient matrix A and an observation vector y, there exist infinite x such that y
=
A
x. In order to recover the unique vector x from the observed vector y, we need two conditions; that is, the vector x is sparse and the matrix A must satisfy some special properties, such as restricted isometry property (RIP) and mutual coherence [18]. In other words, if the matrix A satisfies the RIP, then we can recover the N-dimensional sparse vector x from M-dimensional observed vector y. Further, the RIP is sufficient for a variety of algorithms to be able to successfully recover a sparse vector from noisy samplings. These two useful theoretical results about compressed sensing provide insights to solve the above stubborn problems about the identification of CML.Different from the existing methods about parameter identification of CML system, we independently present a new approach using the compressed sensing theory in this paper. Specifically, we first transform the parameter identification problem into the reconstruction problem of underdetermined linear system through simple mathematical transformation. Subsequently, we give a low bound on the mutual coherence of sensing matrix using the inverse formula of Cauchy-Schwarz inequality and then prove that it satisfies the RIP with suitable parameters. At last we exploit the classic Orthogonal Matching Pursuit algorithm in compressed sensing to recover the weighted parameters of CML system. The result shows that if the weighted vector of every lattice element has at mosts nonzero entries, then we just need M observations, which is far less than N, to accurately identify the weighted vector. Another critical advantage of our approach is that the reconstruction algorithm can still work if the sampled data are contaminated with some types of noises (e.g., Gaussian noise, uniform noise). We investigate the effects of coupling parameter and noise on the recovery rate in our simulations. We found an interesting fact that when the sampled data are contaminated with uniform noise, the recovery effects are better than that if the observed data are authentic.The remainder of this paper is organized in the following manner. We recall the standard CML model in Section2. In Section 3 we introduce some backgrounds about the compressed sensing theory. We present the theoretical results about our proposed identification method based on compressed sensing in Section 4 and show our simulations in Section 5. Finally, we draw our conclusions in Section 6.


## 2. The CML Model

We give a brief review of standard CML model in this section. Generally speaking, the widely used CMLs can be divided into two categories, that is, the diffusive (DCML) model and the global (GCML) model. The difference between these two models is whether the evolution of the subsystem at any lattice element depends on the states of all the other elements. In a standard GCML model, if we set some weighted parameters to 0, then it can be seen as a DCML model. Without loss of generality, we consider the following GCML model:(1)
x
t
+
1
i
=
1
-
ϵ
f
x
t
i
+
ϵ
N
∑
j
=
1
N
c
i
j
g
x
t
j
,where x
t
(
i
) defines the state of the lattice element i
(
1
≤
i
≤
N
) at a discrete time step t
(
1
≤
t
≤
M
), ϵ
∈
(
0,1
) is the coupling parameter, f and g are maps with respect to the local dynamics and nonlocal system, and c
i
=
(
c
i
1
,
c
i
2
,
…
,
c
i
N
)
∈
{
0,1
}
1
×
N is the unknown weighted vector of the lattice element i. The two widely used forms of g
(
x
), namely, g
(
x
)
=
f
(
x
) and g
(
x
)
=
x, are corresponding to synchronous and asynchronous updates of the lattice, respectively. For the sake of simplicity, we just consider the synchronous case in our paper; that is, f
(
x
)
=
g
(
x
). In many scenarios, f
(
x
) is the standard logistic map, which can be written as (2)
f
x
=
4
x
1
-
x
,where x
∈
(
0,1
) and the range eventually lies in the interval (0,1).


## 3. Compressed Sensing

In the field of compressed sensing, the researchers mainly concentrate on designing the excellent sensing matrices and the efficient reconstruction algorithms. Compressed sensing provides a method to obtain a unique solution from an underdetermined linear system taking advantage of the prior knowledge that the true solution is sparse. In mathematical terms, we consider the following underdetermined linear system:(3)
y
=
A
x
,where A
∈
R
M
×
N
(
M
<
N
) and x
∈
R
N. This equation depicts the process that the original N-dimensional data x is compressed into an M-dimensional data y. In this formula, A denotes the sensing matrix and we call y observed vector or observed values. A vector x is said to be s-sparse when it has at most s nonzero entries. For a s-sparse original vector x
∈
R
N, if the sensing matrix satisfies some suitable condition, then there exist some algorithms to recover the vector x from the observed vector y. Next, we recall some fundamental results about sensing matrices and reconstruction algorithms in the following two subsections.


### 3.1. Sensing Matrix

In this subsection, we address two significant concepts frequently used in compressed sensing theory, that is, RIP and mutual coherence. The famous RIP was first presented by [14], which is defined as follows.Definition 1.
A matrixA satisfies the RIP of order s if there exists a δ
s
∈
(
0,1
) such that (4)
1
-
δ
s
v
2
2
≤
A
v
2
2
≤
1
+
δ
s
v
2
2holds for all s-sparse vectors v.In fact, the RIP sufficiently guarantees that the original vector can be exactly recovered from the observed values. Furthermore, if the matrixA satisfies the RIP, then it is also sufficient for a variety of algorithms to be able to recover the spare vector from observed data contaminated with noise. The following lemma [19] denotes noiseless recovery if the matrix A satisfies the RIP.Lemma 2.
LetA be a sensing matrix in (3) that satisfies the RIP of order 2
s with δ
2
s
<
2
-
1. Then the original sparse vector can be exactly recovered.Baraniuk et al. [20] have proved that the random sensing matrix, whose entries are identically and independently sampled from a Gaussian distribution or a sub-Gaussian distribution, satisfies the RIP with overwhelming probability. Similar to a Gaussian random matrix, a Bernoulli matrix or a Random Discrete Fourier Transform (RDFT) matrix can also be used as sensing matrix. However, given a specific matrix A, it is very hard to verify whether A satisfies the RIP or not. The concept of mutual coherence provides a more simple choice [18, 21].Definition 3.
Given a matrixA
∈
R
M
×
N
(
M
<
N
), a
i denotes the ith column of A. The mutual coherence of the matrix A, μ
(
A
), is the largest absolute normalized inner product between any two columns of A. Namely, (5)
μ
A
=
max
1
≤
i
,
j
≤
N
,
i
≠
j
⁡
a
i
,
a
j
a
i
2
a
j
2
.From Cauchy-Schwarz inequality|
〈
a
i
,
a
j
〉
|
≤
a
i
2
a
j
2, it is clear that the mutual coherence of any matrix A is bounded by 1. In order to complete our proof, we will review the Gershgorin circle theorem [22] here.Lemma 4.
The eigenvalues of ann
×
n matrix A with entries a
i
j, 1
≤
i, j
≤
n, lie in the union of n discs d
i
=
d
i
(
e
i
,
f
i
) centered at e
i
=
a
i
i and with radius f
i
=
∑
i
≠
j
|
a
i
j
|.


### 3.2. Recovery Algorithm

A straightforward approach to obtain the originals-sparse vector x from the above underdetermined system (3) can be viewed as the optimization problem of (6)
x
∗
=
a
r
g
m
i
n
x
x
0
subject  to
A
x
=
y
,which is called l
0 optimization problem. This problem is very difficult to solve and it is NP-hard in general case [14]. Since the convex property of l
1 norm, a classic method used in compressed sensing is to replace x
0 with x
1; that is, (7)
x
∗
=
a
r
g
m
i
n
x
x
1
subject  to
A
x
=
y
.In fact, Candès [19] has pointed out that the solution to (6) is that of (7) when A satisfies the RIP with δ
2
s
<
2
-
1. Although some convex optimization techniques are powerful for sparse vector reconstruction, there also exist a variety of greedy algorithms [23–25] for solving this problem. We describe the classic Orthogonal Matching Pursuit (OMP) algorithm as follows because our simulations need to use it.In Algorithm1, Λ denotes the support set and x
Λ is the vector obtained by collecting the entries of x corresponding to the set Λ. A
Λ is the submatrix of A composed of the column vectors of A corresponding to the support set Λ. During each pass through the loop, the algorithm first chooses the optimal index J and updates the support set Λ and then computes the vector x which minimizes A
x
-
y
2
2 such that supp
⁡
(
x
)
=
Λ.Algorithm 1:Orthogonal matching pursuit.
Require: y
∈
R
M  t
h
e
o
b
s
e
r
v
e
d
v
e
c
t
o
r
Ensure: x
∈
R
N  t
h
e
s
p
a
r
s
e
v
e
c
t
o
r
x
[
0
]
≔
0;
r
[
0
]
≔
y;
Λ
≔
∅;
k
≔
0.
repeat
J
≔
arg
⁡
min
1
≤
j
≤
N
⁡
a
j
T
r
k
a
j
2,
Λ
≔
Λ
∪
J,
x
Λ
[
k
+
1
]
≔
arg
⁡
min
v
⁡
A
Λ
v
-
y
2
2,
r
[
k
+
1
]
≔
y
-
A
x
[
k
+
1
],
k
≔
k
+
1.
until  r
[
k
]
2
≤
E
P
S.
return  x
≔
x
[
k
].


## 3.1. Sensing Matrix

In this subsection, we address two significant concepts frequently used in compressed sensing theory, that is, RIP and mutual coherence. The famous RIP was first presented by [14], which is defined as follows.Definition 1.
A matrixA satisfies the RIP of order s if there exists a δ
s
∈
(
0,1
) such that (4)
1
-
δ
s
v
2
2
≤
A
v
2
2
≤
1
+
δ
s
v
2
2holds for all s-sparse vectors v.In fact, the RIP sufficiently guarantees that the original vector can be exactly recovered from the observed values. Furthermore, if the matrixA satisfies the RIP, then it is also sufficient for a variety of algorithms to be able to recover the spare vector from observed data contaminated with noise. The following lemma [19] denotes noiseless recovery if the matrix A satisfies the RIP.Lemma 2.
LetA be a sensing matrix in (3) that satisfies the RIP of order 2
s with δ
2
s
<
2
-
1. Then the original sparse vector can be exactly recovered.Baraniuk et al. [20] have proved that the random sensing matrix, whose entries are identically and independently sampled from a Gaussian distribution or a sub-Gaussian distribution, satisfies the RIP with overwhelming probability. Similar to a Gaussian random matrix, a Bernoulli matrix or a Random Discrete Fourier Transform (RDFT) matrix can also be used as sensing matrix. However, given a specific matrix A, it is very hard to verify whether A satisfies the RIP or not. The concept of mutual coherence provides a more simple choice [18, 21].Definition 3.
Given a matrixA
∈
R
M
×
N
(
M
<
N
), a
i denotes the ith column of A. The mutual coherence of the matrix A, μ
(
A
), is the largest absolute normalized inner product between any two columns of A. Namely, (5)
μ
A
=
max
1
≤
i
,
j
≤
N
,
i
≠
j
⁡
a
i
,
a
j
a
i
2
a
j
2
.From Cauchy-Schwarz inequality|
〈
a
i
,
a
j
〉
|
≤
a
i
2
a
j
2, it is clear that the mutual coherence of any matrix A is bounded by 1. In order to complete our proof, we will review the Gershgorin circle theorem [22] here.Lemma 4.
The eigenvalues of ann
×
n matrix A with entries a
i
j, 1
≤
i, j
≤
n, lie in the union of n discs d
i
=
d
i
(
e
i
,
f
i
) centered at e
i
=
a
i
i and with radius f
i
=
∑
i
≠
j
|
a
i
j
|.


## 3.2. Recovery Algorithm

A straightforward approach to obtain the originals-sparse vector x from the above underdetermined system (3) can be viewed as the optimization problem of (6)
x
∗
=
a
r
g
m
i
n
x
x
0
subject  to
A
x
=
y
,which is called l
0 optimization problem. This problem is very difficult to solve and it is NP-hard in general case [14]. Since the convex property of l
1 norm, a classic method used in compressed sensing is to replace x
0 with x
1; that is, (7)
x
∗
=
a
r
g
m
i
n
x
x
1
subject  to
A
x
=
y
.In fact, Candès [19] has pointed out that the solution to (6) is that of (7) when A satisfies the RIP with δ
2
s
<
2
-
1. Although some convex optimization techniques are powerful for sparse vector reconstruction, there also exist a variety of greedy algorithms [23–25] for solving this problem. We describe the classic Orthogonal Matching Pursuit (OMP) algorithm as follows because our simulations need to use it.In Algorithm1, Λ denotes the support set and x
Λ is the vector obtained by collecting the entries of x corresponding to the set Λ. A
Λ is the submatrix of A composed of the column vectors of A corresponding to the support set Λ. During each pass through the loop, the algorithm first chooses the optimal index J and updates the support set Λ and then computes the vector x which minimizes A
x
-
y
2
2 such that supp
⁡
(
x
)
=
Λ.Algorithm 1:Orthogonal matching pursuit.
Require: y
∈
R
M  t
h
e
o
b
s
e
r
v
e
d
v
e
c
t
o
r
Ensure: x
∈
R
N  t
h
e
s
p
a
r
s
e
v
e
c
t
o
r
x
[
0
]
≔
0;
r
[
0
]
≔
y;
Λ
≔
∅;
k
≔
0.
repeat
J
≔
arg
⁡
min
1
≤
j
≤
N
⁡
a
j
T
r
k
a
j
2,
Λ
≔
Λ
∪
J,
x
Λ
[
k
+
1
]
≔
arg
⁡
min
v
⁡
A
Λ
v
-
y
2
2,
r
[
k
+
1
]
≔
y
-
A
x
[
k
+
1
],
k
≔
k
+
1.
until  r
[
k
]
2
≤
E
P
S.
return  x
≔
x
[
k
].


## 4. Parameter Identification of GCML Based on Compressed Sensing

In this section, we first transform the parameter identification problem of GCML to the reconstruction problem in compressed sensing. Then we give a low bound on the mutual coherence of the corresponding sensing matrix using the inverse formula of Cauchy-Schwarz inequality. At last, we prove that it satisfies the RIP.Theorem 5.
Given a GCML model described as (1) and M observed values x
t
(
i
) of every lattice element i, where 1
≤
t
≤
M, 1
≤
i
≤
N, then the identification problem of (1) can be transformed into the reconstruction problem of an underdetermined linear system.Proof.
From (1), we can obtain the following equation: (8)
N
ϵ
x
t
+
1
i
-
1
-
ϵ
f
x
t
i
=
∑
j
=
1
N
c
i
j
g
x
t
j
.Denote y
t
(
i
)
=
N
/
ϵ
[
x
t
+
1
(
i
)
-
(
1
-
ϵ
)
f
(
x
t
(
i
)
)
]; then we get (9)
y
t
i
=
∑
j
=
1
N
c
i
j
g
x
t
j
=
g
x
t
1
⋯
g
x
t
N
c
i
1
⋮
c
i
N
.If we sample M times for every element i in the lattice, therefore we have (10)
y
1
i
⋮
y
M
i
=
g
x
1
1
⋯
g
x
1
N
⋮
⋱
⋮
g
x
M
1
⋯
g
x
M
N
c
i
1
⋮
c
i
N
,where i
=
1,2
,
…
,
N. So(11)
y
1
1
⋯
y
1
N
⋮
⋱
⋮
y
M
1
⋯
y
M
N
=
g
x
1
1
⋯
g
x
1
N
⋮
⋱
⋮
g
x
M
1
⋯
g
x
M
N
c
11
⋯
c
N
1
⋮
⋱
⋮
c
1
N
⋯
c
N
N
.Denote(12)
Y
=
y
1
1
⋯
y
1
N
⋮
⋱
⋮
y
M
1
⋯
y
M
N
∈
R
M
×
N
,
B
=
g
x
1
1
⋯
g
x
1
N
⋮
⋱
⋮
g
x
M
1
⋯
g
x
M
N
∈
R
M
×
N
,
C
=
c
11
⋯
c
N
1
⋮
⋱
⋮
c
1
N
⋯
c
N
N
∈
0,1
N
×
N
.Then (11) can be expressed as an underdetermined linear system Y
=
B
C. So the identification of GCML can be transformed into the reconstruction problem of an underdetermined linear system.Letb
i be the ith column of the matrix B. Therefore, we define the sensing matrix related to the GCML as A
=
1
/
α
B, where α
=
m
a
x
1
≤
i
≤
N
b
i
2
2. Note that the scaler 1
/
α is used for normalization. In what follows, we assume that each column of C has at most s nonzero entries. In order to give a low bound on the mutual coherence of A, we need the following two useful lemmas.Lemma 6.
Leta
i and b
i, 1
≤
i
≤
n, be positive real numbers, where a
i
∈
[
A
1
,
A
2
] and b
i
∈
[
B
1
,
B
2
]. Then (13)
∑
i
=
1
n
b
i
2
+
B
1
B
2
A
1
A
2
∑
i
=
1
n
a
i
2
≤
B
2
A
1
+
B
1
A
2
∑
i
=
1
n
a
i
b
i
.Proof.
For anyi, we have (14)
B
1
A
2
≤
b
i
a
i
≤
B
2
A
1
.Namely, (15)
b
i
a
i
-
B
1
A
2
B
2
A
1
-
b
i
a
i
≥
0
.That is, (16)
B
2
A
1
+
B
1
A
2
a
i
b
i
-
b
i
2
-
B
1
B
2
A
1
A
2
a
i
2
≥
0
.Thus, (17)
b
i
2
+
B
1
B
2
A
1
A
2
a
i
2
≤
B
2
A
1
+
B
1
A
2
a
i
b
i
.Summing i from 0 to n, we obtain the results.Lemma 7 (the inverse formula of Cauchy-Schwarz inequality).
Leta
i and b
i, 1
≤
i
≤
n, be positive real numbers, where a
i
∈
[
A
1
,
A
2
] and b
i
∈
[
B
1
,
B
2
]. Then (18)
∑
i
=
1
n
a
i
2
∑
i
=
1
n
b
i
2
≤
1
4
A
2
B
2
A
1
B
1
+
A
1
B
1
A
2
B
2
2
∑
i
=
1
n
a
i
b
i
2
.Proof.
Consider(19)
∑
i
=
1
n
b
i
2
1
/
2
-
B
1
B
2
A
1
A
1
∑
i
=
1
n
a
i
2
1
/
2
2
=
∑
i
=
1
n
b
i
2
+
B
1
B
2
A
1
A
1
∑
i
=
1
n
a
i
2
-
2
B
1
B
2
A
1
A
1
∑
i
=
1
n
a
i
2
∑
i
=
1
n
b
i
2
1
/
2
≥
0
.Thus, (20)
∑
i
=
1
n
b
i
2
+
B
1
B
2
A
1
A
1
∑
i
=
1
n
a
i
2
≥
2
B
1
B
2
A
1
A
1
∑
i
=
1
n
a
i
2
∑
i
=
1
n
b
i
2
1
/
2
.From Lemma 6, we obtain (21)
B
2
A
1
+
B
1
A
2
∑
i
=
1
n
a
i
b
i
≥
2
B
1
B
2
A
1
A
1
∑
i
=
1
n
a
i
2
∑
i
=
1
n
b
i
2
1
/
2
.Squaring both sides, we complete the proof.Theorem 8.
Letm
a
x
A be the maximal element in A and let m
i
n
A be the minimal element in A. Then (22)
μ
A
≥
2
min
A
⁡
min
A
⁡
m
a
x
A
max
A
⁡
m
a
x
A
+
m
i
n
A
.Proof.
Leta
i be the ith column of the matrix A. Thus, (23)
μ
A
=
max
1
≤
i
≠
j
≤
N
⁡
a
i
,
a
j
a
i
a
j
=
max
1
≤
i
≠
j
≤
N
⁡
∑
k
=
1
M
g
x
k
i
g
x
k
j
∑
k
=
1
M
g
x
k
i
2
∑
k
=
1
M
g
x
k
j
2
.From (1), we can know that each element g
(
x
k
(
i
)
) in matrix A is obviously positive. Figure 1 also provides the experimental evidence. For specific i and j, let C
1
=
m
i
n
1
≤
k
≤
M
g
(
x
k
(
i
)
), C
2
=
m
a
x
1
≤
k
≤
M
g
(
x
k
(
i
)
), D
1
=
m
i
n
1
≤
k
≤
M
g
(
x
k
(
j
)
), and D
2
=
m
a
x
1
≤
k
≤
M
g
(
x
k
(
j
)
). From (21), we obtain (24)
a
i
,
a
j
a
i
a
j
≥
2
D
1
D
2
C
1
C
2
·
C
1
C
2
C
1
D
1
+
C
2
D
2
=
2
C
1
C
2
D
1
D
2
C
1
D
1
+
C
2
D
2
.
If theith column contains the maximal element m
a
x
A in A and the jth column contains the minimal element m
i
n
A, that is, C
2
=
m
a
x
A and D
1
=
m
i
n
A, where i
≠
j, thus, 〈
a
i
,
a
j
〉
/
a
i
a
j
≥
2
C
1
C
2
D
1
D
2
/
C
1
D
1
+
C
2
D
2
≥
2
m
i
n
A
m
i
n
A
m
a
x
A
/
m
a
x
A
(
m
a
x
A
+
m
i
n
A
). If the ith column contains the minimal element and the jth column contains the maximal element, the result also holds. Else, if i
=
j—that is, the maximal element and the minimal element are both in a column of A—then 〈
a
i
,
a
j
〉
/
a
i
a
j also greater than 2
m
i
n
A
m
i
n
A
m
a
x
A
/
m
a
x
A
(
m
a
x
A
+
m
i
n
A
). Thus, we complete the proof.Figure 1
The distribution of observed valuesx
t
(
i
). ϵ
=
0.01, N
=
256, M
=
64, and K
=
25.Theorem 9.
Given a sensing matrixA defined by the above, then A satisfies the RIP of order s with δ
s
(
2
m
i
n
A
m
i
n
A
m
a
x
A
/
m
a
x
A
(
m
a
x
A
+
m
i
n
A
)
(
s
-
1
)
≤
δ
s
<
1
) for all s
<
1
/
μ
(
A
)
+
1.Proof.
For anys-sparse vector v, let Λ be the support set and |
Λ
|
=
s. A
Λ denotes the submatrix of A composed of the column vectors of A corresponding to the support set Λ and v
Λ is the vector obtained by collecting the elements of x corresponding to the set Λ. Thus, (25)
A
v
2
2
=
A
Λ
v
Λ
,
A
Λ
v
Λ
=
v
Λ
T
A
Λ
T
A
Λ
v
Λ
.We consider the Gram matrix G
=
A
Λ
T
A
Λ. Evidently it is positive semidefinite. We denote the minimal eigenvalue by λ
m
i
n and the maximal eigenvalue by λ
m
a
x. From Lemma 4, there exist h
,
k
∈
Λ such that (26)
b
h
2
-
∑
i
∈
Λ
∖
h
b
h
,
b
i
α
2
≤
λ
m
a
x
≤
b
h
2
+
∑
i
∈
Λ
∖
h
b
h
,
b
i
α
2
,
b
k
2
-
∑
i
∈
Λ
∖
k
b
k
,
b
i
α
2
≤
λ
m
i
n
≤
b
k
2
+
∑
i
∈
Λ
∖
k
b
k
,
b
i
α
2
.Therefore, (27)
A
v
2
2
=
v
Λ
T
A
Λ
T
A
Λ
v
Λ
≤
v
Λ
T
λ
m
a
x
v
Λ
≤
b
h
2
+
∑
i
∈
Λ
∖
h
b
h
,
b
i
α
2
v
2
2
,
A
v
2
2
=
v
Λ
T
A
Λ
T
A
Λ
v
Λ
≥
v
Λ
T
λ
m
i
n
v
Λ
≥
b
k
2
-
∑
i
∈
Λ
∖
k
b
k
,
b
i
α
2
v
2
2
.Because α
=
m
a
x
1
≤
i
≤
N
b
i
2
2, μ
(
B
)
=
μ
(
A
), and |
Λ
∖
h
|
=
|
Λ
∖
k
|
=
s
-
1, we can get (28)
b
h
2
+
∑
i
∈
Λ
∖
h
b
h
,
b
i
α
2
≤
1
+
s
-
1
μ
A
,
b
k
2
-
∑
i
∈
Λ
∖
k
b
k
,
b
i
α
2
≥
1
-
s
-
1
μ
A
.If (
s
-
1
)
μ
(
A
)
<
1, then we let δ
s
=
(
s
-
1
)
μ
(
A
). Therefore, when s
<
1
/
μ
A
+
1, there exists δ
s such that (
1
-
δ
s
)
v
2
2
≤
A
v
2
2
≤
(
1
+
δ
s
)
v
2
2. Note that, from Theorem 8, we know that 2
m
i
n
A
m
i
n
A
m
a
x
A
/
m
a
x
A
(
m
a
x
A
+
m
i
n
A
)
(
s
-
1
)
≤
δ
s
<
1. Thus, we complete the proof.


## 5. Simulation Results

Ifs
<
1
/
μ
(
A
)
+
1, Theorem 9 shows that the sensing matrix of GCML satisfies the RIP of order s and thus the weighted vector c
i of every element i can be exactly recovered. In this section, we give the experimental results of parameter identification of this special type of CML using the above OMP algorithm. We state that the weighted parameter matrix C is s-sparse in our model. Namely, every column vector of C contains at most s nonzero numbers, where s is much smaller than N. Simulations can be classified into the following two types: noiseless recovery and noisy recovery.


### 5.1. Noiseless Recovery

In this subsection we consider the noiseless model; that is, the observed data are truly produced by (1). Figure 1 investigates the distribution of x
t
(
i
), where the weighted matrix is 25-sparse and all the nonzero entries of the matrix are independently selected from a normal distribution with mean 0 and variance 0.5. The result shows that it can be roughly regarded as a uniform distribution whose possible values are from 0 to 1. In Figure 2, we randomly choose two lattice elements and study the identification accuracy of the weighted vector. Figures 2(a) and 2(b), respectively, depict the identification effects about the 35th and the 162nd lattice elements in our GCML model. The experimental results show that it can accurately identify the parameters using the reconstruction algorithm in compressed theory. Figure 3 depicts the overall relationship among the sparsity, the required sampling times, and the recovery rate. In our simulations, the recovery rate is defined as S
E
/
N
2, where S
E stands for the number of the same entries between the original and the reconstructed weighted matrix. In Figure 3, the recovery rate is close to 1 due to the sparsity of the weighted matrix. However, when M
<
2
s, the recovery rate is equal to 0. This particular phenomenon is reasonable because if M
<
2
s, then the underdetermined linear system y
=
A
x does not have a unique sparse solution. In Figure 4, we study the effects of the sparsity, the sampling time, and the coupling parameter on the recovery rate. Figure 4(a) shows that, whatever the coupling parameter we choose, it only needs less than 100 samplings to completely recover the whole weighted matrix. Similarly, Figure 4(b) shows that the sparsity has a negative effect on the recovery rate. In general, the smaller the coupling parameter is, the higher the recovery rate is.Figure 2
The identification effects based on compressed sensing.ϵ
=
0.01, N
=
256, M
=
100, and s
=
15.
(a)
(b)Figure 3
The relationship among the sparsity, the sampling time, and the recovery rate.ϵ
=
0.01 and N
=
128.Figure 4
Recovery rate for different sampling times, sparsity, and coupling parameters.(
a
)
N
=
160 and s
=
20; (
b
)
N
=
256 and M
=
60.
(a)
(b)


### 5.2. Noisy Recovery

It is very difficult to obtain the accurate observations in actual operation. So we consider the case that the observed data are contaminated with noise. Here we mainly consider two classic types of noises, that is, Gaussian noise and uniform noise. Figure5 shows that if the observed data are contaminated with Gaussian noise, then the recovery rate is lower than that of accurate observations. However, if the data are contaminated with uniform noise, then the recovery rate is surprisingly higher than that of accurate observations. From a statistical point of view, the reason why this counterintuitive phenomenon happens is that the data contaminated with uniform noise are more uniform and random. In fact, the sensing matrix produced by this mixed data has stronger restricted isometry property.Figure 5
Recovery rate for different sampling times, sparsity, and noises.(
a
)
ϵ
=
0.01, N
=
160, and s
=
20; (
b
)
ϵ
=
0.01, N
=
256, and M
=
60.
(a)
(b)


## 5.1. Noiseless Recovery

In this subsection we consider the noiseless model; that is, the observed data are truly produced by (1). Figure 1 investigates the distribution of x
t
(
i
), where the weighted matrix is 25-sparse and all the nonzero entries of the matrix are independently selected from a normal distribution with mean 0 and variance 0.5. The result shows that it can be roughly regarded as a uniform distribution whose possible values are from 0 to 1. In Figure 2, we randomly choose two lattice elements and study the identification accuracy of the weighted vector. Figures 2(a) and 2(b), respectively, depict the identification effects about the 35th and the 162nd lattice elements in our GCML model. The experimental results show that it can accurately identify the parameters using the reconstruction algorithm in compressed theory. Figure 3 depicts the overall relationship among the sparsity, the required sampling times, and the recovery rate. In our simulations, the recovery rate is defined as S
E
/
N
2, where S
E stands for the number of the same entries between the original and the reconstructed weighted matrix. In Figure 3, the recovery rate is close to 1 due to the sparsity of the weighted matrix. However, when M
<
2
s, the recovery rate is equal to 0. This particular phenomenon is reasonable because if M
<
2
s, then the underdetermined linear system y
=
A
x does not have a unique sparse solution. In Figure 4, we study the effects of the sparsity, the sampling time, and the coupling parameter on the recovery rate. Figure 4(a) shows that, whatever the coupling parameter we choose, it only needs less than 100 samplings to completely recover the whole weighted matrix. Similarly, Figure 4(b) shows that the sparsity has a negative effect on the recovery rate. In general, the smaller the coupling parameter is, the higher the recovery rate is.Figure 2
The identification effects based on compressed sensing.ϵ
=
0.01, N
=
256, M
=
100, and s
=
15.
(a)
(b)Figure 3
The relationship among the sparsity, the sampling time, and the recovery rate.ϵ
=
0.01 and N
=
128.Figure 4
Recovery rate for different sampling times, sparsity, and coupling parameters.(
a
)
N
=
160 and s
=
20; (
b
)
N
=
256 and M
=
60.
(a)
(b)


## 5.2. Noisy Recovery

It is very difficult to obtain the accurate observations in actual operation. So we consider the case that the observed data are contaminated with noise. Here we mainly consider two classic types of noises, that is, Gaussian noise and uniform noise. Figure5 shows that if the observed data are contaminated with Gaussian noise, then the recovery rate is lower than that of accurate observations. However, if the data are contaminated with uniform noise, then the recovery rate is surprisingly higher than that of accurate observations. From a statistical point of view, the reason why this counterintuitive phenomenon happens is that the data contaminated with uniform noise are more uniform and random. In fact, the sensing matrix produced by this mixed data has stronger restricted isometry property.Figure 5
Recovery rate for different sampling times, sparsity, and noises.(
a
)
ϵ
=
0.01, N
=
160, and s
=
20; (
b
)
ϵ
=
0.01, N
=
256, and M
=
60.
(a)
(b)


## 6. Conclusions

In this paper we establish a bridge between the parameter identification of CML and compressed sensing theory. Specifically, we first skillfully transform the identification problem into the sparse reconstruction problem of an underdetermined linear system. And then we prove that the sensing matrixA of CML satisfies the RIP if the sparsity of original signals is smaller than 1
/
μ
(
A
)
+
1. In our simulations, we consider the effects of various factors on the recovery rate, such as sampling time, sparsity, coupled parameter, and noise. In general, our proposed approach has the following advantages. Compared with some existing identification approaches, our approach only requires a very few number of observations for accurate identification. In addition, if the sampled data are contaminated with some types of noises, it will still be able to work.



---

*Source: 6435320-2016-03-17.xml*