Compressive Sensing with Measurement Matrix Constructed by Cat Map
Yan-jie Song, Wei Zhang, Fang-da Guo, Hai Yu, Zhi-liang Zhu
Software College, Northeastern University,
No. 11, Lane 3, WenHua Road, Shenyang, Liaoning, China
Email: 1026753294@qq.com, zhangwei@swc.neu.edu.cn,
gfdyes@gmail.com, yuhai@126.com, zzl@mail.neu.edu.cn
Abstract – A new approach to construct the measurement
matrix in compressive sensing is proposed. In this
approach, a circulant matrix is first generated by a
modified cat map and a random sequence. Then it is
optimized through solving the problem of sparse
optimization and becomes the measurement matrix used in
compressive sensing. The proposed measurement matrix is
compared with the Bernoulli and chaos-based random
measurement matrices before and after optimization. The
results show that our construction method leads to a higher
reconstruction fidelity.
1. Introduction
According to the Nyquist-Shannon theorem
[1]
, a signal
cannot be exactly recovered from its discrete samples
unless the sampling frequency is at least two times the
highest signal frequency. However, this is not necessary if
some high frequency components are ignored after the
sampled signal has been compressed.
Recently, a new sampling theory called compressive
sensing (CS)
was proposed by Candes et al.
[2-5]
and
Donoho
[8]
independently. Its principle is that a smaller
measurement matrix can be used to sample a sparse signal
in order to extract the significant information of this
sparse signal only. The exact reconstruction of the sparse
signal is guaranteed if some conditions are satisfied. In
this way, the measurement matrix is far smaller than that
required by the Nyquist-Shannon theorem.
The core of CS is that sampling and compression can
be performed at the same time. The measurement matrix
used in the sampling process needs to be incoherent with
the sparse transform basis of the signal. More formally,
the Restricted Isometry Property (RIP) must be satisfied
[6]
. It is well-known that a random matrix is incoherent
with almost any matrices and it satisfies the RIP criterion
with a high probability.
According to the above criteria, various methods for
constructing the measurement matrix have been
suggested. They can be divided into three categories. The
first one includes Bernoulli random measurement
matrix
[7-9]
, very sparse random projection matrix
[10]
, etc.
The elements in these matrices are independent but follow
a certain distribution. Their size is very small but the
computational complexity is high. The second category
consists of the partial Fourier matrix
[5,11]
, non-relevant
measurement matrix
[12]
, etc. These matrices are generated
through extracting the rows of an orthogonal matrix.
These algorithms are faster than those belonging to the
first category. However, they are incoherent with most
sparse signals. The final category includes binary sparse
matrix
[13]
, structurally random matrix
[12]
, chirp
measurement matrix
[14]
, etc. This kind of matrices has a
certain kind of deterministic structure. The time required
for generating the measurement matrix and reconstructing
the original signal is shorter than that of the other two
kinds. However, the quality of the recovered signal is not
satisfactory.
In this paper, an approach for constructing a
measurement matrix having the advantages of those in the
first and the third categories is proposed. In particular, a
circulant matrix satisfying RIP is constructed using a
uniformly-distributed sequence generated by a modified
cat map. Then, the matrix is optimized to enhance the
reconstruction fidelity through solving the sparse
optimization problem.
The main contribution of this work is the establishment
of a connection between CS and the chaotic cat map. The
performance of the suggested approach with and without
optimization is compared with that of Bernoulli and
chaotic measurement matrices on the reconstruction
fidelity. The experimental results justify that the proposed
measurement matrix leads to a better reconstruction than
the other two matrices. This paper is organized as follows.
In Section II, the proposed method for constructing the
measurement matrix is introduced. The approach to
optimize the matrix generated by the modified cat map
and the property of the resultant matrix are analyzed in
Section III. Simulation results are presented in Section IV.
The final section concludes our work.
2. Construction and Optimization of Measurement
Matrix
2.1. Matrix Construction
The classic cat map was proposed by Arnold and
Avez
[15]
. It has been widely used in image encryption as it
can re-distribute all pixels of the original image to make
the image noise-like and unrecognizable. The cat map is
governed by the following equation:
1
1
1
mod
1
ii
ii
xx
a
n
yy
bab
(1)
- 389 -
2014 International Symposium on Nonlinear Theory and its Applications
NOLTA2014, Luzern, Switzerland, September 14-18, 2014