Compressive Sensing Resources | Rice DSP

压缩感知理论指出:只要信号是可压缩的或在某个变换域是稀疏的,那么就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上,然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构出原信号,可以证明这样的投影包含了重构信号的足够信息。

这里分享一个Rice University关于压缩感知的资料集,以下

The dogma of signal processing maintains that a signal must be sampled at a rate at least twice its highest frequency in order to be represented without error. However, in practice, we often compress the data soon after sensing, trading off signal representation complexity (bits) for some error (consider JPEG image compression in digital cameras, for example). Clearly, this is wasteful of valuable sensing resources. Over the past few years, a new theory of “compressive sensing” has begun to emerge, in which the signal is sampled (and simultaneously compressed) at a greatly reduced rate.

As the compressive sensing research community continues to expand rapidly, it behooves us to heed Shannon’s advice.

Compressive sensing is also referred to in the literature by the terms: compressed sensing, compressive sampling, and sketching/heavy-hitters. ->完整内容

分段双调排序算法

双调排序是data-independent的排序, 即比较顺序与数据无关的排序方法, 特别适合做并行计算,例如用GPU、fpga来计算。

1、双调序列

双调序列是一个先单调递增后单调递减(或者先单调递减后单调递增)的序列。

2、Batcher定理

将任意一个长为2n的双调序列A分为等长的两半X和Y,将X中的元素与Y中的元素一一按原序比较,即a[i]与a[i+n] (i < n)比较,将较大者放入MAX序列,较小者放入MIN序列。则得到的MAX和MIN序列仍然是双调序列,并且MAX序列中的任意一个元素不小于MIN序列中的任意一个元素。

1
2
3
for (i=0;i<n;i++) {
if (get(i)>get(i+n)) exchange(i,i+n);
}

3、双调排序

假设我们有一个双调序列,则我们根据Batcher定理,将该序列划分成2个双调序列,然后继续对每个双调序列递归划分,得到更短的双调序列,直到得到的子序列长度为1为止。这时的输出序列按单调递增顺序排列。类似于归并排序。

见下图,升序排序,具体方法是,把一个序列(1…n)对半分,假设n=2^k,然后1和n/2+1比较,小的放上,接下来2和n/2+2比较,小的放上,以此类推;然后看成两个(n/2)长度的序列,因为他们都是双调序列,所以可以重复上面的过程;总共重复k轮,即最后一轮已经是长度是2的序列比较了,就可得到最终的排序结果。

Read More

调频连续波FMCW测距原理

FMCW全拼Frequency Modulated Continuous Wave,这周看的MOBICOM2016关于声信号(Acoustic Signal)跟踪手势的几篇论文中提到的一个比较重要的声波测距技术。

FMCW技术和脉冲雷达技术是两种在高精度雷达测距中使用的技术。其基本原理为,发射波为高频连续波,其频率随时间按照三角波规律变化。雷达接收的回波的频率与发射的频率变化规律相同,都是三角波规律,只是有一个时间差,利用这个微小的时间差可计算出目标距离。

我们来通过MOBICOM2016的一篇论文 CAT: High-Precision Acoustic Motion Tracking 学习一下FMCW技术的测距原理,下图摘自该篇论文。

Traditional FMCW

Read More