稀疏性度量与稀疏信号恢复

本书系统总结了作者在稀疏统计学习与压缩感知领域的研究进展，聚焦稀疏性度量与稀疏信号恢复两大核心问题。全书共5章，首先介绍了稀疏信号恢复的基本概念、理论工具与常用算法，奠定了研究基础；接着聚焦稀疏性度量，详细讨论了可分离和不可分离两类度量方法。随后分别探讨了可分离与不可分离的非凸稀疏信号恢复方法，包括基于广义误差函数的方法、基于概率分布函数的构造方法、q-ratio稀疏性最小化、加权?r ? ?1与?p / ?1最小化等前沿成果；最后拓展至结构化、非线性及带先验信息等稀疏信号恢复问题。本书兼具理论深度与方法广度，既可为研究人员提供系统参考，也可为数学、统计学和信号处理等领域的应用探索提供借鉴。

周志永，男，博士（后），浙大城市学院计算机与计算科学学院特聘研究员。2011年本科毕业于浙江大学统计学专业，2016年获浙江大学博士学位，2016年9月至2019年5月期间在瑞典于默奥大学做博士后。主要研究方向为金融时间序列分析、压缩感知和稀疏统计学习等。累计发表SCI收录论文十余篇。现主持浙江省自然科学基金项目一项。

目 录

第 1 章 基本概念 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1 稀疏信号恢复概述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 基本问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3 理论分析工具. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.3.1 零空间性质 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.3.2 约束等距性质. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6

1.3.3 球形截面性质. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7

1.3.4 稳健宽度性质. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8

1.3.5 其他分析工具 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.4 求解算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.4.1 凸优化算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.4.2 非凸优化算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.4.3 其他算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

第 2 章 稀疏性度量. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.1 可分离的稀疏性度量. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.2 不可分离的稀疏性度量. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23

2.3 CMSV. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26

2.3.1 CMSV 的理论分析. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.3.2 几何性质 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

2.3.3 基于几何性质的恢复结果. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .39

2.3.4 随机矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

2.3.5 结构随机矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

2.3.6 数值实验 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

第 3 章 可分离的非凸稀疏信号恢复方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

3.1 常见的可分离的非凸方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

3.2 基于广义误差函数的非凸方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

3.2.1 GERF 惩罚函数的性质 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

3.2.2 近端算子 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

3.2.3 理论分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

3.2.4 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

3.2.5 数值实验 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

3.3 基于概率分布函数的构造方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

3.3.1 作为稀疏性度量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

3.3.2 次可加性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

3.3.3 渐近行为 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

3.3.4 理论分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

3.3.5 Weibull 惩罚 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

3.3.6 其他构造方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

第 4 章 不可分离的非凸稀疏信号恢复方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

4.1 q-ratio 稀疏性最小化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

4.1.1 理论分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

4.1.2 求解算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

4.1.3 数值实验 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

4.2 加权 ?r-?1 最小化. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .116

4.2.1 恢复分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

4.2.2 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

4.2.3 数值实验 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128

4.2.4 RIP 分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

4.2.5 数值实验 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

4.3 ?p/?1 最小化. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .159

4.3.1 充分条件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

4.3.2 q-ratio CMSV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162

4.3.3 RIP 分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166

4.3.4 算法和数值实验 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177

第 5 章 稀疏信号恢复拓展. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183

5.1 结构化稀疏信号恢复. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .183

5.1.1 块 q-ratio 稀疏性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184

5.1.2 块 q-ratio 稀疏性最小化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187

5.1.3 理论分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190

5.1.4 求解算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197

5.1.5 数值实验 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199

5.2 非线性稀疏信号恢复. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .202

5.2.1 SRIP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203

5.2.2 加权零空间性质 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .