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

40th IEEE Conference on Decision and Control

作者： Oishi, Y Kimura, H Univ Tokyo Grad Sch Informat Sci & Technol Dept Math Informat Bunkyo Ku Tokyo 1130033 Japan

ISBN: (纸本)0780370619

The randomized algorithm of Calafiore and Polyak, which consists of random sampling and subgradient descent, is analyzed in the case that it is used to solve parameter-dependent linear matrix inequalities. This paper shows that the expected time to achieve a solution is infinite if this algorithm is used in its original form. However, it is also shown that the algorithm can be improved so that its expected achievement time becomes finite. An explicit upper bound of the expected achievement time is given in a special case. A numerical example is provided.

关键词： randomized algorithms parameter-dependent linear matrix inequalities computational complexity curse of dimensionality linear parameter-varying systems

来源：评论

学校读者我要写书评

暂无评论

randomized algorithms to Update Partial Singular Value Decomposition on a Hybrid CPU/GPU Cluster 15

Randomized Algorithms to Update Partial Singular Value Decom...

引用

International Conference for High Performance Computing, Networking, Storage and Analysis (SC)

作者： Yamazaki, Ichitaro Kurzak, Jakub Luszczek, Piotr Dongarra, Jack Univ Tennessee Dept Elect Engn & Comp Sci Knoxville TN 37996 USA

ISBN: (纸本)9781450337236

For data analysis, a partial singular value decomposition (SVD) of the sparse matrix representing the data is a powerful tool. However, computing the SVD of a large matrix can take a significant amount of time even on a current high-performance supercomputer. Hence, there is a growing interest in a novel algorithm that can quickly compute the SVD for efficiently processing massive amounts of data that are being generated from many modern applications. To respond to this demand, in this paper, we study randomized algorithms that update the SVD as changes are made to the data, which is often more efficient than recomputing the SVD from scratch. Furthermore, in some applications, recomputing the SVD may not be possible because the original data, for which the SVD has been already computed, is no longer available. Our experimental results with the data sets for the Latent Semantic Indexing and population clustering demonstrate that these randomized algorithms can obtain the desired accuracy of the SVD with a small number of data accesses, and compared to the state-of-the-art updating algorithm, they often require much lower computational and communication costs. Our performance results on a hybrid CPU/GPU cluster show that these randomized algorithms can obtain significant speedups over the state-of-the-art updating algorithm.

关键词： Clustering algorithms Sparse matrices Algorithm design and analysis Approximation algorithms Sociology Statistics Singular value decomposition Singular value decomposition Swine vesicular disease randomized algorithms Sparse matrix Algorithm design and analysis Clustering algorithms Sociology Approximation algorithms updating algorithm

来源：评论

学校读者我要写书评

暂无评论

randomized algorithms for the majority problem

引用

Electronic Notes in Discrete Mathematics 2009年 34卷 453-457页

作者： Christofides, Demetres School of Mathematics University of Birmingham Birmingham United Kingdom

In the majority problem, we are given n balls coloured black or white and we are allowed to query whether two balls have the same colour or not. The goal is to find a ball of majority colour in the minimum number of queries. The answer is known to be n - B (n), where B (n) is the number of 1's in the binary representation of n. In [G. De Marco and A. Pelc, randomized algorithms for determining the majority on graphs, Combin. Probab. Comput. 15 (2006), 823-834], De Marco and Pelc proved that even if we use a randomized algorith which is allowed to fail with probability at most ε, we still need linear expected time to determine a ball in majority colour. We prove that any such algorithm has expected running time at least (frac(2, 3) - δ (ε)) n, where δ (ε) → 0 as ε → 0. Moreover, we provide a randomized algorithm showing that this result is best possible. © 2009 Elsevier B.V. All rights reserved.

关键词： majority problem randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

COMPETITIVE randomized algorithms FOR NONUNIFORM PROBLEMS

引用

ALGORITHMICA 1994年第6期11卷 542-571页

作者： KARLIN, AR MANASSE, MS MCGEOCH, LA OWICKI, S AMHERST COLL DEPT MATH & COMP SCIAMHERSTMA 01002

Competitive analysis is concerned with comparing the performance of on-line algorithms with that of optimal off-line algorithms. In some cases randomization can lead to algorithms with improved performance ratios on worst-case sequences. In this paper we present new ramdomized on-line algorithms for snoopy caching and the spin-block problem. These algorithms achieve competitive ratios approaching e/(e - 1) almost-equal-to 1.58 against an oblivious adversary. These ratios are optimal and are a surprising improvement over the best possible ratio in the deterministic case, which is 2. We also consider the situation when the request sequences for these problems are generated according to an unknown probability distribution. In this case we show that deterministic algorithms that adapt to the observed request statistics also have competitive factors approaching e/(e - 1). Finally, we obtain randomized algorithms for the 2-server problem on a class of isosceles triangles. These algorithms are optimal against an oblivious adversary and have competitive ratios that approach e/(e - 1). This compares with the ratio of 3/2 that can be achieved on an equilateral triangle.

关键词： ONLINE algorithms COMPETITIVE ANALYSIS randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Computational complexity of randomized algorithms for solving parameter-dependent linear matrix inequalities

引用

AUTOMATICA 2003年第12期39卷 2149-2156页

作者： Oishi, Y Kimura, H Univ Tokyo Grad Sch Informat Sci & Technol Dept Math Informat Bunkyo Ku Tokyo 1138656 Japan Univ Tokyo Grad Sch Frontier Sci Dept Complex Sci & Engn Bunkyo Ku Tokyo 1130033 Japan

randomized algorithms are proposed for solving parameter-dependent linear matrix inequalities and their computational complexity is analyzed. The first proposed algorithm is an adaptation of the algorithms of Polyak and Tempo [(Syst. Control Lett. 43(5) (2001) 343)] and Calafiore and Polyak [(IEEE Trans. Autom. Control 46 (11) (2001) 1755)] for the present problem. It is possible however to show that the expected number of iterations necessary to have a deterministic solution is infinite. In order to make this number finite, the improved algorithm is proposed. The number of iterations necessary to have a probabilistic solution is also considered and is shown to be independent of the parameter dimension. A numerical example is provided. (C) 2003 Elsevier Ltd. All rights reserved.

关键词： randomized algorithms parameter-dependent linear matrix inequalities computational complexity conservatism curse of dimensionality linear parameter-varying systems

来源：评论

学校读者我要写书评

暂无评论

Some applications of randomized algorithms for control system design

引用

AUTOMATICA 2002年第12期38卷 2085-2092页

作者： Patel, VV Deodhare, G Viswanath, T Ctr Artificial Intelligence & Robot Bangalore 560001 Karnataka India Univ Twente Fac Math Sci NL-7500 AE Enschede Netherlands

In this paper a few "difficult" problems related to simultaneous stabilization of three plants (equivalent to a certain problem related to unit interpolation in H.) have been addressed through the framework of randomized algorithms. These problems which were proposed by Blondel (Simultaneous Stabilization of Linear Systems, Springer, Berlin, 1994) and Blondel and Gevers (Math. Control Signals Systems 6 (1994) 135) concern the existence of a controller. (C) 2002 Elsevier Science Ltd. All rights reserved.

关键词： simultaneous stabilization of three plants unit interpolation in H-infinity randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

THE COMPETITIVENESS OF randomized algorithms FOR ONLINE STEINER TREE AND ONLINE SPANNING TREE PROBLEMS

引用

INFORMATION PROCESSING LETTERS 1993年第4期48卷 177-182页

作者： TSAI, YT TANG, CY NATL TSING HUA UNIV DEPT COMP SCIHSINCHU 300TAIWAN

This paper considers a family of randomized on-line algorithms, Algorithm R(m), where 1 less-than-or-equal-to m less-than-or-equal-to n - 1 and n is the number of input points, for the on-line Steiner tree and on-line spanning tree problems on Euclidean space. Our main result is that if m is a fixed constant, the competitive ratios of Algorithm R(m) for the on-line Steiner tree and spanning tree problems are THETA(n). We also show that the competitive ratio of Algorithm R(n - 1), which is deterministic greedy algorithm, for the on-line spanning tree problem is the same as that for the on-line Steiner tree problem, which is O(log n).

关键词： ANALYSIS OF algorithms ONLINE algorithms randomized algorithms COMPETITIVE ANALYSIS ONLINE STEINER TREE PROBLEM ONLINE SPANNING TREE PROBLEM

来源：评论

学校读者我要写书评

暂无评论

Worst-case properties of the uniform distribution and randomized algorithms for robustness analysis

引用

MATHEMATICS OF CONTROL SIGNALS AND SYSTEMS 1998年第3期11卷 183-196页

作者： Bai, EW Tempo, R Fu, MY Univ Iowa Dept Elect & Comp Engn Iowa City IA 52242 USA Politecn Torino CNR CENS Turin Italy Univ Newcastle Dept Elect & Comp Engn Newcastle NSW 2308 Australia

In this paper we study a probabilistic approach which is an alternative to the classical worst-case algorithms for robustness analysis and design of uncertain control systems. That is, we aim to estimate the probability that a control system with uncertain parameters q restricted to a box I! attains a given level of performance gamma. Since this probability depends on the underlying distribution, we address the following question: What is a "reasonable" distribution so that the estimated probability makes sense? To answer this question, we define two worst-case criteria and prove that the uniform distribution is optimal in both cases. In the second part of the paper we turn our attention to a subsequent problem. That is, we estimate the sizes of both the so-called "good" and "bad" sets via sampling. Roughly speaking, the good set contains the parameters q is an element of Q with a performance level better than or equal to gamma while the bad set is the set of parameters q is an element of Q with a performance level worse than gamma. We give bounds on the minimum sample size to attain a good estimate of these sets in a certain probabilistic sense.

关键词： randomized algorithms robustness analysis uncertain parameters

来源：评论

学校读者我要写书评

暂无评论

Fault Detection for Non-Gaussian Processes Using Generalized Canonical Correlation Analysis and randomized algorithms

引用

IEEE TRANSACTIONS ON INDUSTRIAL ELECTRONICS 2018年第2期65卷 1559-1567页

作者： Chen, Zhiwen Ding, Steven X. Peng, Tao Yang, Chunhua Gui, Weihua Cent South Univ Sch Informat Sci & Engn Changsha 410083 Hunan Peoples R China Univ Duisburg Essen Inst Automat Control & Complex Syst AKS D-47057 Duisburg Germany

In this paper, we first study a generalized canonical correlation analysis (CCA)-based fault detection (FD) method aiming at maximizing the fault detectability under an acceptable false alarm rate. More specifically, two residual signals are generated for detecting of faults in input and output subspaces, respectively. The minimum covariances of the two residual signals are achieved by taking the correlation between input and output into account. Considering the limited application scope of the generalized CCA due to the Gaussian assumption on the process noises, an FD technique combining the generalized CCA with the threshold-setting based on the randomized algorithm is proposed and applied to the simulated traction drive control system of high-speed trains. The achieved results show that the proposed method is able to improve the detection performance significantly in comparison with the standard generalized CCA-based FD method.

关键词： Canonical correlation analysis (CCA) fault detection non-Gaussian process randomized algorithms traction drive control system (TDCS)

来源：评论

学校读者我要写书评

暂无评论

Distributed randomized algorithms for probabilistic performance analysis

引用

SYSTEMS & CONTROL LETTERS 2009年第3期58卷 202-212页

作者： Calafiore, Giuseppe Carlo Politecn Torino Dipartimento Automat & Informat I-10129 Turin Italy

randomized algorithms are a useful tool for analyzing the performance of complex uncertain systems. Their implementation requires the generation of a large number N of random samples representing the uncertainty scenarios, and the corresponding evaluation of system performance. When N is very large and/or performance evaluation is costly or time consuming, it can be necessary to distribute the computational burden of such algorithms among many cooperating computing units. This paper studies distributed versions of randomized algorithms for expected value, probability and extrema estimation over a network of computing nodes with possibly time-varying communication links. Explicit a priori bounds are provided for the sample and communication complexity of these algorithms in terms of number of local samples, number of computing nodes and communication iterations. (C) 2008 Elsevier B.V. All rights reserved.

关键词： randomized algorithms Probabilistic robustness Distributed estimation Consensus and agreement problems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：