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

Discontinuous information in the worst case and randomized settings

MATHEMATISCHE NACHRICHTEN 2013年第7期286卷 679-690页

作者： Hinrichs, Aicke Novak, Erich Wozniakowski, Henryk Univ Jena Math Inst D-07737 Jena Germany Columbia Univ Dept Comp Sci New York NY 10027 USA Univ Warsaw Inst Appl Math PL-02097 Warsaw Poland

We believe that discontinuous linear information is never more powerful than continuous linear information for approximating continuous operators. We prove such a result in the worst case setting. In the randomized setting we consider compact linear operators defined between Hilbert spaces. In this case, the use of discontinuous linear information in the randomized setting cannot be much more powerful than continuous linear information in the worst case setting. These results can be applied when function evaluations are used even if function values are defined only almost everywhere. (C) 2012 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim

关键词： Discontinuous information randomized algorithms information-based complexity

来源：评论

学校读者我要写书评

暂无评论

randomized methods based on new Monte Carlo schemes for control and optimization

引用

ANNALS OF OPERATIONS RESEARCH 2011年第1期189卷 343-356页

作者： Polyak, Boris T. Gryazina, Elena N. Russian Acad Sci Inst Control Sci Moscow 117997 Russia

We address randomized methods for control and optimization based on generating points uniformly distributed in a set. For control systems this sets are either stability domain in the space of feedback controllers, or quadratic stability domain, or robust stability domain, or level set for a performance specification. By generating random points in the prescribed set one can optimize some additional performance index. To implement such approach we exploit two modern Monte Carlo schemes for generating points which are approximately uniformly distributed in a given convex set. Both methods use boundary oracle to find an intersection of a ray and the set. The first method is Hit-and-Run, the second is sometimes called Shake-and-Bake. We estimate the rate of convergence for such methods and demonstrate the link with the center of gravity method. Numerical simulation results look very promising.

关键词： randomized algorithms Monte Carlo Optimization Random search Linear systems Stabilization

来源：评论

学校读者我要写书评

暂无评论

randomized Kaczmarz solver for noisy linear systems

引用

BIT NUMERICAL MATHEMATICS 2010年第2期50卷 395-403页

作者： Needell, Deanna Stanford Univ Dept Stat Stanford CA 94305 USA

The Kaczmarz method is an iterative algorithm for solving systems of linear equations Ax=b. Theoretical convergence rates for this algorithm were largely unknown until recently when work was done on a randomized version of the algorithm. It was proved that for overdetermined systems, the randomized Kaczmarz method converges with expected exponential rate, independent of the number of equations in the system. Here we analyze the case where the system Ax=b is corrupted by noise, so we consider the system Axa parts per thousand b+r where r is an arbitrary error vector. We prove that in this noisy version, the randomized method reaches an error threshold dependent on the matrix A with the same rate as in the error-free case. We provide examples showing our results are sharp in the general context.

关键词： randomized algorithms Kaczmarz method Algebraic reconstruction technique

来源：评论

学校读者我要写书评

暂无评论

The randomized algorithm for finding an eigenvector of the stochastic matrix with application to PageRank

引用

DOKLADY MATHEMATICS 2009年第3期79卷 424-427页

作者： Nazin, A. V. Polyak, B. T. RAS Trapeznikov Inst Control Sci Moscow 117997 Russia

The problem of finding the eigenvector corresponding to the largest eigenvalue of a stochastic matrix has numerous applications in ranking search results, multi-agent, consensus, networked control and data mining. The power method is a typical tool for its solution. However randomized methods could be competitors vs standard ones;they require much less calculations for one iteration and are well tailored for distributed computations. We propose a new randomized algorithm and provide upper bound for its rate of convergence which is O(lnN/n), where N is the dimension and n is the number of iterations. The bound looks promising because lnN is not large even for very high dimensions. The algorithm is based on the mirror-descent method for convex stochastic optimization. Applications to PageRank problem are discussed.

关键词： Algorithm Eigenvector Application Eigenvector randomized algorithms Stochastic algorithms dimensions Competitors

来源：评论

学校读者我要写书评

暂无评论

A randomized algorithm for gossiping in radio networks

引用

NETWORKS 2004年第2期43卷 119-124页

作者： Chrobak, M Gasieniec, L Rytter, W Univ Calif Riverside Dept Comp Sci Riverside CA 92521 USA Univ Liverpool Dept Comp Sci Liverpool L69 7ZF Merseyside England Univ Warsaw Inst Informat PL-02097 Warsaw Poland

We present an O(n log(4)n)-time randomized algorithm for gossiping in radio networks with unknown topology. This is the first algorithm for gossiping in this model whose running time is only a polylogarithmic factor away from the optimum. The fastest previously known (deterministic) algorithm for this problem works in time O(n(3/2)log(2)n). (C) 2004 Wiley Periodicals, Inc.

关键词： radio networks gossiping randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Online Dominant Generalized Eigenvectors Extraction via a randomized Algorithm

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2023年第6期72卷 7597-7612页

作者： Cai, Haoyuan Kaloorazi, Maboud Chen, Jie Chen, Wei Richard, Cedric Northwestern Polytech Univ Shenzhen Res & Dev Inst Shenzhen 518063 Peoples R China Northwestern Polytech Univ Sch Marine Sci & Technol Xian 710072 Peoples R China Beijing Jiaotong Univ State Key Lab Rail Traff Control & Safety Beijing 100044 Peoples R China Univ Cote Azur F-06000 Nice France

This paper is concerned with online algorithms for the generalized Hermitian eigenvalue problem (GHEP). We first present an algorithm based on randomization, termed alternate-projections randomized eigenvalue decomposition (APR-EVD), to solve the standard eigenvalue problem. The APR-EVD algorithm is computationally efficient and can be computed by making only one pass through the input matrix. We then develop two online algorithms based on APR-EVD for the dominant generalized eigenvectors extraction. Our proposed algorithms use the fact that GHEP is transformed into a standard eigenvalue problem, however to avert computations of a matrix inverse and inverse of the square root of a matrix, which are prohibitive, they exploit the rank-1 strategy for the transformation. Our algorithms are devised for extracting generalized eigenvectors for scenarios in which observed stochastic signals have unknown covariance matrices. The effectiveness and practical applicability of our proposed algorithms are validated through numerical experiments with synthetic and real-world data.

关键词： Dominant generalized eigenvector extraction fast subspace estimation and tracking matrix decomposition online algorithms randomized algorithms real-time hyperspectral image denoising

来源：评论

学校读者我要写书评

暂无评论

Improved lower bounds on the randomized complexity of graph properties

引用

RANDOM STRUCTURES & algorithms 2007年第3期30卷 427-440页

作者： Chakrabarti, Amit Khot, Subhash Dartmouth Coll Dept Comp Sci Hanover NH 03755 USA Georgia Inst Technol Coll Comp Atlanta GA 30332 USA

We prove a lower bound of Omega(n(4/3) log(1/3) n) on the randomized decision tree complexity of any nontrivial monotone n-vertex graph property, and of any nontrivial monotone bipartite graph property with bipartitions of size it. This improves the previous best bound of Omega(n(4/3)) due to Hajnal (Combinatorica 11 (1991) 131-143). Our proof works by improving a graph packing lemma used in earlier work, and this improvement in turn stems from a novel probabilistic analysis. Graph packing being a well-studied subject in its own right, our improved packing lemma and the probabilistic technique used to prove it may be of independent interest. (c) 2007 Wiley Periodicals, Inc.

关键词： decision trees graph properties complexity randomized algorithms graph packing probabilistic method

来源：评论

学校读者我要写书评

暂无评论

A New randomized Algorithm for Community Detection in Large Networks

引用

IFAC-PapersOnLine 2016年第13期49卷 31-35页

作者： Kirianovskii, Ilia Granichin, Oleg Proskurnikov, Anton Saint Petersburg State University Faculty of Mathematics and Mechanics Research Laboratory for Analysis and Modeling of Social Processes 7-9 Universitetskaya nab. St. Petersburg 199034 Russia ITMO University 61 Bolshoy pr. St. Petersburg 14A Birzhevaya liniya St. Petersburg 199178 199034 Russia Engineering and Technology Institute Groningen University of Groningen Netherlands

The problem of community detection (or clustering) in graphs plays an important role in analysis of complex large-scale networks and big data structures, arising in natural, behavioral and engineering sciences. Examples of such networks include, but are not limited to, World Wide Web (WWW) and Internet, social networks, ecological networks and food webs, cellular and molecular ensembles. A community (or a module) in a graph is a subset of its nodes, whose members are “densely” connected to each other yet have relatively few connections with nodes outside this subset. A number of algorithms to subdivide the nodes of large-scale graphs into communities have recently been proposed; many of them hunt for the graph's partitions of maximal modularity. One of the most efficient graph clustering algorithms of this type is the Multi-Level Aggregation (or “Louvain”) method. In this paper, a randomized counterpart of this algorithm is proposed, which provides a comparable “quality” of graph's clustering, being however much faster on huge graphs. We demonstrate the efficiency of our algorithm, comparing its performance on several “benchmark” large-scale graphs with existing methods. © 2016

关键词： Clustering algorithms Behavioral research Benchmarking Big data Ecology Graph theory Graphic methods Population dynamics Web browsers Distributed parameter systems Ecological networks Engineering science Graph clustering algorithms Networked systems randomized algorithms Sequential learning World wide webs (WWW)

来源：评论

学校读者我要写书评

暂无评论

randomized Competitive Perimeter Defense on a Line

引用

IEEE CONTROL SYSTEMS LETTERS 2024年 8卷 1000-1005页

作者： Bajaj, Shivam Torng, Eric Bopardikar, Shaunak D. Purdue Univ Dept Elect & Comp Engn Lafayette IN 47905 USA Michigan State Univ Dept Comp Sci & Engn E Lansing MI 48824 USA Michigan State Univ Dept Elect & Comp Engn E Lansing MI 48824 USA

We consider a perimeter defense problem in which a vehicle seeks to defend a compact region from mobile intruders in a one-dimensional environment parameterized by the perimeter size relative to the environment and the intruder-to-vehicle speed ratio. The intruders move with fixed speed and direction to reach the perimeter. We present a competitive analysis approach to this problem by measuring the performance of randomized online algorithms for the vehicle against arbitrary inputs, relative to an optimal offline algorithm that has information about entire input sequence in advance. In particular, we characterize regimes in the parameter space in which, for any online randomized algorithm, (i) the competitive ratio has to be at least 2 and (ii) the competitive ratio has to be at least 1.33. We then design three randomized algorithms and characterize their competitive ratios. Finally, we present parameter regime plots that provide insights into parameter ranges in which the algorithms' performances are near optimal.

关键词： Probability distribution Heuristic algorithms Aerospace electronics Games Vehicle routing Surveys Vehicle dynamics Agents-based systems competitive analysis perimeter defense randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

A SUBLINEAR-TIME randomized APPROXIMATION ALGORITHM FOR MATRIX GAMES

引用

OPERATIONS RESEARCH LETTERS 1995年第2期18卷 53-58页

作者： GRIGORIADIS, MD KHACHIYAN, LG Department of Computer Science Rutgers University New Brunswick NJ 08903 USA

This paper presents a parallel randomized algorithm which computes a pair of epsilon-optimal strategies for a given (m,n)matrix game A = [a(ij)] is an element of [-1, 1] in 0(epsilon(-2) log(2)(n+m)) expected time on an (n+m)/log(n+m)-processor EREW PRAM. For any fixed accuracy epsilon > 0, the expected sequential running time of the suggested algorithm is 0((n + m)log(n + m)), which is sublinear in mn, the number of input elements of A. On the other hand, simple arguments are given to show that for epsilon < 1/2, any deterministic algorithm for computing a pair of epsilon-optimal strategies of an (m, n)-mabix game A with +/-1 elements examines a(mn) of its elements. In particular, for m = n the randomized algorithm achieves an almost quadratic expected speedup relative to any deterministic method.

关键词： APPROXIMATION algorithms COMPLEXITY LINEAR PROGRAMMING MATRIX GAMES PARALLEL algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：