﻿ 压缩感知中测量矩阵构造综述
 计算机应用   2017, Vol. 37 Issue (1): 188-196  DOI: 10.11772/j.issn.1001-9081.2017.01.0188 0

### 引用本文

WANG Qiang, ZHANG Peilin, WANG Huaiguang, YANG Wangcan, CHEN Yanlong. Survey on construction of measurement matrices in compressive sensing[J]. JOURNAL OF COMPUTER APPLICATIONS, 2017, 37(1): 188-196. DOI: 10.11772/j.issn.1001-9081.2017.01.0188.

### 文章历史

Survey on construction of measurement matrices in compressive sensing
WANG Qiang, ZHANG Peilin, WANG Huaiguang, YANG Wangcan, CHEN Yanlong
Department of Vehicles and Electrical Engineering, Ordnance Engineering College, Shijiazhuang Hebei 050003, China
Abstract: The construction of measurement matrix in compressive sensing varies widely and is on the development constantly. In order to sort out the research results and acquire the development trend of measurement matrix, the process of measurement matrix construction was introduced systematically. Firstly, compared with the traditional signal acquisition theory, the advantages of high resource utilization and small storage space were expounded. Secondly, on the basis of the framework of compressive sensing and focusing on four aspects:the construction principle, the generation method, the structure design of measurement matrix and the optimal method, the construction of measurement matrix in compressive sensing was summarized, and advantages of different principles, generations and structures were introduced in detail. Finally, based on the research results, the development directions of measurement matrix were prospected.
Key words: Compressive Sensing (CS)    measurement matrix    Restricted Isometry Property (RIP)    signal reconstruction    signal acquisition
0 引言

1 压缩感知理论模型

 $x=\sum\limits_{i=1}^{N}{{{s}_{i}}{{\psi }_{i}}}$ (1)

 ${{\mathrm{s}}_{i}}=\left\langle x,\left. {{\mathrm{ }\!\!\psi\!\!\text{ }}_{i}} \right\rangle \right.=\mathrm{ }\!\!\psi\!\!\text{ }_{^{i}}^{\text{T}}\mathrm{x}$ (2)

 $\mathrm{y}=\mathrm{ }\!\!\Phi\!\!\text{ x}=\mathrm{ }\!\!\Phi\!\!\text{ }\!\!\psi\!\!\text{ s}=\mathrm{ }\!\!\Theta\!\!\text{ s}$ (3)

 图 1 信号获取与传输 Figure 1 Signals acquisition and transmission

2 测量矩阵构造原则

 图 2 压缩感知测量过程 Figure 2 Measurement process of compressive sensing

 图 3 稀疏信号压缩感知 Figure 3 Compressive sensing for sparse signals
2.1 RIP 2.1.1 RIC

 $(1-{{\delta }_{K}})\left\| \mathrm{x} \right\|_{{{l}_{2}}}^{2}\le \left\| \mathrm{ }\!\!\Phi\!\!\text{ x} \right\|_{{{l}_{2}}}^{2}\le (1+{{\delta }_{K}})\left\| \mathrm{x} \right\|_{{{l}_{2}}}^{2}$ (4)

 $(1-{{\delta }_{K}})\left\| \mathrm{x} \right\|_{{{l}_{2}}}^{2}\le \left\| \mathrm{ }\!\!\Theta\!\!\text{ x} \right\|_{{{l}_{2}}}^{2}\le (1+{{\delta }_{K}})\left\| \mathrm{x} \right\|_{{{l}_{2}}}^{2}$ (5)

 $(1-{{\delta }_{2K}})\left\| \mathrm{c} \right\|_{{{l}_{2}}}^{2}\le \left\| {{\mathrm{ }\!\!\Phi\!\!\text{ }}_{\mathrm{T}}}\mathrm{c} \right\|_{{{l}_{2}}}^{2}\le (1+{{\delta }_{2K}})\left\| \mathrm{c} \right\|_{{{l}_{2}}}^{2}$ (6)

 $(1-{{\delta }_{2K}})\left\| \mathrm{c} \right\|_{{{l}_{2}}}^{2}\le \left\| {{\mathrm{ }\!\!\Theta\!\!\text{ }}_{\mathrm{T}}}\mathrm{c} \right\|_{{{l}_{2}}}^{2}\le (1+{{\delta }_{2K}})\left\| \mathrm{c} \right\|_{{{l}_{2}}}^{2}$ (7)
2.1.2 RIP的条件描述

RIC的计算是RIP分析的基础，对于可压缩信号，若在信号的稀疏域(时域稀疏信号稀疏域为单位阵I)内：稀疏信号的非零元素位置已知，则在满足0＜δK＜1的条件下，称测量矩阵具有RIP，能够满足信号精确重构的要求；若稀疏域内非零元素位置未知，则在满足δ2K﹤2-1的条件下，原始信号能够被精确重构[11]

RIP通过限制观测矩阵，保证了不同信号在压缩观测后能够映射到不同的集合，同时充分保留原始信号的特性，因此能够保证原始信号的唯一精确重构。RIP的提出，是压缩感知理论上的重要突破：一方面在满足RIP的条件下，远低于奈奎斯特采样定理的信号采样存在精确重构的可能，为压缩感知理论提供基础；另一方面，RIP能够指导测量矩阵的构造，成为部分矩阵构造是否合理的评判标准。文献[20]通过Johnson-Lindenstrauss引理[21]证明，许多密集随机矩阵都能够满足RIP，保证了压缩感知重构效果。

2.2 RIP1性质

 $(1-2\varepsilon )d{{\left\| \mathrm{x} \right\|}_{1}}\le {{\left\| \mathrm{ }\!\!\Phi\!\!\text{ x} \right\|}_{1}}\le d{{\left\| \mathrm{x} \right\|}_{1}}$ (8)

RIP1性质是RIP的扩展，二者在本质上保持着一致性。RIP1通过扩展欧几里得空间至曼哈顿空间，丰富了RIP的应用范围，建立了膨胀图与压缩感知之间的联系，为边膨胀图的确定性矩阵构造方式提供依据。同时，进一步揭示了RIP的实质，即通过保证压缩观测过程保留原始信号在欧几里得空间的基本特性，保证原始信号具有精确重构的可能。

2.3 列相干性

Tropp[27]提出，在冗余字典满足特定列相干性条件的情况下，基追踪(Basis Pursuit,BP)、正交匹配追踪(Orthogonal Matching Pursuit,OMP)等追踪算法能够对原始信号实现准确的稀疏近似。在此基础上，Donoho等[26]将这一结论应用到压缩感知矩阵优化中，作为测量矩阵优化标准，提出了基于列相干性的测量矩阵构造原则。

 \left\{ \begin{align} & \mu \text{=}\underset{i\ne j}{\mathop{\max }}\,\left| \left\langle {{\mathrm{ }\!\!\psi\!\!\text{ }}_{i}},{{\mathrm{ }\!\!\psi\!\!\text{ }}_{j}} \right\rangle \right| \\ & {{\mu }_{1}}\text{(}K\text{)=}\underset{\left| \Lambda \right|=K,j\notin \Lambda }{\mathop{\max }}\,\sum\limits_{i\in \Lambda }{\left| \left\langle {{\mathrm{ }\!\!\psi\!\!\text{ }}_{i}},{{\mathrm{ }\!\!\psi\!\!\text{ }}_{j}} \right\rangle \right|} \\ \end{align} \right. (9)

 $\mu \ge \sqrt{\left( N-M \right)/\left[ (N-1)M \right]}$ (10)

 $\mathrm{x}\text{=}\mathrm{ }\!\!\psi\!\!\text{ s}$ (11)

 ${{\left\| \mathrm{s} \right\|}_{0}}＜\frac{1}{2}\left( 1+\frac{1}{\mu \left\{ \mathrm{ }\!\!\Theta\!\!\text{ } \right\}} \right)$ (12)

 ${{\delta }_{K}}\le {{\mu }_{1}}(K-1)\le (K-1)\centerdot \mu$ (13)

2.4 StRIP/UStRIP性质

 $(1-\varepsilon ){{\left\| \mathrm{x} \right\|}^{2}}\le {{\left\| \mathrm{ }\!\!\Phi\!\!\text{ x}/M \right\|}^{2}}\le (1+\varepsilon ){{\left\| \mathrm{x} \right\|}^{2}}$ (14)

Φ为(K，ε，δ)-StRIP矩阵。

 $\left\{ \mathrm{ }\!\!\beta\!\!\text{ }\!\!|\!\!\text{ }\!\!\beta\!\!\text{ }\in {{R}^{N}};\mathrm{ }\!\!\Phi\!\!\text{ }\!\!\alpha\!\!\text{ }=\mathrm{ }\!\!\Phi\!\!\text{ }\!\!\beta\!\!\text{ } \right\}$ (15)

Φ为(K，ε，δ)-UStRIP矩阵。

1) Φ任意行向量正交，并且行元素求和为零。即：

 $\sum\limits_{j=1}^{N}{{{\mathrm{ }\!\!\Phi\!\!\text{ }}_{j}}(a)}\overline{{{\mathrm{ }\!\!\Phi\!\!\text{ }}_{j}}(b)}=0;a\ne b$ (16)
 $\sum\limits_{j=1}^{N}{{{\Phi }_{j}}(a)}=0$ (17)

2) Φ的任意列向量满足“逐点相乘”，即对于任意列向量Φj″(a)(j″∈｛1,2，…，N｝)，存在不同的列索引j，j′，对任意x满足：

 ${{\mathrm{ }\!\!\Phi\!\!\text{ }}_{{{j}^{\prime \prime }}}}(a)={{\mathrm{ }\!\!\Phi\!\!\text{ }}_{{{j}^{\prime }}}}(a){{\mathrm{ }\!\!\Phi\!\!\text{ }}_{j}}(a)$ (18)

3) 对任意j∈｛2，…，N｝满足：

 ${{\left| \sum\limits_{x}{{{\Phi }_{j}}(a)} \right|}^{2}}\le {{M}^{2-\eta }}$ (19)

StRIP/UStRIP性质通过缩小测量矩阵的应用对象，简化了测量矩阵的评价条件，降低了测量矩阵性质的检验难度。对于满足条件的稀疏信号而言，简单的评价条件具有与RIP类似的性质，能够保证测量矩阵在压缩观测过程中充分保留原始信号的有用信息，从而保证原始信号的唯一精确重构。

3 测量矩阵产生方法

3.1 随机测量矩阵 3.1.1 高斯随机矩阵

Candes等[2]证明，独立同分布于高斯正态分布的高斯矩阵，在K≤O(M log N)的条件下，能够以很高的概率满足RIP[18]，因此作为测量矩阵对K-稀疏信号进行压缩采样后，能够以很高的概率实现原始信号的精确重构。

 ${\Phi _{i,j}} \sim {\rm N}(0,1/M)$ (20)

3.1.2 贝努力随机矩阵

 {{\Phi }_{i,j}}=\left\{ \begin{align} & 1/\sqrt{M}\begin{matrix} , & {{P}_{1}}=1/2 \\ \end{matrix} \\ & -1/\sqrt{M}\begin{matrix} , & {{P}_{2}}=1/2 \\ \end{matrix} \\ \end{align} \right. (21)

3.2 确定性测量矩阵 3.2.1 边膨胀图邻接矩阵

Xu等[22]提出利用非平衡二部图(如图 4)邻接矩阵作为测量矩阵，应用于压缩观测过程。非平衡二部图直接模拟了压缩感知压缩观测过程，其图形分为左右两部分，左子图定义为A1，右子图定义为A2，图中包含有两种节点。根据编码理论的数值描述，将A1中节点定义为可变节点，A2中节点定义为奇偶校验节点。A1节点个数为N，对应于压缩感知原始信号x；A2节点个数为M，对应于压缩观测后信号y。假设M≤N，A1、A2节点之间有边线连接，连接关系对应于邻接矩阵C：

 {{C}_{ij}}=\left\{ \begin{align} & 1\begin{matrix} , & 右i节点与左j节点链接 \\ \end{matrix} \\ & 0\begin{matrix} , & 其他 \\ \end{matrix} \\ \end{align} \right. (22)
 图 4 (k，ε)-边膨胀图 Figure 4 (k，ε)-expander graph

Jarfarpour等[25]指出，在1≤K≤N/2的情况下，若(K，ε)-边膨胀图存在左子图的度d以及右子图大小M为：

 \left\{ \begin{align} & d=O\left( \lg \left( N/K \right)\varepsilon \right) \\ & M=OO\left( \lg \left( N/K \right){{\varepsilon }^{2}} \right) \\ \end{align} \right. (23)

3.2.2 多项式确定性矩阵

 ${{\mathrm{P}}_{r}}=\left\{ Q\left( t \right)={{a}_{0}}+{{a}_{1}}t+\cdots +{{a}_{n}}{{t}^{r}}\left| {{a}_{n}}\in \mathrm{F} \right. \right\}$ (24)

Pr中多项式的个数为pr+1，对于任意Q∈Pr，把Q当作FF的映射函数，则E为t→Q(t)的映射矩阵，满足：

 $Q(t)=\mathrm{E}{{t}^{*}}$ (25)

 $\left( {\begin{array}{*{20}{c}} {\left( {0,0} \right)} & {\begin{array}{*{20}{c}} {\left( {0,1} \right)} & \ldots \end{array}} & {\left( {0,p - 1} \right)} \\ \begin{gathered} \left( {1,0} \right) \hfill \\ \vdots \hfill \\ \end{gathered} & \begin{gathered} \begin{array}{*{20}{c}} {\left( {1,1} \right)} & \cdots \end{array} \hfill \\ \begin{array}{*{20}{c}} \vdots & {\begin{array}{*{20}{c}} {} & \vdots \end{array}} \end{array} \hfill \\ \end{gathered} & \begin{gathered} \left( {1,p - 1} \right) \hfill \\ \vdots \hfill \\ \end{gathered} \\ {\left( {p - 1,0} \right)} & {\begin{array}{*{20}{c}} {\left( {p - 1,1} \right)} & \cdots \end{array}} & {\left( {p - 1,p - 1} \right)} \end{array}} \right)$ (26)

Devore[35]证明，按照上述方式构造的确定性矩阵在稀疏信号稀疏度K＜p/r+1的条件下，RIC δK=(K-1) r/p，满足RIP，能够保证原始稀疏信号的精确重构。

3.2.3 编码矩阵

Nam等[36]提出利用正交光码(Optical Orthogonal Code,OOC)构造压缩感知确定性矩阵，光正交码的构造由Brickell等[37]提出，广泛应用在光线信道的码分多址信道设计，Nam等[36]通过OOC的循环位移以及哈达玛矩阵的嵌套，构造了一个三元实数矩阵，并证明了其优越性能，OOC定义如下。

 $\forall \tau \in \left[ 0,n-1 \right],{{\theta }_{{{\mathrm{v}}^{(i)}},{{\mathrm{v}}^{(j)}}}}(\tau )\le \lambda ;\tau =0,若i=j$ (27)
 ${{\theta }_{{{\mathrm{s}}^{(i)}},{{\mathrm{s}}^{(j)}}}}(\tau )=\sum\limits_{t=0}^{n-1}{\mathrm{v}_{t}^{^{(i)}}\mathrm{v}_{t\oplus \tau }^{^{(j)}}}$ (28)

1) 生成S个0-1序列v(i)(0≤i≤n-1) ，属于(n,ω,λ)OOC码，将每一序列v(i)进行循环位移，共产生nS个序列，每一序列作为矩阵B的列向量。

2) 构造v×v(v=ω+δ,0≤δ≤ω)哈达玛矩阵H，对于B的每一列，将元素1用H中不同的行替换，将元素0扩展成长度为v的行，元素均为0，生成n×vnS矩阵Be

3) 对矩阵进行标准化，生成测量矩阵$D=\left( 1/\sqrt{\omega } \right)B$。

4 测量矩阵结构设计

4.1 托普利兹轮换矩阵

 $U=\left[ \begin{matrix} \begin{matrix} {{u}_{n}}\begin{matrix} {} \\ \end{matrix} & {{u}_{n-1}} & \cdots & {{u}_{2}} & {{u}_{1}} \\ \end{matrix} \\ \begin{matrix} {{u}_{1}}\begin{matrix} {} \\ \end{matrix} & {{u}_{n}}\begin{matrix} {} \\ \end{matrix} & \cdots & {{u}_{3}} & {{u}_{2}} \\ \end{matrix} \\ \begin{matrix} \vdots & \begin{matrix} \begin{matrix} {} \\ \end{matrix} \\ \end{matrix}\vdots & \begin{matrix} {} \\ \end{matrix}\vdots & \begin{matrix} {} \\ \end{matrix}\vdots & \begin{matrix} {} \\ \end{matrix}\vdots \\ \end{matrix} \\ \begin{matrix} {{u}_{m-1}} & {{u}_{m-2}} & \cdots & \cdots & {{u}_{m}} \\ \end{matrix} \\ \end{matrix} \right]$ (29)

Bajwa等[44]提出，当矩阵中元素独立服从特定P(u)，且M≥K3 ln(N/K)时，存在3K阶RIC δ3K∈(0,1/3) ，满足RIP。

4.2 分块矩阵

 $\left[ \begin{array}{*{35}{l}} {{y}_{1}} \\ {{y}_{2}} \\ \vdots \\ {{y}_{M}} \\ \end{array} \right]=\underbrace{\left[ \begin{array}{*{35}{l}} {{\Phi }_{1}} & {} & {} & {} \\ {} & {{\Phi }_{2}} & {} & {} \\ {} & {} & \ddots & {} \\ {} & {} & {} & {{\Phi }_{j}} \\ \end{array} \right]}_{\Phi }\left[ \begin{array}{*{35}{l}} {{x}_{1}} \\ {{x}_{2}} \\ \vdots \\ {{x}_{N}} \\ \end{array} \right]$ (30)

4.3 嵌套矩阵

 图 5 嵌套矩阵 Figure 5 Nested matrices

5 测量矩阵优化方法

5.1 基于Gram的优化算法

 $\mu (\mathrm{ }\!\!\Theta\!\!\text{ })=\underset{i\ne j}{\mathop{\max }}\,\left| \left\langle {{\mathrm{ }\!\!\Theta\!\!\text{ }}_{i}},{{\mathrm{ }\!\!\Theta\!\!\text{ }}_{j}} \right\rangle \right|$ (31)

 $\mathrm{ }\!\!\Xi\!\!\text{ }={{\mathrm{ }\!\!\Theta\!\!\text{ }}^{\operatorname{T}}}\mathrm{ }\!\!\Theta\!\!\text{ }$ (32)

 {{\Xi }_{ij}}'=\left\{ \begin{align} & \gamma {{\Xi }_{ij}}\begin{matrix} {} & , & {{\Xi }_{ij}}\ge th \\ \end{matrix} \\ & \gamma \operatorname{sign}({{\Xi }_{ij}})\begin{matrix} , & th\ge {{\Xi }_{ij}}\ge \gamma th \\ \end{matrix} \\ & {{\Xi }_{ij}}\begin{matrix} {} & , & {{\Xi }_{ij}}\le \gamma th \\ \end{matrix} \\ \end{align} \right. (33)

 $\mathrm{ }\!\!\Xi\!\!\text{ }={{\mathrm{ }\!\!\Psi\!\!\text{ }}^{\operatorname{T}}}{{\mathrm{ }\!\!\Phi\!\!\text{ }}^{\operatorname{T}}}\mathrm{ }\!\!\Phi\!\!\text{ }\!\!\Psi\!\!\text{ =I}$ (34)

 $\mathrm{ }\!\!\Psi\!\!\text{ }{{\mathrm{ }\!\!\Psi\!\!\text{ }}^{\operatorname{T}}}{{\mathrm{ }\!\!\Phi\!\!\text{ }}^{\operatorname{T}}}\mathrm{ }\!\!\Phi\!\!\text{ }\!\!\Psi\!\!\text{ }{{\mathrm{ }\!\!\Psi\!\!\text{ }}^{\operatorname{T}}}=\mathrm{ }\!\!\Psi\!\!\text{ }{{\mathrm{ }\!\!\Psi\!\!\text{ }}^{\operatorname{T}}}$ (35)

ΨΨT进行奇异值分解，U＇ΛU＇T=ΨΨT，令Γ=ΦU＇，则：

 $\underset{\mathrm{ }\!\!\Gamma\!\!\text{ }}{\mathop{\min }}\,\left\| \Lambda {{\mathrm{ }\!\!\Gamma\!\!\text{ }}^{\operatorname{T}}}\mathrm{ }\!\!\Gamma\!\!\text{ }\Lambda -\mathrm{ }\!\!\Lambda\!\!\text{ } \right\|_{F}^{2}$ (36)

5.2 联合优化算法

1) 初始化稀疏字典Ψ

2) 固定稀疏字典Ψ，采用基于Gram矩阵的优化方法，初始化测量矩阵Φ

3) 固定感知因子Θ，利用OMP算法求得稀疏分解系数矩阵。

4) 利用K-SVD算法实现稀疏字典Ψ与测量矩阵Φ的迭代更新，直至满足迭代条件。

6 测量矩阵构造发展方向探讨

1) 在测量矩阵构造原则上，RIP是测量矩阵设计的必要条件，但是无法有效指导测量矩阵构造，列相干性条件与RIP存在一致性，其计算简单、指导性强，并且基于列相干性条件的矩阵训练方法被证明能够用来优化测量矩阵，因此列相干性条件在具体指导测量矩阵构造中将发挥越来越大的作用；另一方面J-R引理在证明矩阵RIP上体现出巨大优势，因此其作为评价矩阵优劣的简单途径，将得到广泛应用。

2) 在测量矩阵产生方法上，确定性矩阵无疑将成为研究热点，现有确定性矩阵在部分信号的重构精度以及普遍适用性上与随机矩阵稍显不足，但是其构造复杂度低、硬件实现简单，已经得到学者的广泛关注，因此在保证重构精度的基础上，更加适用、简单的确定性矩阵是测量矩阵产生方法的发展趋势。

3) 测量矩阵结构设计能够弥补不同测量矩阵产生方法的不足，从而起到优化测量矩阵的作用，现阶段，矩阵结构设计方法相对较少，理论基础相对薄弱，因此针对测量矩阵的结构设计方法有待于进一步完善，相应的理论有待于进一步研究。

4) 对于按照特定方式构造的测量矩阵，矩阵优化方法是对其性能的一种完善，能够进一步改善测量矩阵压缩观测效果。随着自适应稀疏分解算法的不断成熟，测量矩阵与稀疏字典联合优化的方法将得到越来越多的重视，并逐渐体现出单一测量矩阵优化所不具有的优化效果。但由于现有联合优化算法的复杂度较高，联合优化算法仍处于理论研究阶段，因此未来高效率的联合优化算法将成为学者们的研究热点。

7 结语

 [1] CANDES E J, ROMBERG J. Quantitative robust uncertainty principles and optimally sparse decompositions[J]. Foundation of Computational Mathematics, 2006, 6 (2) : 227-254. doi: 10.1007/s10208-004-0162-x [2] CANDES E J, ROMBERG J K, TAO T. Robust uncertainty principles:exact signal reconstruction from high incomplete frequency information[J]. IEEE Transactions on Information Theory, 2006, 52 (2) : 489-509. doi: 10.1109/TIT.2005.862083 [3] CANDES E J, ROMBERG J K, TAO T. Stable signal recovery from incomplete and inaccurate measurements[J]. Communications on Pure and Applied Mathematics, 2006, 59 (8) : 1207-1223. doi: 10.1002/(ISSN)1097-0312 [4] BOUCHHIMA B, AMARA R, ALOUANE T H. Design of optimal matrices for compressive sensing:application to environmental sounds[C]//Proceedings of the 2015 Signal Processing Conference. Piscataway, NJ:IEEE, 2015:130-134. [5] DONOHO D L. Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52 (4) : 1289-1306. doi: 10.1109/TIT.2006.871582 [6] 王强, 李佳, 沈毅. 压缩感知中确定性测量矩阵构造算法综述[J]. 电子学报, 2013, 41 (10) : 2041-2050. ( WANG Q, LI J, SHEN Y. A survey on deterministic measurement matrix construction algorithms in compressive sensing[J]. Acta Electronica Sinica, 2013, 41 (10) : 2041-2050. ) [7] 焦李成, 杨淑媛, 刘芳, 等. 压缩感知回顾与展望[J]. 电子学报, 2011, 39 (7) : 1651-1662. ( JIAO L C, YANG S Y, LIU F, et al. Development and prospect of compressive sensing[J]. Acta Electronica Sinica, 2011, 39 (7) : 1651-1662. ) [8] ELAD M, AHARON M. Image denoising via sparse and redundant representations over learned dictionaries[J]. IEEE Transactions on Information Theory, 2006, 15 (12) : 3736-3745. [9] AHARON M, ELAD M, BRUCKSTEIN A M. The K-SVD:an algorithm for designing of overcomplete dictionaries for sparse representations[J]. IEEE Transactions on Image Processing, 2006, 54 (11) : 4311-4322. doi: 10.1109/TSP.2006.881199 [10] CANDES E J, TAO T. Decoding by linear programming[J]. IEEE Transactions on Information Theory, 2005, 51 (12) : 4203-4215. doi: 10.1109/TIT.2005.858979 [11] CANDES E J. The restricted isometry property and its implication for compressed sensing[J]. Comtes Rendus Mathematique, 2008, 346 (9/10) : 589-592. [12] MALLAT S, ZHANG Z F. Matching pursuits with time frequency dictionaries[J]. IEEE Transactions on Signal Processing, 1993, 41 (12) : 3397-3415. doi: 10.1109/78.258082 [13] TROPP J A, GILBERT A C. Signal recovery from random measurement via orthogonal matching pursuit[J]. IEEE Transactions on Information Theory, 2007, 53 (12) : 4655-4666. doi: 10.1109/TIT.2007.909108 [14] NEEDELL D, TROPP J A. CoSaMP:iterative signal recovery from incomplete and inaccurate samples[J]. Applied and Computational Harmonic Analysis, 2008, 26 (3) : 301-321. [15] CHEN S B, DONOHO D L, SAUNDERS M A. Atomic decomposition by basis pursuit[J]. SIAM Journal on Scientific Computing, 1998, 20 (1) : 33-61. doi: 10.1137/S1064827596304010 [16] APPLEBAUM L, HOWARD S, SEARLE S, et al. Chirp sensing codes:deterministic compressed sensing measurements for fast recovery[J]. Applied and Computational Harmonic Analysis, 2009, 26 (2) : 283-290. doi: 10.1016/j.acha.2008.08.002 [17] ROMBERG J. Compressive sensing by random convolution[J]. SIAM Journal on Imaging Sciences, 2009, 2 (4) : 1098-1128. doi: 10.1137/08072975X [18] CANDES E J, TAO T. Near-optimal signal recovery from random projections:universal encoding strategies?[J]. IEEE Transactions on Information Theory, 2006, 52 (12) : 5406-5425. doi: 10.1109/TIT.2006.885507 [19] ARMIN E, LUN Y H, CHRISTOPHER J R, et al. The restricted isometry property for random block diagonal matrices[J]. Applied & Computational Harmonic Analysis, 2015, 38 (1) : 1-31. [20] BARANIUK R, DAVENPORT M, DEVORE R, et al. A simple proof of the restricted isometry property for random matrices[J]. Constructive Approximation, 2008, 28 (3) : 253-263. doi: 10.1007/s00365-007-9003-x [21] JOHNSON W, LINDENSTRAUSS J. Extensions of Lipschitz maps into a Hilbert space[J]. Contemporary Mathematics, 1984, 26 : 189-206. doi: 10.1090/conm/026 [22] XU W, HASSIBI B. Efficient compressive sensing with deterministic guarantees using expander graphs[C]//ITW'07:Proceedings of the 2007 Information Theory Workshop. Piscataway, NJ:IEEE, 2007:414-419. [23] BERINDE R, GILBERT A C, INDYK P, et al. Combining geometry and combinatorics:a unified approach to sparse signal[EB/OL].[2016-05-15] . https://arxiv.org/abs/0804.4666. [24] CALDERBANK R, HOWARD S, JAFARPOUR S. Construction of a large class of deterministic sensing matrices that satisfy a statistical isometry property[J]. IEEE Journal of Selected Topics in Signal Processing, 2010, 4 (2) : 358-374. doi: 10.1109/JSTSP.2010.2043161 [25] RAGINSKY M, JAFARPOUR S, HARMANY Z T, et al. Performance bounds for expander-based compressed sensing in Poisson noise[J]. IEEE Transactions on Signal Processing, 2011, 59 (9) : 4139-4153. doi: 10.1109/TSP.2011.2157913 [26] DONOHO D L, ELAD M. Optimally sparse representation in general(nonorthogonal) dictionaries via l1 minimization[J]. Proceedings of the National Academy of Sciences, 2003, 100 (5) : 2197-202. doi: 10.1073/pnas.0437847100 [27] TROPP J A. Greed is good:algorithmic results for sparse approximation[J]. IEEE Transactions on Information Theory, 2004, 50 (10) : 2231-2242. doi: 10.1109/TIT.2004.834793 [28] RAUHUT H, SCHNASS K, VANDERGHEYNST P. Compressed sensing and redundant dictionaries[J]. IEEE Transactions on Information Theory, 2008, 54 (5) : 2210-2219. doi: 10.1109/TIT.2008.920190 [29] ELAD M, BRUCKSTEIN A M. A generalized uncertainty principle and sparse representation in pairs bases[J]. IEEE Transactions on Information Theory, 2002, 48 (9) : 2558-2567. doi: 10.1109/TIT.2002.801410 [30] KASHIN B S, TEMLYAKOV V N. A remark on compressed sensing[J]. Mathematics and Statistics, 2007, 42 (5/6) : 748-755. [31] ZHANG G, JIAO S, XU X, et al. Compressed sensing and reconstruction with Bernoulli matrices[C]//Proceedings of the 2010 International Conference on Information and Automation. Piscataway, NJ:IEEE, 2010:455-460 [32] GILBERT A C, GUHA S, INDYK P. Near-optimal sparse Fourier representation via sampling[C]//Proceedings on the 34th Annual ACM Symposium on Theory of Computing. New York:ACM, 2006:152-161. [33] BERINDE R, INDYK P. Sparse recovery using sparse random matrices[C]//LATIN 2010:Proceedings of the 9th Latin American Symposium on Theoretical Informatics, LNCS 6034. Berlin:Springer, 2010:157-157. [34] ZENG L, ZHANG X, CHEN L, et al. Deterministic Construction of Toeplitzed Structurally Chaotic Matrix for Compressed Sensing[J]. Circuits, Systems, and Signal Processing, 2015, 34 (3) : 797-813. doi: 10.1007/s00034-014-9873-7 [35] DEVORE R A. Deterministic construction of compressed sensing[J]. Journal of Complexity, 2007, 23 (4/5/6) : 918-925. [36] NAM Y Y, NA Z. Deterministic construction of real-valued ternary sensing matrices using optical orthogonal codes[J]. IEEE Signal Processing Letters, 2013, 20 (11) : 1106-1109. doi: 10.1109/LSP.2013.2281597 [37] BRICKELL E F, WEI V K. Optical orthogonal codes and cyclic block designs[J]. Congr NumerCongressus Numerantium, 1987, 58 : 175-192. [38] AMINI A, MONTAZERHODJAT V, MARVASTI F. Matrices with small coherence using parry block codes[J]. IEEE Transactions on Signal Processing, 2012, 60 (1) : 172-181. doi: 10.1109/TSP.2011.2169249 [39] LI S X, GAO F, GE G N, et al. Deterministic construction of compressed sensing matrices via algebraic curves[J]. IEEE Transactions on Information Theory, 2012, 58 (8) : 5035-5041. doi: 10.1109/TIT.2012.2196256 [40] GE X, XIA S T. LDPC codes based on Berlekamp-Justesen codes with large stopping distances[C]//ITW'06:Proceedings of the 2006 IEEE Information Theory Workshop. Piscataway, NJ:IEEE, 2006:214-218. [41] DIMAKIS A G, SMARANDACHE R, VONTOBEL P O. LDPC codes for compressed sensing[J]. IEEE Transactions on Information Theory, 2010, 58 (5) : 3093-3114. [42] DO T T, TRAN T D, LU G. Fast compressive sampling with structurally random matrices[C]//Proceedings of the 2008 IEEE International Conference on Acoustics. Piscataway, NJ:IEEE, 2008:3369-3372. [43] 李浩.用于压缩感知的确定性测量矩阵研究[D].北京:北京交通大学,2011:26-38. ( LI H. Research on deterministic measurement matrix for compressed sensing[D]. Beijing:Beijing Jiaotong University, 2011:26-38. ) [44] BAJWA W U, HAUPT J D, RAZ G M, et al. Toeplitz-structured compressed sensing matrices[C]//SSP' 07:Proceedings of the 2007 IEEE/SP 14th Workshop on Statistical Signal Processing. Washington, DC:IEEE Computer Society, 2007:294-298. [45] SALIGRAMA V. Deterministic designs with deterministic guarantees:Toeplitz compressed sensing matrices, sequence design and system ID[J]. IEEE Transactions on Information Theory, 2012, 99 (PP) : 1-1. [46] SEBERT F, ZOU Y M, YING L. Toeplitz block matrices in compressed sensing and their applications in imagine[C]//Proceedings of the 2008 International Conference on Information Technology and Applications in Biomedicine, Piscataway, NJ:IEEE, 2008:47-50. [47] SUN J M, WANG S, DONG Y. Sparse block circulant matrices for compressed sensing[J]. IET Communications, 2013, 7 (13) : 1412-1418. doi: 10.1049/iet-com.2013.0030 [48] 夏树涛, 刘璐, 刘鑫吉. 基于Berlekamp-Justesen码的压缩感知确定性测量矩阵的构造[J]. 电子与信息学报, 2015, 37 (4) : 763-769. ( XIA S T, LIU L, LIU X J. Deterministic constructions of compressive sensing matrices based on Berlekamp-Justesen codes[J]. Journal of Electronics & Information Technology, 2015, 37 (4) : 763-769. ) [49] ELAD M. Optimized projections for compressed sensing[J]. IEEE Transactions on Signal Processing, 2007, 55 (12) : 5695-5702. doi: 10.1109/TSP.2007.900760 [50] 张劲东, 张弓, 潘汇, 等. 基于滤波器结构的压缩感知雷达感知矩阵优化[J]. 航空学报, 2013, 34 (4) : 866-868. ( ZHANG J D, ZHANG G, PAN H, et al. Optimized sensing matrix design of filter structure based compressed sensing radar[J]. Acta Aeeronautica et Astronautica Sinica, 2013, 34 (4) : 866-868. ) [51] LI B, SHEN Y, LI J. Dictionaries construction using alternating projection method in compressive sensing[J]. IEEE Signal Processing Letters, 2011, 18 (11) : 662-666. [52] 赵瑞珍, 秦周, 胡绍海, 等. 一种特征值分解的测量矩阵优化方法[J]. 信号处理, 2012, 38 (5) : 654-656. ( ZHAO R Z, QIN Z, HU S H, et al. An optimization method for measurement matrix based on eigenvalue decomposition[J]. Signal Processing, 2012, 38 (5) : 654-656. ) [53] DUARTE-CARVAJALINO J M, SAPIRO G. Learning to sense sparse signal:simultaneous sensing matrix and sparsifying dictionary optimization[J]. IEEE Transactions on Imagine Processing, 2009, 18 (7) : 1395-1408. doi: 10.1109/TIP.2009.2022459 [54] ABOLGHASEMI V, SAIDEH F, BAHADOR M. On optimization of the measurement matrix for compressive sensing[C]//EUSIPCO 2010:Proceedings of the 18th European Signal Processing Conference, 2010:23-27. [55] ZHANG J D, ZHU D Y, ZHANG G. Adaptive compressed sensing radar oriented towards cognitive detection in dynamic sparse target scene[J]. IEEE Transactions on Signal Processing, 2012, 60 (4) : 1718-1729. doi: 10.1109/TSP.2012.2183127