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

QPA: A Quantization-Aware Piecewise Polynomial approximation Methodology for Hardware-Efficient Implementations

IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS 2023年第7期31卷 931-944页

作者： Geng, Haoran Chen, Xiaoliang Zhao, Ning Du, Yuan Du, Li Nanjing Univ Sch Elect Sci & Engn Nanjing 210023 Peoples R China

Piecewise polynomial approximation (PPA) on nonlinear functions plays an important role in high-precision computing. In this article, we proposed QPA, an integration of error-flattened quantization-aware PPA methods, to generate the optimized coefficients for efficient hardware implementations targeting any polynomial order. QPA incorporated four key features to minimize the fitting error and the hardware cost, including using the Remez algorithm to compute the minimax fitting polynomial, combining the fitting and quantization operations to get an error-flattened characteristic, assigning specific coefficient bit width to each multiplier to reduce the hardware cost, and fine-tuning the truncated coefficients to further reduce the fitting error. Experimental results showed that our methods consistently achieved the lowest fitting error compared with the state-of-the-art error-flattened piecewise approximation methods. We synthesized the proposed designs with 28-nm TSMC CMOS technology. The results showed that the proposed designs achieved up to 37.0% area reduction and 50.5% power consumption reduction compared to the state-of-the-art error-flattened piecewise linear (PWL) method, and up to 27.0% area reduction, 21.4% delay reduction, and 20.8% power consumption reduction compared to the state-of-the-art error-flattened piecewise quadratic (PWQ) method.

关键词： Fitting Hardware approximation algorithms Table lookup Partitioning algorithms Adders Very large scale integration Approximate computing error-flattened fine-tuning rounding fitting algorithm piecewise polynomial approximation (PPA) prequantization Remez algorithm VLSI architecture

来源：评论

学校读者我要写书评

暂无评论

Hierarchical Clustering of Data Streams: Scalable algorithms and approximation Guarantees 38

Hierarchical Clustering of Data Streams: Scalable Algorithms...

引用

International Conference on Machine Learning (ICML)

作者： Rajagopalan, Anand Vitale, Fabio Vainstein, Danny Citovsky, Gui Procopiuc, Cecilia M. Gentile, Claudio Google Res New York NY 10003 USA Lille Univ Lille France INRIA Lille Lille France Tel Aviv Univ Tel Aviv Israel

ISBN: (纸本)9781713845065

We investigate the problem of hierarchically clustering data streams containing metric data in R-d. We introduce a desirable invariance property for such algorithms, describe a general family of hyperplane-based methods enjoying this property, and analyze two scalable instances of this general family against recently popularized similarity/dissimilarity-based metrics for hierarchical clustering. We prove a number of new results related to the approximation ratios of these algorithms, improving in various ways over the literature on this subject. Finally, since our algorithms are principled but also very practical, we carry out an experimental comparison on both synthetic and real-world datasets showing competitive results against known baselines.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Adaptive Extension Fitting Scheme: An Effective Curve approximation Method Using Piecewise Bezier Technology

引用

IEEE ACCESS 2023年 11卷 58422-58435页

作者： Cui, Xingyu Li, Yong Xu, Lili Beijing Normal Univ Sch Stat Haidian Beijing 100875 Peoples R China Beijing Normal Univ Sch Appl Math Zhuhai 519087 Guangdong Peoples R China

Curve approximation is a challenging issue to precisely depict exquisite shapes of natural phenomena, in which the piecewise Bezier curve is one of the most widely utilized tools due to its beneficial properties. It is essential to determine the quantity and location of control points through the process of generating the mathematical representation of desired objects. This paper presents a new algorithm called adaptive extension fitting scheme (AEFS) to determine a piecewise Bezier curve that best fits a given sequence of data points as well as locate the coordinates of the connecting points between the pieces adaptively. Taking full advantage of the scalability of the Bezier curve segment, AEFS is effective in sequential knot searching within an impressively small computational consumption. The capability of the proposed stepwise extension strategy is deduced from rigorous theoretical proof, resulting in proper connecting points together with well-fitted Bezier curves. The proposed algorithm is evaluated by some popular benchmarks for curve fitting, and compared with several state-of-the-art approaches. Experimental results indicate that AEFS outperforms other models involved in terms of execution time, fitting accuracy, number of segments, and the authenticity of shape contours.

关键词： Splines (mathematics) Curve fitting Standards Interpolation Surface reconstruction Computer graphics approximation algorithms Piecewise Bezier curve Bezier curve segment adaptive extension fitting curve approximation connecting point detection

来源：评论

学校读者我要写书评

暂无评论

Performance evaluation of typical approximation algorithms for nonconvex l_p-minimization in diffuse optical tomography

引用

JOURNAL OF THE OPTICAL SOCIETY OF AMERICA A-OPTICS IMAGE SCIENCE AND VISION 2014年第4期31卷 852-862页

作者： Shaw, Calvin B. Yalavarthy, Phaneendra K. Indian Inst Sci Supercomp Educ & Res Ctr Bangalore 560012 Karnataka India

The sparse estimation methods that utilize the l(p)-norm, with p being between 0 and 1, have shown better utility in providing optimal solutions to the inverse problem in diffuse optical tomography. These l(p)-norm-based regularizations make the optimization function nonconvex, and algorithms that implement l(p)-norm minimization utilize approximations to the original l(p)-norm function. In this work, three such typical methods for implementing the l(p)-norm were considered, namely, iteratively reweighted l(1)-minimization (IRL1), iteratively reweighted least squares (IRLS), and the iteratively thresholding method (ITM). These methods were deployed for performing diffuse optical tomographic image reconstruction, and a systematic comparison with the help of three numerical and gelatin phantom cases was executed. The results indicate that these three methods in the implementation of l(p)-minimization yields similar results, with IRL1 fairing marginally in cases considered here in terms of shape recovery and quantitative accuracy of the reconstructed diffuse optical tomographic images. (C) 2014 Optical Society of America

关键词： Tomography approximation algorithms image reconstruction Inverse method Performance Evaluation

来源：评论

学校读者我要写书评

暂无评论

Few-Shot Data-Driven algorithms for Low Rank approximation 35

Few-Shot Data-Driven Algorithms for Low Rank Approximation

引用

35th Annual Conference on Neural Information Processing Systems (NeurIPS)

作者： Indyk, Piotr Wagner, Tal Woodruff, David P. MIT Cambridge MA 02139 USA Microsoft Res Redmond Redmond WA USA Carnegie Mellon Univ Pittsburgh PA 15213 USA

ISBN: (纸本)9781713845393

Recently, data-driven and learning-based algorithms for low rank matrix approximation were shown to outperform classical data-oblivious algorithms by wide margins in terms of accuracy. Those algorithms are based on the optimization of sparse sketching matrices, which lead to large savings in time and memory during testing. However, they require long training times on a large amount of existing data, and rely on access to specialized hardware and software. In this work, we develop new data-driven low rank approximation algorithms with better computational efficiency in the training phase, alleviating these drawbacks. Furthermore, our methods are interpretable: while previous algorithms choose the sketching matrix either at random or by black-box learning, we show that it can be set (or initialized) to clearly interpretable values extracted from the dataset. Our experiments show that our algorithms, either by themselves or in combination with previous methods, achieve significant empirical advantages over previous work, improving training times by up to an order of magnitude toward achieving the same target accuracy.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Exploring Potential Barrier Estimation Mechanism Based on Quantum Dynamics Framework

引用

Chinese Journal of Electronics 2025年第1期34卷 350-364页

作者： Quan Tang Peng Wang Chengdu Institution of Computer Application Chinese Academy of Science University of Chinese Academy of Sciences School of Computer Science and Engineering Southwest Minzu University

Due to the probability characteristics of quantum mechanism, the combination of quantum mechanism and intelligent algorithm has received wide attention. Quantum dynamics theory uses the Schr?dinger equation as a quantum dynamics equation. Through three approximation of the objective function, quantum dynamics framework(QDF) is obtained which describes basic iterative operations of optimization algorithms. Based on QDF, this paper proposes a potential barrier estimation(PBE) method which originates from quantum mechanism. With the proposed method, the particle can accept inferior solutions during the sampling process according to a probability which is subject to the quantum tunneling effect, to improve the global search capacity of optimization *** effectiveness of the proposed method in the ability of escaping local minima was thoroughly investigated through double well function(DWF), and experiments on two benchmark functions sets show that this method significantly improves the optimization performance of high dimensional complex functions. The PBE method is quantized and easily transplanted to other algorithms to achieve high performance in the future.

关键词： Potential energy Electric potential Shape Heuristic algorithms Estimation Tunneling Linear programming approximation algorithms Iterative algorithms Optimization

来源：评论

学校读者我要写书评

暂无评论

approximation of Initial Coset Cardinality Spectrum of Distributed Arithmetic Coding for Uniform Binary Sources

引用

IEEE COMMUNICATIONS LETTERS 2023年第1期27卷 65-69页

作者： Yang, Nan Fang, Yong Wang, Lin Wang, Zhipeng Jiang, Fan Changan Univ Sch Informat Engn Xian 710064 Shaanxi Peoples R China Xiamen Univ Dept Commun Engn Xiamen 361005 Peoples R China Beihang Univ Sch Elect Informat Engn Beijing 100191 Peoples R China Xian Univ Posts & Telecommun Shaanxi Key Lab Informat Commun Network & Secur Xian 710121 Peoples R China

Distributed Arithmetic Coding (DAC) is a practical realization of Slepian-Wolf coding, one of whose properties is Coset Cardinality Spectrum (CCS). The initial CCS is especially important because it has many applications. Up to now, the initial CCS is calculable only for some discrete rates, while in general cases, the time-consuming numerical algorithm is needed. Though a polynomial approximation of the initial CCS has been proposed recently, its complexity becomes very high as code rate decreases. Hence, this letter aims at finding simpler approximations for the initial CCS at low rates by proposing two methods: interpolation approximation and bell-shaped approximation. The effectiveness of both methods is illustrated by simulation results.

关键词： Interpolation approximation algorithms Encoding Complexity theory Arithmetic Symbols Probability density function Slepian-Wolf coding distributed arithmetic coding coset cardinality spectrum interpolation approximation bell-shaped approximation

来源：评论

学校读者我要写书评

暂无评论

GBCT: Efficient and Adaptive Clustering via Granular-Ball Computing for Complex Data

引用

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS 2025年 PP卷 PP页

作者： Xia, Shuyin Shi, Bolun Wang, Yifan Xie, Jiang Wang, Guoyin Gao, Xinbo Chongqing Univ Posts & Telecommun Chongqing Key Lab Computat Intelligence Key Lab Cyberspace Big Data Intelligent Secur Minist Educ Chongqing 400065 Peoples R China Chongqing Univ Posts & Telecommun Key Lab Big Data Intelligent Comp Chongqing 400065 Peoples R China Chongqing Univ Posts & Telecommun Dept Comp Sci Chongqing 400065 Peoples R China

Traditional clustering algorithms often focus on the most fine-grained information and achieve clustering by calculating the distance between each pair of data points or implementing other calculations based on points. This way is not inconsistent with the cognitive mechanism of "global precedence" in the human brain, resulting in those methodsbad performance in efficiency, generalization ability, and robustness. To address this problem, we propose a new clustering algorithm called granular-ball clustering via granular-ball computing. First, clustering algorithm based on granular-ball (GBCT) generates a smaller number of granular-balls to represent the original data and forms clusters according to the relationship between granular-balls, instead of the traditional point relationship. At the same time, its coarse-grained characteristics are not susceptible to noise, and the algorithm is efficient and robust;besides, as granular-balls can fit various complex data, GBCT performs much better in nonspherical datasets than other traditional clustering methods. The completely new coarse granularity representation method of GBCT and cluster formation mode can also be used to improve other traditional methods.

关键词： Clustering algorithms Partitioning algorithms Computational modeling Robustness Noise approximation algorithms Mathematical models Clustering methods Telecommunications Shape Clustering granular computing granular-ball multigranularity

来源：评论

学校读者我要写书评

暂无评论

An approximation Theory Framework for Measure-Transport Sampling algorithms

arXiv

引用

arXiv 2023年

作者： Baptista, Ricardo Hosseini, Bamdad Kovachki, Nikola B. Marzouk, Youssef Sagiv, Amir Computing and Mathematical Sciences Caltech PasadenaCA United States Applied Mathematics University of Washington SeattleWA United States NVIDIA Corporation Santa ClaraCA United States Center for Computational Science and Engineering MIT CambridgeMA United States Technion - Israel Institute of Technology Haifa Israel

This article presents a general approximation-theoretic framework to analyze measure transport algorithms for probabilistic modeling. A primary motivating application for such algorithms is sampling-a central task in statistical inference and generative modeling. We provide a priori error estimates in the continuum limit, i.e., when the measures (or their densities) are given, but when the transport map is discretized or approximated using a finite-dimensional function space. Our analysis relies on the regularity theory of transport maps and on classical approximation theory for high-dimensional functions. A third element of our analysis, which is of independent interest, is the development of new stability estimates that relate the distance between two maps to the distance (or divergence) between the pushforward measures they define. We present a series of applications of our framework, where quantitative convergence rates are obtained for practical problems using Wasserstein metrics, maximum mean discrepancy, and Kullback-Leibler divergence. Specialized rates for approximations of the popular triangular Knöthe-Rosenblatt maps are obtained, followed by numerical experiments that demonstrate and extend our theory. Copyright © 2023, The Authors. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

New Subset Selection algorithms for Low Rank approximation: Offline and Online

arXiv

引用

arXiv 2023年

作者： Woodruff, David P. Yasuda, Taisuke Carnegie Mellon University United States

Subset selection for the rank k approximation of an n × d matrix A offers improvements in the interpretability of matrices, as well as a variety of computational savings. This problem is well-understood when the error measure is the Frobenius norm, with various tight algorithms known even in challenging models such as the online model, where an algorithm must select the column subset irrevocably when the columns arrive one by one. In sharp contrast, when the error measure is replaced by other matrix losses, optimal trade-offs between the subset size and approximation quality have not been settled, even in the standard offline setting. We give a number of results towards closing these gaps. In the offline setting, we achieve nearly optimal bicriteria algorithms in two settings. First, we remove a √k factor from a result of [SWZ19b] when the loss function is any entrywise loss with an approximate triangle inequality and at least linear growth, which includes, e.g., the Huber loss. Our result is tight when applied to the 1 loss. We give a similar improvement for the entrywise p loss for p > 2, improving a previous distortion of Õ(k1−1/p) to O(k1/2−1/p). We show this is tight for p = ∞, while for 2 1/p) distortion, which is nearly optimal and improves the previously best known Õ(d) [WW22] and closes a long line of work. In the online setting, we give the first online subset selection algorithm for p subspace approximation and entrywise p low rank approximation by showing how to implement the classical sensitivity sampling algorithm online, which is challenging due to the sequential nature of sensitivity sampling. Our main technique is an online algorithm for detecting when an approximately optimal subspace changes substantially. We also give new related results for the online setting, including online coresets for Euclidean (k, p) clustering as well as an online active regression algorithm making Θ˜(dp/2/Εp−1) queries, answering open questions of [MMWY22, CLS22]. © 2023

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：