Summarizing information structures by random sampling algorithms

本文的研究重点是稀疏傅里叶采样算法，该算法是随机采样算法总结信息结构的一个突出例子，它可以在保持数据结构的情况下，使用随机采样快速总结大规模数据。该算法能够估计一个巨大的信号数据的主要傅立叶系数仅依赖于相对较少的样本从信号。本研究的主要贡献是基于一个实现的一系列性能分析。特别是，该算法应用于许多类型的数据，将各种参数的值设置为小于理论性能保证的值，以便明确算法在什么参数和什么类型的数据上运行有/没有性能裕量。采用GP/PARI语言实现了该算法，并对算法的运行时间、成功概率和误差进行了检验。结果表明：(a)当考虑将有限的计算资源分配给“隔离信号数”和“滤波度”时，将频率识别过程中使用的原始数字滤波器替换为具有相同滤波度和更好的频率选择性的四倍滤波器，以同一过程中运行时间的小增量为代价，将识别主要频率的成功率提高了15%。对“隔离信号的数量”给予更多的权重是好的(c)算法在这样一个由一个重要频率分量和许多小频率分量组成的信号上运行有一定的性能裕度，另一方面，当信号包含两个或更多大致相同幅度的主要频率分量时，它没有裕度(d)当所需的傅立叶系数精度约为5%时。估计傅里叶系数所花费的时间与识别主频率所花费的时间相比是非常小的。这些结果将为实际实现提供很好的提示，可以用于汇总大型多媒体数据。少

The research focused on the sparse Fourier sampling algorithm, which is a prominent example of summarizing information structures by random sampling algorithms, an approach that quickly summarizes a large scale data keeping its structure and using random sampling. The algorithm enables estimating major Fourier coefficients of a huge signal data depending only on relatively small number of samples from the signal., and is expected to be useful in summarizing large-scale multimedia data The main contribution of the research is a series of performance analyses based on an implementation. In particular, the algorithm was applied to many types of data, setting values of various parameters to be smaller than that would be derived from theoretical performance guarantee, so that it was clear in what parameter and to what type of data the algorithm runs with/without performance margin. The algorithm was implemented using GP/PARI language and the running time, the success probability and the acc … More uracy of the Fourier coefficients were examined. It turned out that (a) replacing the original digital filter used in the frequency identification procedure with a equripple filter with the same filter degree and a better frequency selectivity increases the success probability of identifying major frequencies by 15 percent points, at a cost of small increment of the running time (b) in the same procedure, when one considers distributing a limited amount of computational resource to "'the number of isolated signals" and "filter degree", it is good to put more weight on "the number of isolated signals" (c) the algorithm runs with some performance margin on such a signal that consists of one significant frequency component and many small frequency components, on the other hand, it runs without margin when the signal contains two or more major frequency components of approximately same magnitudes (d) when the required accuracy of the Fourier coefficients is around 5 percent, the time taken by the estimation of Fourier coefficients is very small compared to that taken by the identification of major frequencies. These results will be good hint for practical implementation that can be used to summarize large multimedia data. Less