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

randomized algorithms for Distributed Nonlinear Optimization Under Sparsity Constraints

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2016年第6期64卷 1420-1434页

作者： Ravazzi, Chiara Fosson, Sophie M. Magli, Enrico Politecn Torino Dept Elect & Telecommun I-10129 Turin Italy

Distributed optimization in multi-agent systems under sparsity constraints has recently received a lot of attention. In this paper, we consider the in-network minimization of a continuously differentiable nonlinear function which is a combination of local agent objective functions subject to sparsity constraints on the variables. A crucial issue of in-network optimization is the handling of the communications, which may be expensive. This calls for efficient algorithms, that are able to reduce the number of required communication links and transmitted messages. To this end, we focus on asynchronous and randomized distributed techniques. Based on consensus techniques and iterative hard thresholding methods, we propose three methods that attempt to minimize the given function, promoting sparsity of the solution: asynchronous hard thresholding (AHT), broadcast hard thresholding (BHT), and gossip hard thresholding (GHT). Although similar in many aspects, it is difficult to obtain a unified analysis for the proposed algorithms. Specifically, we theoretically prove the convergence and characterize the limit points of AHT in regular networks under some proper assumptions on the functions to be minimized. For BHT and GHT, instead, we characterize the fixed points of the maps that rule their dynamics in terms of stationary points of original problem. Finally, we illustrate the implementation of our techniques in compressed sensing and present several numerical results on performance and number of transmissions required for convergence.

关键词： Distributed optimization nonlinear optimization randomized algorithms sparse signal recovery

来源：评论

学校读者我要写书评

暂无评论

randomized algorithms for generalized Hermitian eigenvalue problems with application to computing Karhunen-Loeve expansion

引用

NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS 2016年第2期23卷 314-339页

作者： Saibaba, Arvind K. Lee, Jonghyun Kitanidis, Peter K. Stanford Univ Inst Computat & Math Engn Huang Bldg 475 Via Ortega Stanford CA 94305 USA

We describe randomized algorithms for computing the dominant eigenmodes of the generalized Hermitian eigenvalue problem Ax = Bx, with A Hermitian and B Hermitian and positive definite. The algorithms we describe only require forming operations Ax,Bx and B(-1)x and avoid forming square roots of B (or operations of the form, B(1/2)x or B(-1/2)x). We provide a convergence analysis and a posteriori error bounds and derive some new results that provide insight into the accuracy of the eigenvalue calculations. The error analysis shows that the randomized algorithm is most accurate when the generalized singular values of B(-1)A decay rapidly. A randomized algorithm for the generalized singular value decomposition is also provided. Finally, we demonstrate the performance of our algorithm on computing an approximation to the Karhunen-Loeve expansion, which involves a computationally intensive generalized Hermitian eigenvalue problem with rapidly decaying eigenvalues. Copyright (c) 2015 John Wiley & Sons, Ltd.

关键词： randomized algorithms generalized Hermitian eigenvalue problems Karhunen-Loeve expansion

来源：评论

学校读者我要写书评

暂无评论

Sequential randomized algorithms for Convex Optimization in the Presence of Uncertainty

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2016年第9期61卷 2565-2571页

作者： Chamanbaz, Mohammadreza Dabbene, Fabrizio Tempo, Roberto Venkataramanan, Venkatakrishnan Wang, Qing-Guo Data Storage Inst Singapore 138632 Singapore Natl Univ Singapore Dept Elect & Comp Engn Singapore 119077 Singapore Politecn Torino CNR IEIIT I-10129 Turin Italy

In this technical note, we propose new sequential randomized algorithms for convex optimization problems in the presence of uncertainty. A rigorous analysis of the theoretical properties of the solutions obtained by these algorithms, for full constraint satisfaction and partial constraint satisfaction, respectively, is given. The proposed methods allow to enlarge the applicability of the existing randomized methods to real-world applications involving a large number of design variables. Since the proposed approach does not provide a priori bounds on the sample complexity, extensive numerical simulations, dealing with an application to hard-disk drive servo design, are provided. These simulations testify the goodness of the proposed solution.

关键词： Convex optimization hard-disk servo design randomized algorithms sequential algorithms

来源：评论

学校读者我要写书评

暂无评论

randomized algorithms for Scheduling VMs in the Cloud

Randomized Algorithms for Scheduling VMs in the Cloud

引用

Annual IEEE International Conference on Computer Communications

作者： Javad Ghaderi Electrical Engineering Department Columbia University

ISBN: (纸本)9781467399548

We consider the problem of scheduling VMs (Virtual Machines) in a multi-server system motivated by cloud computing applications. VMs arrive dynamically over time and require various amounts of resources (e.g., CPU, Memory, Storage, etc.) for the duration of their service. When a VM arrives, it is queued and later served by one of the servers that has sufficient remaining capacity to serve it. The scheduling of VMs is subject to: (i) packing constraints, i.e., multiple VMs can be be served simultaneously by a single server if their cumulative resource requirement does not violate the capacity of the server, and (ii) non-preemption, i.e., once a VM is scheduled in a server, it cannot be interrupted or migrated to another server. To achieve maximum throughput, prior results hinge on solving a hard combinatorial problem (Knapsack) at the instances that all the servers become empty (the so-called global refresh times which require synchronization among the servers). The main contribution of this paper is that it resolves these issues. Specifically, we present a class of randomized algorithms for placing VMs in the servers that can achieve maximum throughput without preemptions. The algorithms are naturally distributed, have low complexity, and each queue needs to perform limited operations. Further, our algorithms display good delay performance in simulations, comparable to delay of heuristics that may not be throughput-optimal, and much better than the delay of the prior known throughput-optimal algorithms.

关键词： Servers randomized algorithms virtual machines Voltmeter server systems Queue

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Sequential randomized algorithms for Robust Convex Optimization

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2015年第12期60卷 3356-3361页

作者： Wada, Takayuki Fujisaki, Yasumasa Osaka Univ Grad Sch Informat Sci & Technol Dept Informat & Phys Sci Osaka 5650871 Japan

Sequential randomized algorithms are considered for robust convex optimization which minimizes a linear objective function subject to a parameter dependent convex constraint. Employing convex optimization and random sampling of parameter, these algorithms enable us to obtain a suboptimal solution within reasonable computational time. The suboptimal solution is feasible in a probabilistic sense and the suboptimal value belongs to an interval which contains the optimal value. The maximum of the interval is the optimal value of the robust convex optimization plus a specified tolerance. On the other hand, its minimum is the optimal value of the chance constrained optimization which is a probabilistic relaxation of the robust convex optimization, with high probability.

关键词： Optimization algorithms randomized algorithms robust control

来源：评论

学校读者我要写书评

暂无评论

Learning Sequential and Parallel Runtime Distributions for randomized algorithms

Learning Sequential and Parallel Runtime Distributions for R...

引用

International Conference on Tools with Artificial Intelligence

作者： Alejandro Arbelaez Charlotte Truchet Barry O'Sullivan Insight Centre for Data Analytics Univ. Coll. Cork Cork Ireland LINA Univ. of Nantes Nantes France

ISBN: (纸本)9781509044603

In cloud systems, computation time can be rented by the hour and for a given number of processors. Thus, accurate predictions of the behaviour of both sequential and parallel algorithms has become an important issue, in particular in the case of costly methods such as randomized combinatorial optimization tools. In this work, our objective is to use machine learning to predict performance of sequential and parallel local search algorithms. In addition to classical features of the instances used by other machine learning tools, we consider data on the sequential runtime distributions of a local search method. This allows us to predict with a high accuracy the parallel computation time of a large class of instances, by learning the behaviour of the sequential version of the algorithm on a small number of instances. Experiments with three solvers on SAT and TSP instances indicate that our method works well, with a correlation coefficient of up to 0.85 for SAT instances and up to 0.95 for TSP instances.

关键词： Runtime Algorithm design and analysis Prediction algorithms Parallel algorithms Machine learning algorithms Approximation algorithms Search problems Runtime Algorithm design and analysis Parallel algorithms tabu search Machine learning algorithms Prediction algorithms Sequential Approximation algorithms randomized algorithms Search methods SEMI-AUTOMATIC TRIM College Entrance Examination Board Scholastic Aptitude Test

来源：评论

学校读者我要写书评

暂无评论

PARALLEL randomized TUCKER DECOMPOSITION algorithms

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2024年第2期46卷 A1186-A1213页

作者： Minster, Rachel Li, Zitong Ballard, Grey Wake Wake Forest Univ Winston Salem NC 27109 USA Univ Calif Irvine Irvine CA 92697 USA

The Tucker tensor decomposition is a natural extension of the singular value decomposition (SVD) to multiway data. We propose to accelerate Tucker tensor decomposition algorithms by using randomization and parallelization. We present two algorithms that scale to large data and many processors, significantly reduce both computation and communication cost compared to previous deterministic and randomized approaches, and obtain nearly the same approximation errors. The key idea in our algorithms is to perform randomized sketches with Kronecker-structured random matrices, which reduces computation compared to unstructured matrices and can be implemented using a fundamental tensor computational kernel. We provide probabilistic error analysis of our algorithms and implement a new parallel algorithm for the structured randomized sketch. Our experimental results demonstrate that our combination of randomization and parallelization achieves accurate Tucker decompositions much faster than alternative approaches. We observe up to a 16X speedup over the fastest deterministic parallel implementation on 3D simulation data.

关键词： Key words. Tucker decompositions tensors randomized algorithms parallel algorithms low- rank multilinear algebra

来源：评论

学校读者我要写书评

暂无评论

tttplots compare a perl program to compare time-to-target plots or general runtime distributions of randomized algorithms

引用

OPTIMIZATION LETTERS 2015年第3期9卷 601-614页

作者： Ribeiro, Celso C. Rosseti, Isabel Univ Fed Fluminense Dept Comp Sci BR-24210240 Niteroi RJ Brazil

Run time distributions or time-to-target plots display on the ordinate axis the probability that an algorithm will find a solution at least as good as a given target value within a given running time, shown on the abscissa axis. Given a pair of different randomized algorithms and , we describe a numerical method that gives the probability that finds a solution at least as good as a given target value in a smaller computation time than , for the case where the runtimes of each of the two algorithms follow any runtime distribution. An illustrative example of a numerical application is also reported. We describe the perl program tttplots-compare, developed to compare time-to-target plots or general runtime distribution for measured CPU times of any two randomized heuristics. A listing of the perl program is given, and the program can also be downloaded from http://***/similar to celso/compare-tttplots..

关键词： randomized algorithms GRASP tttplots Metaheuristics Stochastic local search Runtime distributions Algorithm performance Comparison of two algorithms

来源：评论

学校读者我要写书评

暂无评论

Ergodic randomized algorithms and Dynamics Over Networks

引用

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS 2015年第1期2卷 78-87页

作者： Ravazzi, Chiara Frasca, Paolo Tempo, Roberto Ishii, Hideaki Politecn Torino DET I-10129 Turin Italy Univ Twente Dept Appl Math NL-7522 NB Enschede Netherlands Politecn Torino CNR IEIIT I-10129 Turin Italy Tokyo Inst Technol Dept Computat Intelligence & Syst Sci Yokohama Kanagawa 2268502 Japan

algorithms and dynamics over networks often involve randomization and randomization can induce oscillating dynamics that fail to converge in a deterministic sense. Under assumptions of independence across time and linearity of the updates, we show that the oscillations are ergodic if the expected dynamics is stable. We apply this result to three problems of network systems, namely, the estimation from relative measurements, the PageRank computation, and the dynamics of opinions in social networks. In these applications, the randomized dynamics is the asynchronous counterpart of a deterministic (stable) synchronous one. By ergodicity, the deterministic limit can be recovered via a time-averaging operation, which can be performed locally by each node of the network.

关键词： randomized algorithms networks opinion dynamics PageRank problem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：