Monthly Archives: June 2010

Convolution / Circulant Sampling in 1D and 2D

压缩感知(compressive sensing)在采样前“压缩”信号,从而达到减少采样的数量、时间、成本的目的。理论上,最优的(在order of magnitude和with overwhelming probability意义上)压缩感知方式之一是全随机线性投影。如果用向量x表示一个信号,那么全随机线性投影就是一个矩阵A,它的每个元素是独立的随机数(常见的服从高斯或者伯努利分布)。但是,这样的压缩方式自由度太大,因此很难在机械、物理、电子上简单地实现。然而,压缩感知的目的之一是缩小传感器的尺寸和造价,缩短采样时间。我们又知道,压缩感知必定需要某种全局形式的线性投影。因此,为了在实现中有效的进行压缩采样,我们需要一种物理或者电子上容易实现的线性投影方式,并且要求它依旧有最低的采样要求。 Toeplitz/Circulant/卷积形式的随机线性投影比较容易实现。目前,使用它们的具体工作在通信、图像、核磁共振等方面已经出现了。Toeplitz和Circulant矩阵分别是 它们与同样尺寸的高斯随机矩阵相比拥有少得多的自由度,因此也可以说它们更加得不随机。线性投影的随机性在压缩感知很重要,它极大地保证线性投影(encoding linear projection)和信号的稀疏基(sparsifying basis)之间的不一致(incoherent)。这种不一致使得信号可以从很少的采样中被还原。既然Toeplitz和Circulant矩阵比高斯矩阵更加的不随机,那么使用Toeplitz和Circulant矩阵会不会需要更多的采样呢?答案是不会。并且,如果使用了它们,信号还原的算法速度会更快。Toeplitz和Circulant矩阵的产生方法、采样点、最低的采样率、以及快速还原方法在这里有介绍(我的共同作者是Simon Morgan、杨俊峰、张寅)。我们欢迎兴趣的同行索要代码。 最近,一些同行在运行我们的2维代码之后询问我到底什么是2维Circulant Sampling,如何2D图像上实现,跟二维卷积有什么关系,等等。下面,我简单回答一下,并附上Matlab代码作为演示。 This part describes how to implement circulant sampling for both 1D signals and 2D images. It serves an orientation page for algorithms described in this work. … Continue reading

Posted in Compressive Sensing, 稀疏优化 | 5 Comments

Protected: Maintaining the constraints X^*X = I

There is no excerpt because this is a protected post.

Posted in Uncategorized