基于勒贝格积分原理的一种傅立叶变换算法
勒贝格原理
勒贝格积分
勒贝格积分是指是值域积分原理，具有典型的统计特征。相对于黎曼积分而言，一维勒贝格积分定义如下：
其中函数是一个测度函数，计算函数
在
区间的测度，这里的测度是简单的面积测度（
）。
离散勒贝格积分
离散情况下，勒贝格积分的计算本质上依赖于排序方法。假定积分间隔为等间隔，那么积分化为离散求和。首先计算出所有的离散序对
，然后对
排序，得到
序列。我们依次统计处于
中的函数面积
。在这个过程中需要对计算给定
值，对应的
区间集合
。所有区间集合的面积即
，其中
。
线性变换
线性变换满足
。利用勒贝格积分计算离散傅立叶变换时，即对每个
对应的区间集合
进行变换。对于傅立叶变换来说，这个变换更为简单。
方波函数的傅立叶变换
方波函数，其他情况
。傅立叶变换对应：
离散情况下变为求和：
其中为方波的非
整数区间。
利用勒贝格积分原理，我们从值域处理，我们可以将离散函数分解为若干个区间的组合。实际上很多区间都是
，我们只需要计算那些测度非零区间（即有函数区域覆盖）的傅立叶变换，将其组合求和即可。
依据该思路有两种算法
- 传统积分结合线性变换，即冲击响应函数方法（类似Green函数方法）。利用
函数的傅立叶变换，直接用每个
进行线性变换后组合。
- 利用勒贝格积分在值域进行切割后，利用方波函数的投影快速方法加速变换。
注意： - 速度较快的关键在于：对
求和时，直接使用等比数列求和算法。
- 决定该算法的关键在于快速找到每个值域区间对应的定义域区间对。
- 当该信号类似于中心频率零频高斯脉冲时，效率极高，因为每个值域区间恰好仅仅只有一个连续定义域区间。满足该条件时，速度比
快。
- 排序算法不需要浮点计算效率很高。与FFT同是
时，时间系数更小。
- 需要快速扫描线算法，找到切割的定义域区间。可以利用导数信息快速求得相应的区间。原则上该算法的复杂性应当也是
- 求和的时间复杂性为
- 浮点乘法和三角函数计算的复杂性与区间的多少相关。
- 和FFT一样，$$
算法
略。
