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

Generalized fast algorithms for the polynomial time-frequency transform

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2007年第10期55卷 4907-4915页

作者： Ju, Yingtuo Bi, Guoan Nanyang Technol Univ Sch Elect & Elect Engn Singapore 639798 Singapore

This paper presents a general class of fast algorithms for computing the polynomial time-frequency transform (PTFT) of length-a(P)b, where a, b, and p are positive integers. The process of derivation shows some interesting properties that are effectively used for minimization of the computational complexity. By assigning values of a, b, and p, various algorithms, for example, radix-a and split-radix-2/(2a), can be easily obtained to provide the flexibility supporting polynomial time-frequency transforms of various sequence lengths. The detailed analysis on the computational complexities needed by these algorithms is also presented in terms of the numbers of additions and multiplications. It is shown that the proposed algorithms significantly reduce the computational complexity for applications that deal with polynomial phase signals.

关键词： fast algorithms fourier transforms polynomial phase signal polynomial time-frequency transform (PTFT)

来源：评论

学校读者我要写书评

暂无评论

Automatic generation of fast algorithms for matrix-vector multiplication

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2018年第3期95卷 626-644页

作者： Andreatto, B. Cariow, A. West Pomeranian Univ Technol Fac Comp Sci & Informat Technol Szczecin Poland

This paper describes the methods for finding fast algorithms for computing matrix-vector products including the procedures based on the block-structured matrices. The proposed methods involve an analysis of the structural properties of matrices. The presented approaches are based on the well-known optimization techniques: the simulated annealing and the hill-climbing algorithm along with its several extensions. The main idea of the proposed methods consists in finding a decomposition of the original matrix into a sparse matrix and a matrix corresponding to an appropriate block-structured pattern. The main criterion for optimizing is a reduction of the computational cost. The methods presented in this paper can be successfully implemented in many digital signal processing tasks.

关键词： fast algorithms matrix-vector multiplication computational complexity reduction block matrices simulated annealing hill-climbing

来源：评论

学校读者我要写书评

暂无评论

Pivoting and backward stability of fast algorithms for solving Cauchy linear equations

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2002年 343卷 63-99页

作者： Boros, T Kailath, T Olshevsky, V Georgia State Univ Dept Math & Stat Atlanta GA 30303 USA Stanford Univ Dept Elect Engn Informat Syst Lab Stanford CA 94305 USA ArrayComm Inc San Jose CA 95134 USA

Three fast O(n(2)) algorithms for solving Cauchy linear systems of equations are proposed. A rounding error analysis indicates that the backward stability of these new Cauchy solvers is similar to that of Gaussian elimination, thus suggesting to employ various pivoting techniques to achieve a favorable backward stability. It is shown that Cauchy structure allows one to achieve in O(n(2)) operations partial pivoting ordering of the rows and several other judicious orderings in advance, without actually performing the elimination. The analysis also shows that for the important class of totally positive Cauchy matrices it is advantageous to avoid pivoting, which yields a remarkable backward stability of the suggested algorithms. It is shown that Vandermonde and Chebyshev-Vandermonde matrices can be efficiently transformed into Cauchy matrices, using Discrete Fourier, Cosine or Sine transforms. This allows us to use the proposed algorithms for Cauchy matrices for rapid and accurate solution of Vandermonde and Chebyshev-Vandermonde linear systems. The analytical results are illustrated by computed examples. (C) 2002 Elsevier Science Inc. All rights reserved.

关键词： displacement structure Cauchy matrix Vandermonde matrix fast algorithms pivoting rounding error analysis backward stability total positivity

来源：评论

学校读者我要写书评

暂无评论

Levinson-like and Schur-like fast algorithms for solving block-slanted Toeplitz systems of equations arising in wavelet-based solution of integral equations

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 1998年第7期46卷 1798-1813页

作者： Joshi, RR Yagle, AE Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48109 USA

The Wiener-Hopf integral equation of linear least-squares estimation of a wide-sense stationary random process and the Krein integral equation of one-dimensional (1-D) inverse scattering are Fredholm equations with symmetric Toeplitz kernels. They are transformed using a wavelet-based Galerkin method into a symmetric "block-slanted Toeplitz (BST)" system of equations. Levinson-like and Schur-like fast algorithms are developed for solving the symmetric BST system of equations, The significance of these algorithms is as follows, If the kernel of the integral equation is not a Calderon-Zygmund operator, the wavelet transform may not sparsify it. The kernel of the Krein and Wiener-Hopf integral equations does not, in general, satisfy the Calderon-Zygmund conditions. As a result, application of the wavelet transform to the integral equation does not yield a sparse system matrix. There is, therefore, a need for fast algorithms that directly exploit the (symmetric block-slanted Toeplitz) structure of the system matrix and do not rely on sparsity, The first such O(n(2)) algorithms, viz,, a Levinson-like algorithm and a Schur-like algorithm, are presented here. These algorithms are also applied to the factorization of the BST system matrix. The Levinson-like algorithm also yields a test for positive definiteness of the BST system matrix. The results obtained here are directly applicable to the problem of constrained deconvolution of a nonstationary signal, where the locations of the smooth regions of the signal being deconvolved are known a priori.

关键词： .Fredholm integral equation Toeplitz fast algorithms system matrix Systems of Equations inverse scattering Levinson-Like Schur-Like

来源：评论

学校读者我要写书评

暂无评论

Adaptive vectorial total variation models for multi-channel synthetic aperture radar images despeckling with fast algorithms

引用

IET IMAGE PROCESSING 2013年第9期7卷 795-804页

作者： Liu, Huiyan Yan, Fengxia Zhu, Jubo Fang, Faming Natl Univ Def Technol Dept Math & Syst Sci Changsha 410073 Hunan Peoples R China E China Normal Univ Dept Comp Sci Shanghai 200241 Peoples R China

This study proposes two adaptive vectorial total variation models for multi-channel synthetic aperture radar (SAR) images despeckling with the help of prior knowledge of the image amplitude. Besides despeckling the multi-channel SAR images efficiently, the proposed new models have advantages over other total variation methods in many aspects, such as preserving the radar reflectivity, the targets and edges contrast. The Bermudez-Moreno algorithm and the accelerated fast iterative shrinkage thresholding algorithm are employed to implement the new two models, respectively. Experimental results on multi-polarimetric, multi-temporal RADARSAT-2 images show that the visual quality and evaluation indexes of the proposed models and the corresponding algorithms outperform the other methods with edge preservation.

关键词： image segmentation iterative methods radar imaging synthetic aperture radar vectors adaptive vectorial total variation models multichannel synthetic aperture radar images despeckling SAR images fast algorithms image amplitude radar reflectivity Bermudez-Moreno algorithm iterative shrinkage thresholding algorithm multipolarimetric images multitemporal RADARSAT-2 images visual quality evaluation indexes edge preservation

来源：评论

学校读者我要写书评

暂无评论

Path-Based Spectral Clustering: Guarantees, Robustness to Outliers, and fast algorithms

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2020年第1期21卷 1-66页

作者： Little, Anna Maggioni, Mauro Murphy, James M. Michigan State Univ Dept Computat Math Sci & Engn E Lansing MI 48824 USA Johns Hopkins Univ Dept Math Dept Appl Math & Stat Baltimore MD 21218 USA Tufts Univ Dept Math Medford MA 02139 USA

We consider the problem of clustering with the longest-leg path distance (LLPD) metric, which is informative for elongated and irregularly shaped clusters. We prove finite-sample guarantees on the performance of clustering with respect to this metric when random samples are drawn from multiple intrinsically low-dimensional clusters in high-dimensional space, in the presence of a large number of high-dimensional outliers. By combining these results with spectral clustering with respect to LLPD, we provide conditions under which the Laplacian eigengap statistic correctly determines the number of clusters for a large class of data sets, and prove guarantees on the labeling accuracy of the proposed algorithm. Our methods are quite general and provide performance guarantees for spectral clustering with any ultrametric. We also introduce an efficient, easy to implement approximation algorithm for the LLPD based on a multiscale analysis of adjacency graphs, which allows for the runtime of LLPD spectral clustering to be quasilinear in the number of data points.

关键词： unsupervised learning spectral clustering manifold learning fast algorithms shortest path distance

来源：评论

学校读者我要写书评

暂无评论

Recurrence relations and fast algorithms

引用

APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS 2010年第1期28卷 121-128页

作者： Tygert, Mark Univ Calif Los Angeles Dept Math Los Angeles CA 90095 USA

We construct fast algorithms for evaluating transforms associated with families of functions which satisfy recurrence relations. These include algorithms both for computing the coefficients in linear combinations of the functions, given the values of these linear combinations at certain points, and. vice versa, for evaluating such linear combinations at those points, given the coefficients in the linear combinations;such procedures are also known as analysis and synthesis of series of certain special functions. The algorithms of the present paper are efficient in the sense that their computational costs are proportional to n Inn at any fixed precision of computations, where n is the amount of input and output data. Stated somewhat more precisely, we find a positive real number C such that, for any positive integer n >= 10 and positive real number epsilon <= 1/10, the algorithms require at most Cn(lnn)(ln(1/epsilon))(3) floating-point operations to evaluate at n appropriately chosen points any linear combination of n special functions. given the coefficients in the linear combination, where s is the precision of computations. (C) 2009 Elsevier Inc. All rights reserved.

关键词： Recurrence fast algorithms Special functions Pseudospectral Transforms

来源：评论

学校读者我要写书评

暂无评论

MONTE-CARLO ESTIMATION OF NUMERICAL STABILITY IN fast algorithms FOR SYSTEMS OF BILINEAR-FORMS

引用

INFORMATION PROCESSING LETTERS 1982年第4期14卷 162-167页

作者： BERETTA, G ETH Informatik CH-8092 Zürich Switzerland

Strassen's (1969) matrix multiplication is a well-known example of a fast algorithm for the evaluation of systems of bilinear forms. The fast algorithms substitute additions for multiplications; however, while reducing the number of multiplications, fast algorithms may increase the total number of required operations. This prospect calls into question the numerical stability of fast algorithms in relation to classical algorithms. Experimental evidence is presented for the numerical instability of fast algorithms for matrices, quaternions, and complex numbers. The classical counterparts to fast algorithms are shown to possess a higher degree of numerical stability, and are, therefore, of more practical utility.

关键词： fast algorithms Strassen algorithm numerical stability roundoff error

来源：评论

学校读者我要写书评

暂无评论

Constructing fast algorithms by Expanding a Set of Matrices into Rank-1 Matrices

引用

CIRCUITS SYSTEMS AND SIGNAL PROCESSING 2020年第3期39卷 1630-1648页

作者： da Silva, G. Jeronimo, Jr. de Souza, R. M. Campello Fed Univ Pernambuco UFPE Dept Elect & Syst Ave Arquitetura S-NBloco B4o Andar BR-50740550 Recife PE Brazil

This paper introduces the notion of numerical basis for a numerical space and uses it to establish a relation between a fast algorithm for computing a discrete linear transform and the problem of expanding a given finite set of matrices as a linear combination of rank-1 matrices. It is shown that the number of multiplications of the algorithm is given by the number of rank-1 matrices in the expansion. Applying this approach, an algorithm for computing three components of the nine-point discrete Fourier transform (DFT) and an algorithm to compute the seven-point DFT with the least possible number of multiplications are shown.

关键词： fast algorithms Rank-1 set of matrices expansion fast Fourier transform Multiplicative complexity

来源：评论

学校读者我要写书评

暂无评论

Two fast algorithms for projecting a point onto the canonical simplex

引用

COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS 2016年第5期56卷 730-743页

作者： Malozemov, V. N. Tamasyan, G. Sh. St Petersburg State Univ Univ Skaya Nab 7-9 St Petersburg 199034 Russia

Two fast orthogonal projection algorithms of a point onto the canonical simplex are analyzed. These algorithms are called the vector and scalar algorithms, respectively. The ideas underlying these algorithms are well known. Improved descriptions of both algorithms are given, their finite convergence is proved, and exact estimates of the number of arithmetic operations needed for their implementation are derived, and numerical results of the comparison of their computational complexity are presented. It is shown that on some examples the complexity of the scalar algorithm is maximal but the complexity of the vector algorithm is minimal and conversely. The orthogonal projection of a point onto the solid simplex is also considered.

关键词： quadratic programming projecting onto a simplex optimality condition fast algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：