关于压缩感知中一些算法的几个问题

Compressed sensing is a new branch which involves many areas such as information theory, approximation theory, applied harmonic analysis, probility thoery, staticstical science, numerical calculation, optimization theory and discrete mathematics et. all. Its main point is, without loss any information, to use very few measurements to encoding high dimensional sparse signals. This project is to study some problems of some algorithms in compressed sensing. These algorithms are 1-norm minimization algorithm and orthogonal matching pursuit (OMP). We want to study some necessary conditions of those algorithms and the relations between those algorithms. Also, although it is very common to use random matrix as the measurement matrix, due to many advantages of non-random matrices, if it is possible, we also want do some basic research on designing some non-random matrices as the measurement matrix.

压缩感知是近年来新兴起的一门交叉学科。她涉及信息论、逼近论、应用调和分析、概率论、统计学、数值计算、运筹学和离散数学等学科。她的要点是尽可能节省地对高维稀疏信号进行采样、编码和解码。本项目计划研究关于压缩感知的一些算法中的问题。这些算法主要包括1-范数最小化算法（P1问题）和正交投影逼近（OMP）算法。研究的内容包括这些算法的一些充分条件以及它们之间是否有包含关系。另外，尽管现在熟知和通用的是用随机矩阵来做编码（测量）矩阵；但是由于确定性矩阵有很多优点，有可能的话，本项目也想初步研究确定性编码（测量）矩阵的设计。

本项目研究压缩感知中一些算法的几个问题 。压缩感知是最近十几年来的研究热点问题之一。它的核心想法是用尽量少的测量来观测高维空间中的k稀疏向量。常用的算法有1-范数最小化方法，OMP算法等。常用的算法有1-范数最小化方法，OMP算法等。常用的工具有R.I.P.常数，随机矩阵，J-L引理等工具。本项目组从R.I.P.常数这个方向入手，给出了一个OMP算法能够精确恢复k稀疏向量x的支集的紧致的RIP条件。一方面，我们证明了这个条件是充分条件； 另一方面，我们给出具体的例子，说明把这个条件再稍微放松一点都有反例。从而在某种意义下，这是一个最好而且无法再改进的结果。