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

On the mean square error of randomized averaging algorithms

AUTOMATICA 2013年第8期49卷 2496-2501页

作者： Frasca, Paolo Hendrickx, Julien M. Politecn Torino Dept Math Sci I-10129 Turin Italy Catholic Univ Louvain ICTEAM Inst B-1348 Louvain Belgium

This paper considers randomized discrete-time consensus systems that preserve the average "on average". As a main result, we provide an upper bound on the mean square deviation of the consensus value from the initial average. Then, we apply our result to systems in which few or weakly correlated interactions take place: these assumptions cover several algorithms proposed in the literature. For such systems we show that, when the network size grows, the deviation tends to zero, and that the speed of this decay is not slower than the inverse of the size. Our results are based on a new approach, which is unrelated to the convergence properties of the system. (C) 2013 Elsevier Ltd. All rights reserved.

关键词： Consensus algorithm randomized algorithm Networked estimation

来源：评论

学校读者我要写书评

暂无评论

Fast randomized Iteration: Diffusion Monte Carlo through the Lens of Numerical Linear Algebra

引用

SIAM REVIEW 2017年第3期59卷 547-587页

作者： Lim, Lek-Heng Weare, Jonathan Univ Chicago Dept Stat Chicago IL 60637 USA Univ Chicago James Franck Inst Dept Stat 5640 S Ellis Ave Chicago IL 60637 USA

We review the basic outline of the highly successful diffusion Monte Carlo technique commonly used in contexts ranging from electronic structure calculations to rare event simulation and data assimilation, and propose a new class of randomized iterative algorithms based on similar principles to address a variety of common tasks in numerical linear algebra. From the point of view of numerical linear algebra, the main novelty of the fast randomized iteration schemes described in this article is that they have dramatically reduced operations and storage cost per iteration (as low as constant under appropriate conditions) and are rather versatile: we will show how they apply to the solution of linear systems, eigenvalue problems, and matrix exponentiation, in dimensions far beyond the present limits of numerical linear algebra. While traditional iterative methods in numerical linear algebra were created in part to deal with instances where a matrix (of size O(n(2))) is too big to store, the algorithms that we propose are effective even in instances where the solution vector itself (of size O(n)) may be too big to store or manipulate. In fact, our work is motivated by recent diffusion Monte Carlo based quantum Monte Carlo schemes that have been applied to matrices as large as 10(108) x 10(108). We provide basic convergence results, discuss the dependence of these results on the dimension of the system, and demonstrate dramatic cost savings on a range of test problems.

关键词： dimension reduction randomized algorithm eigenvalue problem matrix exponentiation diffusion Monte Carlo quantum Monte Carlo

来源：评论

学校读者我要写书评

暂无评论

Efficient randomized web-cache replacement schemes using samples from past eviction times

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2002年第4期10卷 441-454页

作者： Psounis, K Prabhakar, B Stanford Univ Dept Elect Engn Stanford CA 94305 USA Stanford Univ Dept Comp Sci Stanford CA 94305 USA

The problem of document replacement in web caches has received much attention in recent research, and it has been shown that the eviction rule "replace the least recently used document" performs poorly in web caches. Instead, it has been shown that using a combination of several criteria, such as the recentness and frequency of use, the size, and the cost of fetching a document, leads to a sizable improvement in hit rate and latency reduction. However, in order to implement these novel schemes, one needs to maintain complicated data structures. We propose randomized algorithms for, approximating any existing web-cache replacement scheme and thereby avoid the need for any data structures. At document-replacement times, the randomized algorithm samples N documents from the cache and replaces the least useful document from the sample, where usefulness is determined according to the criteria mentioned above. The next M < N least useful documents are retained for the succeeding iteration. When the next replacement is to be performed, the algorithm obtains N - M new samples from the cache and replaces the least useful document from the N - M new samples and the M previously retained. Using theory and simulations, we analyze the algorithm and find that it matches the performance of existing document replacement schemes for values of N and M as low as 8 and 2 respectively. Interestingly, we find. that retaining. a small number of samples from one iteration to the next leads to an exponential improvement in performance as compared to retaining no samples at all.

关键词： Cache replacement scheme past samples randomized algorithm Web caching

来源：评论

学校读者我要写书评

暂无评论

A randomized adaptive neighbor discovery for wireless networks with multi-packet reception capability

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2019年 131卷 235-244页

作者： Chae, Sung-Yoon Kang, Kyungran Cho, Young-Jong Korea Railrd Res Inst Control & Commun Res Team Uiwang South Korea Ajou Univ Coll Informat & Technol Suwon South Korea

Neighbor discovery is a first step in the initialization of wireless networks in large-scale ad hoc networks. In this paper, we propose a randomized neighbor discovery scheme for wireless networks with a multi packet reception (MPR) capability. We let the nodes to have different advertisement probabilities. The node gradually adjusts its probability according to its operation phases: greedy or slow-start. In the greedy phase, the node advertises aggressively while it does moderately in the slow-start phase. Initial phase and advertisement probability are determined randomly. Then, the nodes change the probability adaptively according to advertisements the reception state from the other nodes. In order to decide the reception state precisely, the exact number of nodes in the network is necessary. To make our proposed scheme work in case of no prior knowledge of the population, we propose a population estimation method based on a maximum likelihood estimation. We evaluate our proposed scheme through numerical analysis and simulation. Through the numerical analysis, we show that the discovery completion time is lower bounded in Theta(N/k) and upper bounded in Theta(NlnN/k) when there exists N nodes with MPR-k capability. The bounds are the same as those of previous studies that propose static optimal advertisement probability. Through the simulation, we evaluate that our adaptive scheme outperforms in terms of discovery completion time, advertisement efficiency, and wasted time slot ratio than a scheme with static advertisement probability when the population of the network is unknown. (C) 2018 Elsevier Inc. All rights reserved.

关键词： Neighbor discovery Wireless network randomized algorithm Multi-packet reception Maximum likelihood estimation Adaptive advertisement

来源：评论

学校读者我要写书评

暂无评论

randomized parameterized algorithms for P₂-Packing and Co-Path Packing problems

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2015年第1期29卷 125-140页

作者： Feng, Qilong Wang, Jianxin Li, Shaohua Chen, Jianer Cent South Univ Sch Informat Sci & Engn Changsha 410083 Hunan Peoples R China Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA

In this paper, we study the Parameterized P-2-Packing problem and Parameterized Co-Path Packing problem from random perspective. For the Parameterized P-2-Packing problem, based on the structure analysis of the problem and using random partition technique, a randomized parameterized algorithm of running time O*(6.75(k)) is obtained, improving the current best result O*(8(k)). For the Parameterized Co-Path Packing problem, we firstly study the kernel and randomized algorithm for the degree-bounded instance, where each vertex in the instance has degree at most three. A kernel of size 20k and a randomized algorithm of running time O*(2(k)) are given for the Parameterized Co-Path Packing problem with bounded degree constraint. By applying iterative compression technique and based on the randomized algorithm for degree bounded problem, a randomized algorithm of running time O*(3(k)) is given for the Parameterized Co-Path Packing problem.

关键词： P-2-Packing Co-Path Packing randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Low-rank approximation of large-scale matrices via randomized methods

引用

JOURNAL OF SUPERCOMPUTING 2018年第2期74卷 830-844页

作者： Hatamirad, Sarvenaz Pedram, Mir Mohsen Kharazmi Univ Dept Elect & Comp Engn Fac Engn Tehran Iran

Decomposition of a matrix into low-rank matrices is a powerful tool for scientific computing and data analysis. The purpose is to obtain a low-rank matrix by decomposition of the original matrix into a product of smaller and lower-rank matrices or by randomly projecting the matrix down to a lower-dimensional space. Such decomposition requires less storage and computational burden. The focus of this paper is on randomized methods which try as much as possible to preserve the original matrix properties by applying the subspace sampling. In many applications, randomized algorithms in terms of accuracy, stability and speed are much better than the classical decomposition algorithms. In this study, we propose a sparse orthogonal transformation matrix to reduce the dimension of the data. The results show that compared with the most accurate methods, the transformation speed is much faster and can save a lot of memory in the case of huge matrices.

关键词： Matrix approximation Dimension reduction randomized algorithm Johnson-Lindenstrauss lemma Random matrix Column subset selection Big data

来源：评论

学校读者我要写书评

暂无评论

randomized block Krylov subspace methods for trace and log-determinant estimators

引用

BIT NUMERICAL MATHEMATICS 2021年第3期61卷 911-939页

作者： Li, Hanyu Zhu, Yuanyang Chongqing Univ Coll Math & Stat Chongqing 401331 Peoples R China

We present randomized algorithms based on block Krylov subspace methods for estimating the trace and log-determinant of Hermitian positive semi-definite matrices. Using the properties of Chebyshev polynomials and Gaussian random matrix, we provide the error analysis of the proposed estimators and obtain the expectation and concentration error bounds. These bounds improve the corresponding ones given in the literature. Numerical experiments are presented to illustrate the performance of the algorithms and to test the error bounds.

关键词： randomized algorithm Krylov subspace method Trace estimator Log-determinant estimator Chebyshev polynomials

来源：评论

学校读者我要写书评

暂无评论

A block-randomized stochastic method with importance sampling for CP tensor decomposition

引用

ADVANCES IN COMPUTATIONAL MATHEMATICS 2024年第2期50卷 1-27页

作者： Yu, Yajie Li, Hanyu Chongqing Univ Coll Math & Stat Chongqing 401331 Peoples R China

One popular way to compute the CANDECOMP/PARAFAC (CP) decomposition of a tensor is to transform the problem into a sequence of overdetermined least squares subproblems with Khatri-Rao product (KRP) structure involving factor matrices. In this work, based on choosing the factor matrix randomly, we propose a mini-batch stochastic gradient descent method with importance sampling for those special least squares subproblems. Two different sampling strategies are provided. They can avoid forming the full KRP explicitly and computing the corresponding probabilities directly. The adaptive step size version of the method is also given. For the proposed method, we present its theoretical properties and comprehensive numerical performance. The results on synthetic and real data show that our method is effective and efficient, and for unevenly distributed data, it performs better than the corresponding one in the literature.

关键词： CP decomposition Importance sampling Stochastic gradient descent Khatri-Rao product randomized algorithm Adaptive algorithm

来源：评论

学校读者我要写书评

暂无评论

On the properties of the exceptional set for the randomized Euler and Runge-Kutta schemes

引用

ADVANCES IN COMPUTATIONAL MATHEMATICS 2023年第2期49卷 1-16页

作者： Bochacik, Tomasz AGH Univ Sci & Technol Fac Appl Math Al A Mickiewicza 30 PL-30059 Krakow Poland

We show that the probability of the exceptional set decays exponentially for a broad class of randomized algorithms approximating solutions of ODEs, admitting a certain error decomposition. This class includes randomized explicit and implicit Euler schemes, and the randomized two-stage Runge-Kutta scheme (under inexact information). We design a confidence interval for the exact solution of an IVP and perform numerical experiments to illustrate the theoretical results.

关键词： Exceptional set Confidence region Noisy information randomized algorithm Explicit and implicit Euler schemes Two-stage Runge-Kutta scheme

来源：评论

学校读者我要写书评

暂无评论

randomized Generalized Singular Value Decomposition

引用

Communications on Applied Mathematics and Computation 2021年第1期3卷 137-156页

作者： Wei Wei Hui Zhang Xi Yang Xiaoping Chen College of Science Nanjing University of Aeronautics and AstronauticsNanjing 210016China College of Jincheng Nanjing University of Aeronautics and AstronauticsNanjing 211156China Department of Mathematics Taizhou UniversityTaizhou 225300Zhejiang ProvinceChina

The generalized singular value decomposition(GSVD)of two matrices with the same number of columns is a very useful tool in many practical ***,the GSVD may suffer from heavy computational time and memory requirement when the scale of the matrices is quite *** this paper,we use random projections to capture the most of the action of the matrices and propose randomized algorithms for computing a low-rank approximation of the *** error bounds of the approximation are also presented for the proposed randomized ***,some experimental results show that the proposed randomized algorithms can achieve a good accuracy with less computational cost and storage requirement.

关键词： Generalized singular value decomposition randomized algorithm Low-rank approximation Error analysis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：