Summarizing information structures by random sampling algorithms

研究的重点是稀疏傅立叶采样算法，它是用随机采样算法来总结信息结构的一个突出例子，它是一种快速地总结大规模数据保持其结构并使用随机抽样的方法。该算法能够仅依赖于信号中相对较少的样本来估计巨大信号数据的主要傅立叶系数，有望用于大规模多媒体数据的汇总。研究的主要贡献是基于实现的一系列性能分析。特别是，该算法应用于多种类型的数据，将各种参数的取值设置为小于理论性能保证的取值，从而清楚地表明算法在什么参数和什么类型的数据上运行时有/没有性能裕度。用GP/PARI语言实现了该算法，计算了算法的运行时间、成功概率和访问…比较了傅立叶系数的精确度。结果表明：(A)将频率识别过程中使用的原始数字滤波器替换为具有相同滤波度和更好的频率选择性的等幅滤波器，以小的运行时间增量为代价，将识别主频的成功率提高15%；(B)在相同的过程中，当考虑将有限的计算资源分配给“孤立信号的数目”和“滤波度”时，最好将更多的权重放在“孤立信号的数目”上；(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