Summarizing information structures by random sampling algorithms

研究的重点是稀疏傅立叶采样算法，它是利用随机采样算法对信息结构进行归纳的一个突出例子，是一种利用随机采样快速归纳出大规模数据保持其结构的方法。该算法使得能够仅依赖于来自信号的相对少量的样本来估计巨大信号数据的主要傅立叶系数。并预计将是有用的，在总结大规模的多媒体数据的主要贡献的研究是一系列的性能分析的基础上实现。特别地，该算法被应用于许多类型的数据，将各种参数的值设置为小于将从理论性能保证导出的值，使得清楚地知道算法在具有/不具有性能裕度的情况下在什么参数和什么类型的数据中运行。该算法用GP/PARI语言实现，并对算法的运行时间、成功概率和正确率进行了分析。 关于我们 傅里叶系数的精度进行了检查。结果表明：（a）用具有相同滤波阶数和更好频率选择性的等频率滤波器代替频率识别过程中使用的原始数字滤波器，以在相同过程中小的运行时间（B）增加为代价，将识别主频率的成功概率提高了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