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

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Kasturi Varadarajan Xin Xiao Department of Computer Science University of Iowa

ISBN: (纸本)9781611972108

We consider the problem of projective clustering in Euclidean spaces of non-fixed dimension. Here, we are given a set P of n points in R~m and integers j ≥ 1, k ≥ 0, and the goal is to find j k-subspaces so that the sum of the distances of each point in P to the nearest subspace is minimized. Observe that this is a shape fitting problem where we wish to find the best fit in the L1 sense. Here we will treat the number j of subspaces we want to fit and the dimension k of each of them as constants. We consider instances of projective clustering where the point coordinates are integers of magnitude polynomial in m and n. Our main result is a randomized algorithm that for any ε ＞ 0 runs in time O(mn polylog(mn)) and outputs a solution that with high probability is within (1 ＋ ε) of the optimal solution. To obtain this result, we show that the fixed dimensional version of the above projective clustering problem has a small coreset. We do that by observing that in a fairly general sense, shape fitting problems that have small corsets in the L_∞ setting also have small coresets in the L_1 setting, and then exploiting an existing construction for the L_∞ setting. This observation seems to be quite useful for other shape fitting problems as well, as we demonstrate by constructing the first "regular" coreset for the circle fitting problem in the plane.

关键词： Integer MACHINE SHOP PRACTICE Subspace solidification randomized algorithms Cluster Analysis existing construction (fema)

来源：评论

学校读者我要写书评

暂无评论

Multi-agent Systems Reaching Optimal Consensus Based on Simple Bernoulli Decisions

Multi-agent Systems Reaching Optimal Consensus Based on Simp...

引用

第三十一届中国控制会议

作者： Karl Henrik Johansson ACCESS Linnaeus Centre School of Electrical EngineeringRoyal Institute of TechnologyStockholm 10044Sweden

In this paper,we formulate and solve a randomized optimal consensus problem for multi-agent systems with stochastically time-varying interconnection *** considered multi-agent system with a simple randomized iterating rule achieves an almost sure consensus meanwhile solving the optimization problem min∑~n f（z）,in which the optimal solution set of objective function f corresponding to agent i can only be observed by agent i *** each time step,each agent independently and randomly chooses either taking an average among its neighbor set,or projecting onto the optimal solution set of its own optimization *** directed and bidirectional communication graphs are *** conditions are proposed to guarantee an optimal consensus almost surely with proper convexity and intersection *** convergence analysis is carried out using convex *** results illustrate that a group of autonomous agents can reach an optimal opinion with probability one by each node simply making a randomized trade-off between following its neighbors or sticking to its own opinion at each time step.

关键词： Multi-agent systems Optimal consensus Set convergence Distributed optimization randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimal Column-Based Low-Rank Matrix Reconstruction 12

Optimal Column-Based Low-Rank Matrix Reconstruction

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Venkatesan Guruswami Ali Kemal Sinop Computer Science Department Carnegie Mellon University

ISBN: (纸本)9781611972108

We prove that for any real-valued matrix X ∈ R~(m×n), and positive integers r ≥ k, there is a subset of r columns of X such that projecting X onto their span gives a {the square rot of}((r＋1)/(r-k＋1)) approximation to best rank-k approximation of X in Frobenius norm. We show that the trade-off we achieve between the number of columns and the approximation ratio is optimal up to lower order terms. Furthermore, there is a deterministic algorithm to find such a subset of columns that runs in O(rnm~ω logm) arithmetic operations where ω is the exponent of matrix multiplication. We also give a faster randomized algorithm that runs in O(rnm~2) arithmetic operations.

关键词： Matrix multiplication FOOT SUPPORT Subset deterministic algorithms Euclidean matrix norm Exponent arithmetic Optimal matrices mechanical heart valve approximation randomized algorithms Surgery

来源：评论

学校读者我要写书评

暂无评论

randomized Algorithm to Determine the Eigenvector of a Stochastic Matrix with Application to the PageRank Problem

引用

AUTOMATION AND REMOTE CONTROL 2011年第2期72卷 342-352页

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

Consideration was given to estimation of the eigenvector corresponding to the greatest eigenvalue of a stochastic matrix. There exist numerous applications of this problem arising at ranking the results of search, coordination of the multiagent system actions, network control, and data analysis. The standard technique for its solution comes to the power method with an additional regularization of the original matrix. A new randomized algorithm was proposed, and a uniform-over the entire class of the stochastic matrices of a given size-upper boundary of the convergence rate was validated. It is given by C root ln(N)/n, where C is an absolute constant, N is size, and n is the number of iterations. This boundary seems promising because ln(N) is smallish even for a very great size. The algorithm relies on the mirror descent method for the problems of convex stochastic optimization. Applicability of the method to the PageRank problem of ranking the Internet pages was discussed.

关键词： randomized algorithms Eigenvector Stochastic one-piece run

来源：评论

学校读者我要写书评

暂无评论

Fast distributed smoothing of relative measurements

Fast distributed smoothing of relative measurements

引用

IEEE Annual Conference on Decision and Control

作者： Nikolaos M. Freris Anastasios Zouzias School of Computer and Communication Sciences Ecole Polytechnique Federale de Lausanne Department of Computer Science at the University of Toronto

ISBN: (纸本)9781467320658

We consider the problem of estimation from noisy relative measurements in a network. In previous work, a distributed scheme for obtaining least-squares (LS) estimates was developed based on the Jacobi algorithm;in a synchronous version, the algorithm was shown to converge exponentially and bounds on the rate of convergence have been obtained. In this paper, we design and analyze a new class of distributed asynchronous smoothing algorithms based on a randomized version of Kaczmarz algorithm for solving linear systems. One of the proposed schemes applies randomized Kaczmarz directly to the noisy linear system, whereas the other one operates on the normal equations for LS estimation. We analyze the expected convergence rate of the proposed algorithms depending solely on properties of the network topology. Inspired by the analytical insights, we propose a distributed smoothing algorithm, namely randomized Kaczmarz Over-smoothing (RKO), which has demonstrated significant improvement over existing protocols in terms of both convergence speedup and energy savings.

关键词： Smoothing Distributed algorithms Clock synchronization randomized algorithms Least Squares Estimation Wireless Networks Sensor networks smoothing clock recovery randomized algorithms distributed algorithms relative measurement Network topology Sensor networks Wireless networks Converge Fasting Distribute

来源：评论

学校读者我要写书评

暂无评论

Fast Algorithm for Finding True Number of Clusters. Applications to Control Systems

Fast Algorithm for Finding True Number of Clusters. Applicat...

引用

The 24th Chinese Control and Decision Conference (第24届中国控制与决策学术年会 2012 CCDC)

作者： Mikhail Morozkov Oleg Granichin Zeev Volkovich Xuming Zhang Department of Mathematicsand Mechanics Saint Petersburg State University 198504 Universitetskiipr Software Engineering Department ORT Braude College of Engineering Karmiel 21982 Israel Department of Biomedical Engineering School of Life Science and Technology Huazhong University of

One of the most *** problems in cluster analysis is the *** of the number of groups in a given data set. In this paper we offer the randomized approach in the rate distortion framework. A randomized algorithm has been suggested to allocate this position. The scenario approach is used to *** reduce the computational complexity. With ability to determine the true number of clusters and perform clustering in real-time operational mode we outline several applications in control systems and decision-making problems that can bene.t from algorithm in question essentially. We also provide simulation results to show considerable speed optimization with guaranteed level of probability.

关键词： Clustering randomized algorithms Adaptive Control Optimitzaion

来源：评论

学校读者我要写书评

暂无评论

On the quantum and randomized approximation of linear functionals on function spaces

引用

QUANTUM INFORMATION PROCESSING 2011年第3期10卷 279-296页

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

We deal with quantum and randomized algorithms for approximating a class of linear continuous functionals. The functionals are defined on a Holder space of functions f of d variables with r continuous partial derivatives, the rth derivative being a Holder function with exponent rho. For a certain class of such linear problems (which includes the integration problem), we define algorithms based on partitioning the domain of f into a large number of small subdomains, and making use of the well-known quantum or randomized algorithms for summation of real numbers. For N information evaluations (quantum queries in the quantum setting), we show upper bounds on the error of order N (-(gamma+1)) in the quantum setting, and N (-(gamma+1/2)) in the randomized setting, where gamma = (r + rho)/d is the regularity parameter. Hence, we obtain for a wider class of linear problems the same upper bounds as those known for the integration problem. We give examples of functionals satisfying the assumptions, among which we discuss functionals defined on the solution of Fredholm integral equations of the second kind, with complete information about the kernel. We also provide lower bounds, showing in some cases sharpness of the obtained results, and compare the power of quantum, randomized and deterministic algorithms for the exemplary problems.

关键词： Linear functionals Approximation Quantum algorithms randomized algorithms Upper and lower bounds

来源：评论

学校读者我要写书评

暂无评论

Fast Algorithm for Finding True Number of Clusters. Applications to Control Systems

Fast Algorithm for Finding True Number of Clusters. Applicat...

引用

第24届中国控制与决策会议

作者： Mikhail Morozkov Oleg Granichin Zeev Volkovich Department of Mathematics and Mechanics Saint Petersburg State University

One of the most difficult problems in cluster analysis is the identification of the number of groups in a given data set. In this paper we offer the randomized approach in the rate distortion framework. A randomized algorithm has been suggested to allocate this position. The scenario approach is used to significantly reduce the computational complexity. With ability to determine the true number of clusters and perform clustering in real-time operational mode we outline several applications in control systems and decision-making problems that can benefit from algorithm in question essentially. We also provide simulation results to show considerable speed optimization with guaranteed level of probability.

关键词： Clustering randomized algorithms Adaptive Control Optimitzaion

来源：评论

学校读者我要写书评

暂无评论

A Cognitive-inspired Model for Self-organizing Networks

A Cognitive-inspired Model for Self-organizing Networks

引用

IEEE International Conference on Self-Adaptive and Self-Organizing Systems Workshops

作者： Daniel Borkmann Andrea Guazzini Emanuele Massaro Stefan Rudolph Communication Systems Group ETH Zurich Switzerland Institute for Informatics and Telematics National Research Council Pisa Italy Department of Informatics and Systems University of Florence Italy Organic Computing Group University of Augsburg Germany

ISBN: (纸本)9781467351539

In this work we propose a computational scheme inspired by the workings of human cognition. We embed some fundamental aspects of the human cognitive system into this scheme in order to obtain a minimization of computational resources and the evolution of a dynamic knowledge network over time, and apply it to computer networks. Such algorithm is capable of generating suitable strategies to explore huge graphs like the Internet that are too large and too dynamic to be ever perfectly known. The developed algorithm equips each node with a local information about possible hubs which are present in its environment. Such information can be used by a node to change its connections whenever its fitness is not satisfying some given requirements. Eventually, we compare our algorithm with a randomized approach within an ecological scenario for the ICT domain, where a network of nodes carries a certain set of objects, and each node retrieves a subset at a certain time, constrained with limited resources in terms of energy and bandwidth. We show that a cognitive-inspired approach improves the overall networks topology better than a randomized algorithm.

关键词： complex networks cognitive modelling selfawareness systems complex networks Line of nodes Cognitive Maps Self-organizing networks randomized algorithms computational scheme computer network local information. Network

来源：评论

学校读者我要写书评

暂无评论

A random coordinate descent method for large-scale resource allocation problems

A random coordinate descent method for large-scale resource ...

引用

IEEE Annual Conference on Decision and Control

作者： I. Necoara University Politehnica Bucharest Automatic Control and Systems Engineering Department

ISBN: (纸本)9781467320658

In this paper we develop a randomized (block) coordinate descent method for solving singly linear equality constrained optimization problems that appear for example in resource allocation over networks. We show that for strongly convex objective functions the new algorithm has an expected linear convergence rate that depends on the second smallest eigenvalue λ_2(Q) of a matrix Q that is defined in terms of the probabilities and the number of blocks. However, the computational complexity per iteration of our method is much simpler than of a method based on full gradient information. We also focus on how to choose the probabilities to make this randomized algorithm to converge as fast as possible and we arrive at solving a sparse SDP. Finally, we present some numerical results for our method that show its efficiency on huge sparse problems.

关键词： descent method Resource utilization management of resources randomized algorithms Coordinates iterative methods Converge

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：