压缩感知中最优限制等距常数界

摘要

压缩感知是近十年来国际应用数学研究领域一个十分重要的热门研究方向，它涉及到函数逼近理论，统计理论，矩阵理论，以及优化理论等重要研究领域，特别是由于它在核磁共振等领域中的成功应用，以及大数据科学的迫切要求，使得该领域的研究越来越重要了。
　　限制等距性质(RIP)常数是压缩感知中的核心概念，它的重要性在于可以利用RIP常数的上界估计，将一个组合优化问题转化成一个凸优化问题。2005年E.J.Candès和T.Tao创造性的利用RIP常数的上界刻画其等价性。此项工作引起国际同行的极大关注（2006年世界数学家大会一个小时报告及45分钟报告均重点介绍了此内容）。然而，正如Candès和Tao在论文中指出的，他们的界并不是最佳的。他们指出，可以通过引用更加优美的分析技术，来优化上界。因此对最优上界的估计问题，就成了压缩感知近十年的核心问题之一。所以到目前为止，涌现了大量工作侧重于此上界估计。特别指出的是Candès证明了当δ2k＜√2-1，可以通过l1最小化模型来精确恢复k稀疏信号。之后，Tony Cai和Anru Zhang在文章[5]中证明了当4/3≤t时，δtk＜√/(t-1)/t是最优的RIP上界。同时他们猜测当0＜t＜3时，δtk＜t/4-t是最优的RIP上界。我们在本文第二章中证实了该猜测，更进一步，相似的刻画同样被用于低秩矩阵恢复。因此结合[5]，关于所有t＞0时通过l1范数最小化模型恢复所有k稀疏信号的紧的RIP常数δtk界问题得到了彻底解决。同时，我们也讨论了噪音情形和逼近稀疏情形。为了解决这个猜测，我们利用凸多面体的稀疏表示，引入了组合的方法，使得tk阶RIP条件可以被完美应用。
　　在第三章中，我们同样考虑用lp最小化(0＜p≤1)来恢复稀疏信号关于RIP上界的一致分析，这也是关于lp优化问题的一个焦点问题。到目前为止，有大量的文章优化它的上界。然而，并没有得到最优的上界估计。我们将给出一致的最优上界估计，证明了如果测量矩阵A满足RIP条件δ2k＜δ(p），然后所有k稀疏信号x可以通过带约束lp最小化来稳定恢复。更进一步，我们证明对于任何(∈)＞0，δ2k＜δ(p)+∈不能够保证恢复所有k稀疏信号。这个结果同样被应用到低秩矩阵恢复上。特别的，当p=1时，对应的常数δ(1)=√2/2，这个紧的界在文章[5]中给出了证明。
　　在大量实际应用中，许多信号并不一定在正交基表示下是稀疏的，而是在某个冗余字典表示下是稀疏的，例如在紧框架的表示下是稀疏的。其中矩阵D-RIP常数是刻画此类问题的核心概念，在第四章我们侧重于紧框架下稀疏信号的恢复问题，并且作为一个应用，我们同样解决了紧框架下的最优D-RIP上界。

目录

声明

摘要

1 引言

1．1 压缩感知经典理论

1．1．1 部分Fourier随机矩阵

1．1．2 Gaussian随机矩阵

1．1．3 Subgaussian随机矩阵

1．1．4 结构随机矩阵

1．1．5 确定性矩阵

1．2 低秩矩阵恢复

1．3 关键性引理

1．3．1 零空间条件

1．3．2 稀疏表示

1．4 本文的主要内容

2 φ1最小化模型

2．1 RIP常数δtk(0＜t＜3／4)的猜测

2．2 证明

2．2．1 引理

2．2．2 信号精确恢复定理的证明

2．2．3 带噪音信号恢复结果的证明

3 φp最小化模型

3．1 最优的RIP上界

3．1．1 推广到低秩矩阵恢复

3．2 主要定理的证明

4 最优的D-RIP上界

4．1 关于字典的稀疏信号恢复

4．2 记号和引理

4．3 精确恢复

4．4 有界噪音的恢复

参考文献

附录

作者简历

发表文章目录

致谢