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

勒贝格原理

勒贝格积分
勒贝格积分是指是值域积分原理，具有典型的统计特征。相对于黎曼积分而言，一维勒贝格积分定义如下：

其中函数是一个测度函数，计算函数在区间的测度，这里的测度是简单的面积测度（）。

离散勒贝格积分
离散情况下，勒贝格积分的计算本质上依赖于排序方法。假定积分间隔为等间隔，那么积分化为离散求和。首先计算出所有的离散序对，然后对排序，得到序列。我们依次统计处于中的函数面积。在这个过程中需要对计算给定值，对应的区间集合。所有区间集合的面积即，其中。

线性变换

线性变换满足。利用勒贝格积分计算离散傅立叶变换时，即对每个对应的区间集合进行变换。对于傅立叶变换来说，这个变换更为简单。

方波函数的傅立叶变换
方波函数，其他情况。傅立叶变换对应：

离散情况下变为求和：

其中为方波的非整数区间。

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

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

算法

略。