权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Summarizing information structures by random sampling algorithms

通过随机采样算法总结信息结构

基本信息

批准号：
18500008
负责人：
TAKEI Yoshinori
金额：
$ 1.54万
依托单位：
Nagaoka University of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2006
资助国家：
日本
起止时间：
2006 至 2007
项目状态：
已结题

项目摘要

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

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