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

Constructing Embedded lattice-Based algorithms for Multivariate Function Approximation with a Composite Number of Points

引用

CONSTRUCTIVE APPROXIMATION 2025年第1期61卷 81-113页

作者： Kuo, Frances Y. Mo, Weiwen Nuyens, Dirk UNSW Sydney Sch Math & Stat Sydney NSW 2052 Australia Dept Comp Sci KU Leuven Celestijnenlaan 200A B-3001 Leuven Belgium

We approximate d-variate periodic functions in weighted Korobov spaces with general weight parameters using n function values at lattice points. We do not limit n to be a prime number, as in currently available literature, but allow any number of points, including powers of 2, thus providing the fundamental theory for construction of embedded lattice sequences. Our results are constructive in that we provide a component-by-component algorithm which constructs a suitable generating vector for a given number of points or even a range of numbers of points. It does so without needing to construct the index set on which the functions will be represented. The resulting generating vector can then be used to approximate functions in the underlying weighted Korobov space. We analyse the approximation error in the worst-case setting under both the L2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L_2$$\end{document} and L infinity\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L_{\infty }$$\end{document} norms. Our component-by-component construction under the L2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L_2$$\end{document} norm achieves the best possible rate of convergence for lattice-based algorithms, and the theory can be applied to lattice-based kernel methods and splines. Depending on the value of the smoothness parameter alpha\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackag

关键词： lattice rules lattice algorithms Embedded lattice sequences Multivariate function approximation Component-by-component construction Composite number of points Non-prime number of points

来源：评论

学校读者我要写书评

暂无评论

lattice algorithms for recursive instrumental variable methods

引用

INTERNATIONAL JOURNAL OF ADAPTIVE CONTROL AND SIGNAL PROCESSING 1996年第2-3期10卷 177-212页

作者： Swami, A Mendel, JM UNIV SO CALIF DEPT ELECT ENGN SYSTLOS ANGELESCA 90089

We develop recursive lattice algorithms for the estimation of the AR parameters of an ARMA process using an instrumental variable (TV) such as z(n) = y(2)(n), which leads to AR estimates based on the third-order cumulants, or z(n) = y(n - q), which leads to AR estimates based on the higher-order Yule-Walker equations. In the non-recursive mode the resulting set of linear equations involves the cross-correlation matrix of the observed process y(n), and the instrumental process z(n) and hence this matrix is generally not Hermitian. Our time- and order-recursive algorithm leads to a pair of lattices, one excited by y(n) and the other by z(n), the lattices being coupled through order and time update equations. We show that IV-based AR model fitting is equivalent to linear prediction with non-conventional orthogonality conditions. Extensions to ARMA processes are discussed. The joint-process estimation problem is also treated. Some statistical analysis is carried out and convergence results are given when y(n) and z(n) can be modelled as stationary processes. The only assumption that we make about z(n), the associated process, is that the cross-correlation of y(n) and z(n) suffices for the estimation of the AR parameters, i.e. we assume that z(n) is an instrumental process. Particular choices of z(n) lead to estimates based on the higher-order cumulants, which are useful when the non-Gaussian signal is corrupted by additive coloured Gaussian noise.

关键词： lattice algorithms recursive instrumental variable methods cumulants

来源：评论

学校读者我要写书评

暂无评论

A quantum lattice algorithm with fourth-order accuracy for the one-dimensional Dirac equation

引用

JOURNAL OF COMPUTATIONAL PHYSICS 2025年 533卷

作者： Dellar, Paul J. Univ Oxford Math Inst Radcliffe Observ Quarter Oxford OX2 6GG England

The discrete time quantum walk is a quantum cellular automaton whose wavefunction comprises pairs of complex numbers assigned to uniformly spaced points on a line. The wavefunction evolves through the application of an alternating sequence of unitary operators: streaming of wavefunction values to adjacent points, and a Hadamard-type unitary matrix to blend pairs of values at individual points. Each operator generates the exact evolution due to part of the Hamiltonian for the one-dimensional Dirac equation over a finite time step. Composing these operators thus creates a discrete approximation to the Dirac equation. However, the composition of two non-commuting operators creates a global splitting error proportional to the length of the time step. The global error can be reduced from first order to second order in the time step by a unitary pre-and post-processing of the initial conditions and final output. The algorithm then becomes equivalent to a symmetric composition, a Strang splitting, between the two operators. This paper describes a fourth-order accurate composition scheme using nine stages, the fewest possible when the lengths of the time steps employed in the different stages are constrained to be integer multiples of some base time step. Each stage is itself a symmetric composition between two operators. This fourth-order scheme produces quantitatively smaller errors for a typical benchmark problem on spatial lattices with 1024 or more points, and shows the expected fourth-order convergence on sufficiently fine lattices. It has greater accuracy, over sufficiently long times, than three better-known fourth-order composition schemes using fewer stages, but with lengths related by irrational coefficients. The truncation error for plane-wave solutions is due to an operator that separates into a resonant part proportional to the Hamiltonian, and a non-resonant part orthogonal to the Hamiltonian. The resonant part commutes with the exact evolution operator, so i

关键词： lattice algorithms Splitting algorithms Composition schemes Discrete invariants Resonant interactions

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for discrete lattice calculations

引用

JOURNAL OF COMPUTATIONAL PHYSICS 2009年第13期228卷 4858-4880页

作者： Arndt, M. Sorkin, V. Tadmor, E. B. Univ Minnesota Dept Aerosp Engn & Mech Minneapolis MN 55455 USA Univ Minnesota Sch Math Minneapolis MN 55455 USA

We discuss algorithms for lattice-based computations, in particular lattice reduction, the detection of nearest neighbors, and the computation of clusters of nearest neighbors. We focus on algorithms that are most efficient for low spatial dimensions (typically d = 2, 3) and input data within a reasonably limited range. This makes them most useful for physically oriented numerical simulations, for example of crystalline solids. Different solution strategies are discussed, formulated as algorithms, and numerically evaluated. (c) 2009 Elsevier Inc. All rights reserved.

关键词： lattice algorithms lattice reduction Nearest neighbor Cluster computation Quasicontinuum

来源：评论

学校读者我要写书评

暂无评论

Array-based QR-RLS multichannel lattice filtering

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2008年第8期56卷 3510-3522页

作者： Gomes, Joao Barroso, Victor A. N. Univ Tecn Lisboa Inst Syst & Robot Inst Super Tecn Lisbon Portugal

An array-based algorithm for multichannel lattice filtering is proposed. The filter is formed by a set of units that are adapted locally and concurrently using recursions that closely match those for single-channel lattice filters. The design, based on a known modular decomposition approach, allows for unequal filter lengths to be specified for different input channels. Individual units are updated using a square-root recursive least-squares (RLS) algorithm in array form that relies mainly on Givens rotations and exhibits highly favorable numerical behavior and a regular structure that is appealing from a hardware implementation perspective. Iterative implementations of Givens rotations using the Newton method and CORDIC processors are examined in the context of fixed-point implementations. A procedure based on three CORDIC steps is proposed to handle complex data that arise in several applications of multichannel filtering. Algorithm initialization issues are also addressed. The array algorithm is compared in simulation with plain RLS, QR-RLS, and two related multichannel lattice algorithms. Its performance is shown to be comparable to that of other QR-decomposition-based algorithms under fixed-point arithmetic. In particular, it retains desirable graceful degradation properties as the numerical precision decreases.

关键词： adaptive filtering lattice algorithms multichannel filtering recursive least-squares (RLS) estimation

来源：评论

学校读者我要写书评

暂无评论

lattice-Filter-Based Multivariate Autoregressive Spectral Estimation With Joint Model Order and Estimation Bandwidth Adaptation

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2019年第12期64卷 4968-4981页

作者： Niedzwiecki, Maciej Meller, Michal Chojnacki, Damian Gdansk Univ Technol Dept Automat Control Fac Elect Telecommun & Comp Sci PL-80233 Gdansk Poland

The problem of parametric autoregressive model-based estimation of a time-varying spectral density function of a multivariate nonstationary process is considered. It is shown that estimation results can be considerably improved if identification of the autoregressive model is carried out using the two-sided doubly exponentially weighted lattice algorithm, which combines results yielded by two one-sided lattice algorithms running forward in time and backward in time, respectively. It is also shown that the model order and the most appropriate estimation bandwidth can be efficiently selected using the suitably modified Akaikes final prediction error criterion.

关键词： Estimation Reactive power Autoregressive processes lattices Adaptation models Density functional theory Spectral analysis Identification of nonstationary systems lattice algorithms parametric spectrum estimation

来源：评论

学校读者我要写书评

暂无评论

lattice Sparsification and the Approximate Closest Vector Problem

引用

THEORY OF COMPUTING 2016年 12卷

作者： Dadush, Daniel Kun, Gabor CWI Amsterdam Netherlands Hungarian Acad Sci Alfred Renyi Inst Math 13-15 Realtanoda U H-1053 Budapest Hungary

We give a deterministic algorithm for solving the (1 + epsilon)-approximate Closest Vector Problem (CVP) on any n-dimensional lattice and in any near-symmetric norm in 2(O(n))(1 + 1/epsilon)(n) time and 2(n) poly(n) space. Our algorithm builds on the lattice point enumeration techniques of Micciancio and Voulgaris (STOC 2010, SICOMP 2013) and Dadush, Peikert and Vempala (FOCS 2011), and gives an elegant, deterministic alternative to the "AKS Sieve"-based algorithms for (1 + epsilon)-CVP (Ajtai, Kumar, and Sivakumar;STOC 2001 and CCC 2002). Furthermore, assuming the existence of a poly(n)-space and 2(O(n))-time algorithm for exact CVP in the l(2) norm, the space complexity of our algorithm can be reduced to polynomial. Our main technical contribution is a method for "sparsifying" any input lattice while approximately maintaining its metric structure. To this end, we employ the idea of random sublattice restrictions, which was first employed by Khot (FOCS 2003, J. Comp. Syst. Sci. 2006) for the purpose of proving hardness for the Shortest Vector Problem (SVP) under l(p) norms.

关键词： approximation algorithms high dimensional geometry lattice algorithms closest vector problem

来源：评论

学校读者我要写书评

暂无评论

On polynomial-factor approximations to the shortest lattice vector length

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2003年第3期16卷 422-425页

作者： Kumar, R Sivakumar, D IBM Corp Almaden Res Ctr Dept K53 B1 San Jose CA 95120 USA

For every constant epsilon > 0, we obtain a 2(O(n(1/2+1/epsilon))) time randomized algorithm to approximate the length of the shortest vector in an n-dimensional lattice to within a factor of n(3+epsilon)..

关键词： lattice algorithms shortest lattice vector SVP

来源：评论

学校读者我要写书评

暂无评论

A DETERMINISTIC SINGLE EXPONENTIAL TIME ALGORITHM FOR MOST lattice PROBLEMS BASED ON VORONOI CELL COMPUTATIONS

引用

SIAM JOURNAL ON COMPUTING 2013年第3期42卷 1364-1391页

作者： Micciancio, Daniele Voulgaris, Panagiotis Univ Calif San Diego Dept Comp Sci & Engn La Jolla CA 92093 USA Google Inc Mountain View CA 94043 USA

We give deterministic (O) over tilde (2(2n))-time (O) over tilde (2(n))-space algorithms to solve all the most important computational problems on point lattices in NP, including the shortest vector problem (SVP), closest vector problem (CVP), and shortest independent vectors problem (SIVP). This improves the n(O(n)) running time of the best previously known algorithms for CVP [R. Kannan, Math. Oper. Res., 12 (1987), pp. 415-440] and SIVP [D. Micciancio, Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete algorithms, 2008, pp. 84-93] and gives a deterministic and asymptotically faster alternative to the 2(O(n))-time (and space) randomized algorithm for SVP of Ajtai, Kumar, and Sivakumar [Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, 2001, pp. 266-275]. The core of our algorithm is a new method to solve the closest vector problem with preprocessing (CVPP) that uses the Voronoi cell of the lattice (described as intersection of half-spaces) as the result of the preprocessing function. A direct consequence of our results is a derandomization of the best current polynomial time approximation algorithms for SVP and CVP, achieving a 2(O(n log log n/log n)) approximation factor.

关键词： lattice algorithms shortest vector problem closest vector problem Voronoi cell

来源：评论

学校读者我要写书评

暂无评论

Computing a lattice Basis Revisited 19

Computing a Lattice Basis Revisited

引用

44th ACM International Symposium on Symbolic and Algebraic Computation (ISSAC)

作者： Li, Jianwei Nguyen, Phong Q. NUS CQT Singapore Singapore Chinese Acad Sci AMSS KLMM Beijing Peoples R China Inria Paris France Univ Tokyo JFLI CNRS Tokyo Japan

ISBN: (纸本)9781450360845

Given (a, b) is an element of Z(2), Euclid's algorithm outputs the generator gcd(a, b) of the ideal aZ+ bZ. Computing a lattice basis is a high-dimensional generalization: given a(1), ... , a(n) is an element of Z(m), find a Z-basis of the lattice L = {Sigma(n)(i=1) x(i)a(i), x(i) is an element of Z} generated by the a(i)'s. The fastest algorithms known are HNF algorithms, but are not adapted to all applications, such as when the output should not be much longer than the input. We present an algorithm which extracts such a short basis within the same time as an HNF, by reduction to HNF. We also present an HNF-less algorithm, which reduces to Euclid's extended algorithm and can be generalized to quadratic forms. Both algorithms can extend primitive sets into bases.

关键词： lattice algorithms Z-basis HNF XGCD Integer quadratic forms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：