检索结果-内蒙古大学图书馆

Empirical Evaluation of Typical Sparse Fast Fourier Transform algorithms

IEEE ACCESS 2021年 9卷 97100-97119页

作者： Jiang, Zhikang Chen, Jie Li, Bin Shanghai Univ Sch Mech & Elect Engn & Automat Shanghai 200072 Peoples R China

Computing the Sparse Fast Fourier Transform(sFFT) has emerged as a critical topic for a long time. The sFFT algorithms decrease the runtime and sampling complexity by taking advantage of the signal's inherent characteristics that a large number of signals are sparse in the frequency domain. More than ten sFFT algorithms have been proposed, which can be classified into many types according to filter, framework, method of location, method of estimation. In this paper, the technology of these algorithms is completely analyzed in theory. The performance of them is thoroughly tested and verified in practice. The techniques involved in different sFFT algorithms include the following contents: five operations of signal, three methods of frequency bucketization, five methods of location, four methods of estimation, two problems caused by bucketization, three methods to solve these two problems, four algorithmic frameworks. All the above technologies and methods are introduced in detail and examples are given to illustrate the above research. After theoretical research, we make experiments for computing the signals of different SNR, length, sparsity by a standard testing platform and record the run time, percentage of the signal sampled and L-0, L-1, L-2 error with eight different typical sFFT algorithms. The result of experiments satisfies the inferences obtained in theory. It helps us to optimize these algorithms and use them selectively.

关键词： Sparse Fast Fourier Transform(sFFT) flat filter spike train filter Dirichlet kernel filter bank sub-linear algorithms computational complexity

来源：评论

学校读者我要写书评

暂无评论

On Performance of Sparse Fast Fourier Transform algorithms Using the Flat Window Filter

引用

IEEE ACCESS 2020年 8卷 79134-79146页

作者： Li, Bin Jiang, Zhikang Chen, Jie Shanghai Univ Sch Mech & Elect Engn & Automat Shanghai 200072 Peoples R China

The problem of computing the Sparse Fast Fourier Transform(sFFT) of a-sparse signal of sizeS has received significant attention for a long time. The first stage of sFFT is hashing the frequency coefficients into buckets named frequency bucketization. The process of frequency bucketization is achieved through the use of filters: Dirichlet kernel filter, aliasing filter, flat filter, etc. The frequency bucketization through these filters can decrease runtime and sampling complexity in low dimensions. It is a hot topic about sFFT algorithms using the flat filter because of its convenience and efficiency since its emergence and wide application. The next stage of sFFT is the spectrum reconstruction by identifying frequencies that are isolated in their buckets. Up to now, there are more than thirty different sFFT algorithms using the sFFT idea as mentioned above by their unique methods. An important question now is how to analyze and evaluate the performance of these sFFT algorithms in theory and practice. In this paper, it is mainly discussed about sFFT algorithms using the flat filter. In the first part, the paper introduces the techniques in detail, including two types of frameworks, five different methods to reconstruct spectrum and corresponding algorithms. We get the conclusion of the performance of these five algorithms, including runtime complexity, sampling complexity and robustness in theory. In the second part, we make three categories of experiments for computing the signals of different SNR, different , and different by a standard testing platform and record the run time, percentage of the signal sampled, and error both in the exactly sparse case and general sparse case. The result of experiments is consistent with the inferences obtained in theory. It can help us to optimize these algorithms and use them correctly in the right areas.

关键词： Signal processing algorithms Microsoft Windows Runtime Discrete Fourier transforms Complexity theory Kernel Frequency-domain analysis Sparse fast Fourier transform (sFFT) flat window filter sub-linear algorithms computational complexity

来源：评论

学校读者我要写书评

暂无评论

Multi-Resolution Hashing for Fast Pairwise Summations 60

Multi-Resolution Hashing for Fast Pairwise Summations

引用

60th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Charikar, Moses Siminelakis, Paris Stanford Univ Dept Comp Sci Stanford CA 94305 USA Stanford Univ Dept Elect Engn Stanford CA 94305 USA

ISBN: (纸本)9781728149523

A basic computational primitive in the analysis of massive datasets is summing simple functions over a large number of objects. Modern applications pose an additional challenge in that such functions often depend on a parameter vector y (query) that is unknown a priori. Given a set of points X and a pairwise function w(x,y), we study the problem of designing a data-structure that enables sublinear-time approximation of the summation of w(x,y) for all x in X for any query point y. By combining ideas from Harmonic Analysis (partitions of unity and approximation theory) with Hashing-Based-Estimators [Charikar, Siminelakis FOCS'17], we provide a general framework for designing such data structures through hashing that reaches far beyond what previous techniques allowed. A key design principle is constructing a collection of hash families, each inducing a different collision probability between points in the dataset, such that the pointwise supremum of the collision probabilities scales as the square root of the function w(x,y). This leads to a data-structure that approximates pairwise summations using a sub-linear number of samples from each hash family. Using this new framework along with Distance Sensitive Hashing [Aumuller, Christiani, Pagh, Silvestri PODS'18], we show that such a collection can be constructed and evaluated efficiently for log-convex functions of the inner product between two vectors. Our method leads to data structures with sub-linear query time that significantly improve upon random sampling and can be used for Kernel Density, Partition Function Estimation and sampling.

关键词： Hashing Kernel Density Partition Function Importance Sampling sub-linear algorithms

来源：评论

学校读者我要写书评

暂无评论

sublinear algorithms for (1.5+𝜖)-Approximate Matching 2023

Sublinear Algorithms for (1.5+𝜖)-Approximate Matching

引用

Proceedings of the 55th Annual ACM Symposium on Theory of Computing

作者： Sayan Bhattacharya Peter Kiss Thatchaphol Saranurak University of Warwick UK University of Warwick UK / MPI-INF Germany University of Michigan USA

ISBN: (纸本)9781450399135

We study sublinear time algorithms for estimating the size of maximum matching. After a long line of research, the problem was finally settled by Behnezhad [FOCS’22], in the regime where one is willing to pay an approximation factor of 2. Very recently, Behnezhad et al. [SODA’23] improved the approximation factor to (2−1/2O(1/γ)) using n1+γ time. This improvement over the factor 2 is, however, minuscule and they asked if even 1.99-approximation is possible in n2−Ω(1) time. We give a strong affirmative answer to this open problem by showing (1.5+є)-approximation algorithms that run in n2−Θ(є2) time. Our approach is conceptually simple and diverges from all previous sublinear-time matching algorithms: we show a sublinear time algorithm for computing a variant of the edge-degree constrained subgraph (EDCS), a concept that has previously been exploited in dynamic [Bernstein Stein ICALP’15, SODA’16], distributed [Assadi et al. SODA’19] and streaming [Bernstein ICALP’20] settings, but never before in the sublinear setting.

关键词： Matching sub-linear algorithms Approximate algorithms Sparsification

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：