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

randomized approaches to accelerate MCMC algorithms for Bayesian inverse problems

JOURNAL OF COMPUTATIONAL PHYSICS 2021年 440卷 110391-110391页

作者： Saibaba, Arvind K. Prasad, Pranjal de Sturler, Eric Miller, Eric Kilmer, Misha E. North Carolina State Univ Dept Math Raleigh NC 27513 USA Virginia Tech Dept Math Blacksburg VA 24061 USA Tufts Univ Dept Elect & Comp Engn Medford MA 02155 USA Tufts Univ Dept Math Medford MA 02155 USA

Markov chain Monte Carlo (MCMC) approaches are traditionally used for uncertainty quantification in inverse problems where the physics of the underlying sensor modality is described by a partial differential equation (PDE). However, the use of MCMC algorithms is prohibitively expensive in applications where each log-likelihood evaluation may require hundreds to thousands of PDE solves corresponding to multiple sensors;i.e., spatially distributed sources and receivers perhaps operating at different frequencies or wavelengths depending on the precise application. We show how to mitigate the computational cost of each log-likelihood evaluation by using several randomized techniques and embed these randomized approximations within MCMC algorithms. The resulting MCMC algorithms are computationally efficient methods for quantifying the uncertainty associated with the reconstructed parameters. We demonstrate the accuracy and computational benefits of our proposed algorithms on a model application from diffuse optical tomography where we invert for the spatial distribution of optical absorption. (C) 2021 Elsevier Inc. All rights reserved.

关键词： Inverse problems randomized algorithms Bayesian methods Markov chain Monte Carlo

来源：评论

学校读者我要写书评

暂无评论

randomized distributed online algorithms against adaptive offline adversaries

引用

INFORMATION PROCESSING LETTERS 2020年 161卷 105973-105973页

作者： Boyar, Joan Ellen, Faith Larsen, Kim S. Univ Southern Denmark Dept Math & Comp Sci Campusvej 55 DK-5230 Odense M Denmark Univ Toronto Dept Comp Sci 10 Kings Coll Rd Toronto ON M5S 3G4 Canada

In the sequential setting, a decades-old fundamental result in online algorithms states that if there is a c-competitive randomized online algorithm against an adaptive, offline adversary, then there is a c-competitive deterministic algorithm. The adaptive, offline adversary is the strongest adversary among the ones usually considered, so the result states that if one has to be competitive against such a strong adversary, then randomization does not help. This implies that researchers do not consider randomization against an adaptive, offline adversary. We prove that in a distributed setting, this result does not necessarily hold, so randomization against an adaptive, offline adversary becomes interesting again. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Online algorithms randomized algorithms Adaptive offline adversary Distributed systems

来源：评论

学校读者我要写书评

暂无评论

Efficient randomized tensor-based algorithms for function approximation and low-rank kernel interactions

引用

ADVANCES IN COMPUTATIONAL MATHEMATICS 2022年第5期48卷 66-66页

作者： Saibaba, Arvind K. Minster, Rachel Kilmer, Misha E. North Carolina State Univ Dept Math Raleigh NC 27695 USA Wake Forest Univ Dept Comp Sci Winston Salem NC 27101 USA Tufts Univ Dept Math Medford MA 02155 USA

In this paper, we introduce a method for multivariate function approximation using function evaluations, Chebyshev polynomials, and tensor-based compression techniques via the Tucker format. We develop novel randomized techniques to accomplish the tensor compression, provide a detailed analysis of the computational costs, provide insight into the error of the resulting approximations, and discuss the benefits of the proposed approaches. We also apply the tensor-based function approximation to develop low-rank matrix approximations to kernel matrices that describe pairwise interactions between two sets of points;the resulting low-rank approximations are efficient to compute and store (the complexity is linear in the number of points). We present an adaptive version of the function and kernel approximation that determines an approximation that satisfies a user-specified relative error over a set of random points. We extend our approach to the case where the kernel requires repeated evaluations for many values of (hyper)parameters that govern the kernel. We give detailed numerical experiments on example problems involving multivariate function approximation, low-rank matrix approximations of kernel matrices involving well-separated clusters of sources and target points, and a global low-rank approximation of kernel matrices with an application to Gaussian processes. We observe speedups up to 18X over standard matrix-based approaches.

关键词： Multivariate function approximation Tucker format randomized algorithms Low-rank approximations Kernel methods

来源：评论

学校读者我要写书评

暂无评论

randomized protocols for duplicate elimination in peer-to-peer storage systems

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2007年第5期18卷 686-696页

作者： Ferreira, Ronaldo A. Ramanathan, Murali K. Grama, Ananth Jagannathan, Suresh Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

Distributed peer-to-peer systems rely on voluntary participation of peers to effectively manage a storage pool. In such systems, data is generally replicated for performance and availability. If the storage associated with replication is not monitored and provisioned, the underlying benefits may not be realized. Resource constraints, performance scalability, and availability present diverse considerations. Availability and performance scalability, in terms of response time, are improved by aggressive replication, whereas resource constraints limit total storage in the network. Identification and elimination of redundant data pose fundamental problems for such systems. In this paper, we present a novel and efficient solution that addresses availability and scalability with respect to management of redundant data. Specifically, we address the problem of duplicate elimination in the context of systems connected over an unstructured peer-to-peer network in which there is no a priori binding between an object and its location. We propose two randomized protocols to solve this problem in a scalable and decentralized fashion that does not compromise the availability requirements of the application. Performance results using both large-scale simulations and a prototype built on PlanetLab demonstrate that our protocols provide high probabilistic guarantees while incurring minimal administrative overheads.

关键词： peer-to-peer unstructured networks duplicate elimination randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

randomized splay trees: Theoretical and experimental results

引用

INFORMATION PROCESSING LETTERS 2002年第4期81卷 213-221页

作者： Albers, S Karpinski, M Univ Dortmund Lehrstuhl Informat 2 D-44221 Dortmund Germany Univ Bonn Dept Comp Sci D-53117 Bonn Germany

Splay trees are self-organizing binary search trees that were introduced by Sleator and Tarjan [J. ACM 32 (1985) 652-686]. In this paper we present a randomized variant of these trees. The new algorithm for reorganizing the tree is both simple and easy to implement. We prove that our randomized splaying scheme has the same asymptotic performance as the original deterministic scheme but improves constants in the expected running time. This is interesting in practice because the search time in splay trees is typically higher than the search time in skip lists and AVL-trees. We present a detailed experimental study of our algorithm. On request sequences generated by fixed probability distributions, we can achieve improvements of up to 25% over deterministic splaying. On request sequences that exhibit high locality of reference, the improvements are minor. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： data structures randomized algorithms splay trees

来源：评论

学校读者我要写书评

暂无评论

A PRACTICAL randomized CP TENSOR DECOMPOSITION

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2018年第2期39卷 876-901页

作者： Battaglino, Casey Ballard, Grey Kolda, Tamara G. Georgia Inst Technol Computat Sci & Engn Atlanta GA 30332 USA Wake Forest Univ Comp Sci Winston Salem NC 27109 USA Sandia Natl Labs Livermore CA 94551 USA

The CANDECOMP/ PARAFAC (CP) decomposition is a leading method for the analysis of multiway data. The standard alternating least squares algorithm for the CP decomposition (CP-ALS) involves a series of highly overdetermined linear least squares problems. We extend randomized least squares methods to tensors and show that the workload of CP-ALS can be drastically reduced without a sacrifice in quality. We introduce techniques for efficiently preprocessing, sampling, and computing randomized least squares on a dense tensor of arbitrary order, as well as an efficient sampling-based technique for checking the stopping condition. We also show more generally that the Khatri-Rao product (used within the CP-ALS iteration) produces conditions favorable for direct sampling. In numerical results, we see improvements in speed, reductions in memory requirements, and robustness with respect to initialization.

关键词： canonical polyadic tensor decomposition CANDECOMP/PARAFAC (CP) multilinear algebra randomized algorithms randomized least squares

来源：评论

学校读者我要写书评

暂无评论

randomized EXTENDED KACZMARZ FOR SOLVING LEAST SQUARES

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2013年第2期34卷 773-793页

作者： Zouzias, Anastasios Freris, Nikolaos M. Univ Toronto Dept Comp Sci Toronto ON Canada Ecole Polytech Fed Lausanne Sch Comp & Commun Sci IC CH-1015 Lausanne Switzerland

We present a randomized iterative algorithm that exponentially converges in the mean square to the minimum l(2)-norm least squares solution of a given linear system of equations. The expected number of arithmetic operations required to obtain an estimate of given accuracy is proportional to the squared condition number of the system multiplied by the number of nonzero entries of the input matrix. The proposed algorithm is an extension of the randomized Kaczmarz method that was analyzed by Strohmer and Vershynin.

关键词： linear least squares minimum-length solution sparse matrix overdetermined system underdetermined system iterative method random sampling LAPACK randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Fighting fire with fire: Using randomized gossip combat stochastic scalability limits

引用

QUALITY AND RELIABILITY ENGINEERING INTERNATIONAL 2002年第3期18卷 165-184页

作者： Gupta, I Birman, KP Van Renesse, R Cornell Univ Dept Comp Sci Ithaca NY 14853 USA

The mechanisms used to improve the reliability of distributed systems often limit performance and scalability. Focusing on one widely-used definition of reliability, we explore the origins of this phenomenon and conclude that it reflects a tradeoff arising deep within the typical protocol stack. Specifically, we suggest that protocol designs often disregard the high cost of infrequent events. When a distributed system is scaled, both the frequency and the overall cost of such events often grow with the size of the system. This triggers an O(n(2)) phenomenon, which becomes visible above some threshold sizes. Our findings suggest that it would be more effective to construct large-scale reliable systems where, unlike traditional protocol stacks, lower layers use randomized mechanisms, with probabilistic guarantees, to overcome low-probability events. Reliability and other end-to-end properties are introduced closer to the application. We employ a back-of-the-envelope analysis to quantify this phenomenon for a class of strongly reliable multicast problems. We construct a non-traditional stack, as described above, that implements virtually synchronous multicast. Experimental results reveal that virtual synchrony over a non-traditional, probabilistic stack helps break through the scalability barrier faced by traditional implementations of the protocol. Copyright (C) 2002 John Wiley Sons, Ltd.

关键词： group communication reliable multicast scalability randomized algorithms non-traditional stack virtual synchrony

来源：评论

学校读者我要写书评

暂无评论

Complexity of solving nonlinear equations in the deterministic, randomized and quantum settings

引用

APPLIED MATHEMATICS AND COMPUTATION 2013年 224卷 652-662页

作者： Gocwin, Maciej Kacewicz, Boleslaw AGH Univ Sci & Technol Fac Appl Math PL-30059 Krakow Poland

We consider the root finding of a real-valued function f defined on the d-dimensional unit cube. We assume that f has r continuous partial derivatives, with all partial derivatives of order r being Holder functions with the exponent rho. We study the epsilon-complexity of this problem in three settings: deterministic, randomized and quantum. It is known that with the root error criterion the deterministic epsilon-complexity is infinite, i.e., the problem is unsolvable. We show that the same holds in the randomized and quantum settings. Under the residual error criterion, we show that the deterministic and randomized epsilon-complexity is of order epsilon(-d/(r+rho)). In the quantum setting, the epsilon-complexity is shown to be of order epsilon(-d/(2(r+rho))). This means that a quadratic speed-up is achieved on a quantum computer. (C) 2013 Elsevier Inc. All rights reserved.

关键词： Nonlinear equations Deterministic algorithms randomized algorithms Quantum algorithms Optimality Complexity

来源：评论

学校读者我要写书评

暂无评论

randomized routing, selection, and sorting on the OTIS-mesh

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1998年第9期9卷 833-840页

作者： Rajasekaran, S Sahni, S Univ Florida Dept Comp Sci & Informat Engn Gainesville FL 32611 USA

The Optical Transpose Interconnection System (OTIS) is a recently proposed model of computing that exploits the special features of both electronic and optical technologies. in this paper we present efficient algorithms for packet routing, sorting, and selection on the OTIS-Mesh. The diameter of an N-2-processor OTIS-Mesh is 4 root N - 3. We present an algorithm for routing any partial permutation in 4 root N + o(root N) time. Our selection algorithm runs in time 6 root N + o(root N) and our sorting algorithm runs in 8 root N + o(root N) time. All these algorithms are randomized and the stated time bounds hold with high probability. Also, the queue size needed for these algorithms is O(1) with high probability.

关键词： optical computing mesh-connected computers parallel algorithms sorting packet routing selection randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：