基于勒贝格积分的一种离散变换方法

作者: DarkBubble | 来源:发表于2019-03-27 06:07 被阅读0次

基于勒贝格积分原理的一种傅立叶变换算法

勒贝格原理

勒贝格积分
勒贝格积分是指是值域积分原理，具有典型的统计特征。相对于黎曼积分而言，一维勒贝格积分定义如下：
$L[f] = \int \sigma(\text{d}y, y,f)$
其中 $\sigma$ 函数是一个测度函数，计算函数 $f$ 在 $[y,y+\text{d}y]$ 区间的测度，这里的测度是简单的面积测度（ $\text{d}x\text{d}y$ ）。

离散勒贝格积分
离散情况下，勒贝格积分的计算本质上依赖于排序方法。假定积分间隔为等间隔 $1$ ，那么积分化为离散求和。首先计算出所有的离散序对 $y_i=f(x_i)$ ，然后对 $y_i$ 排序，得到 $(y_i')$ 序列。我们依次统计处于 $(y_i',y_{i+1}'$ 中的函数面积 $\sigma_i'$ 。在这个过程中需要对计算给定 $y$ 值，对应的 $x$ 区间集合 $\{x_{ij},x_{i(j+1)}\}$ 。所有区间集合的面积即 $\sum_j \Delta x_{ij} \Delta y_i$ ，其中 $\Delta y_i = y_{i+1} - y_i$ 。

线性变换

线性变换 $L[f]$ 满足 $L[af_1+bf_2] = aL[f_1]+bL[f_2]$ 。利用勒贝格积分计算离散傅立叶变换时，即对每个 $y_i$ 对应的区间集合 $\{ x_{ij},x_{i(j+1)} \}$ 进行变换。对于傅立叶变换来说，这个变换更为简单。

方波函数的傅立叶变换
方波函数 $f(t)=C, t\in[a,b]$ ，其他情况 $f(t)=0$ 。傅立叶变换对应：
$g(\omega) = \int_a^bf(t)e^{i\omega t}\text{d}t = C\int_a^be^{i\omega t}\text{d}t$
离散情况下变为求和：
$g(\omega_j) = \sum_i f(t_i) e^{i\omega_j t_i}\Delta t = \sum_{i=i_1}^{i_2}C e^{i\omega_j t_i}\Delta t$
其中 $[i_1,i_2]$ 为方波的非 $0$ 整数区间。

利用勒贝格积分原理，我们从值域处理，我们可以将离散函数分解为若干个区间 $[(x_i, y_j), (x_{i+1}, y_{j+1})]$ 的组合。实际上很多区间都是 $0$ ，我们只需要计算那些测度非零区间（即有函数区域覆盖）的傅立叶变换，将其组合求和即可。
依据该思路有两种算法

传统积分结合线性变换，即冲击响应函数方法（类似Green函数方法）。利用 $\delta$ 函数的傅立叶变换，直接用每个 $f(x_i)\delta(x_i)$ 进行线性变换后组合。
利用勒贝格积分在值域进行切割后，利用方波函数的投影快速方法加速变换。
注意：
速度较快的关键在于：对 $sum_i e^{i\omega t_i}$ 求和时，直接使用等比数列求和算法。
决定该算法的关键在于快速找到每个值域区间对应的定义域区间对。
当该信号类似于中心频率零频高斯脉冲时，效率极高，因为每个值域区间恰好仅仅只有一个连续定义域区间。满足该条件时，速度比 $FFT$ 快。
排序算法不需要浮点计算效率很高。与FFT同是 $O(n\log n)$ 时，时间系数更小。
需要快速扫描线算法，找到切割的定义域区间。可以利用导数信息快速求得相应的区间。原则上该算法的复杂性应当也是 $O(n\log n)$ 。同样不需要浮点运算。
求和的时间复杂性为 $O(n)$
浮点乘法和三角函数计算的复杂性与区间的多少相关。
和FFT一样，$$