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

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

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

作者： 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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

randomized k-set agreement in crash-prone and Byzantine asynchronous systems

引用

THEORETICAL COMPUTER SCIENCE 2018年 709卷 80-97页

作者： Mostefaoui, Achour Moumen, Hamouma Raynal, Michel Univ Nantes LINA F-44322 Nantes France Univ Batna Batna Algeria Inst Univ France Paris France Univ Rennes IRISA F-35042 Rennes France

k-Set agreement is a central problem of fault-tolerant distributed computing. Considering a set of n processes, where up to t may commit failures, let us assume that each process proposes a value. The problem consists in defining an algorithm such that each non-faulty process decides a value, at most k different values are decided, and the decided values satisfy some context-depending validity condition. algorithms solving k-set agreement in synchronous message-passing systems have been proposed for different failure models (mainly process crashes, and process Byzantine failures). Differently, k-set agreement cannot be solved in failure-prone asynchronous message-passing systems when t > k. To circumvent this impossibility an asynchronous system must be enriched with additional computational power. Assuming t > k, this paper presents two distributed algorithms that solve k-set agreement in asynchronous message-passing systems where up to t processes may commit crash failures (first algorithm) or more severe Byzantine failures (second algorithm). To circumvent k-set agreement impossibility, this article considers that the underlying system is enriched with the computability power provided by randomization. Interestingly, the algorithm that copes with Byzantine failures is signature-free, and ensures that no value proposed only by Byzantine processes can be decided by a non-faulty process. Both algorithms share basic design principles. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Asynchronous system Broadcast abstraction Byzantine process Coin Crash failure Distributed algorithm k-Set agreement Message-passing system randomized algorithm Signature-free algorithm

来源：评论

学校读者我要写书评

暂无评论

randomized approximation of Sobolev embeddings, II

引用

JOURNAL OF COMPLEXITY 2009年第5期25卷 455-472页

作者： Heinrich, Stefan Univ Kaiserslautern Fachbereich Informat D-67653 Kaiserslautern Germany

We Study the approximation of Sobolev embeddings by linear randomized algorithms based on function values. Both the source and the target space are Sobolev spaces of non-negative smoothness order, defined on a bounded Lipschitz domain. The optimal order of convergence is determined. We also study the deterministic setting. Using interpolation, we extend the results to other classes of function spaces. In this context a problem posed by Novak and Wozniakowski is solved. Finally, we present an application to the complexity of general elliptic PDE. (C) 2009 Elsevier Inc. All rights reserved.

关键词： Approximation randomized algorithm Sobolev space Sampling Lower bounds

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Fast randomized numerical rank estimation for numerically low-rank matrices

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2024年 686卷 1-32页

作者： Meier, Maike Nakatsukasa, Yuji Univ Oxford Math Inst Oxford OX2 6GG England

Matrices with low -rank structure are ubiquitous in scientific computing. Choosing an appropriate rank is a key step in many computational algorithms that exploit low -rank structure. However, estimating the rank has been done largely in an ad -hoc fashion in large-scale settings. In this work we develop a randomized algorithm for estimating the numerical rank of a (numerically low -rank) matrix. The algorithm is based on sketching the matrix with random matrices from both left and right;the key fact is that with high probability, the sketches preserve the orders of magnitude of the leading singular values. We prove a result on the accuracy of the sketched singular values and show that gaps in the spectrum are detected. For an m x n (m >= n) matrix of numerical rank r, the algorithm runs with complexity O(mnlog n + r3), or less for structured matrices. The steps in the algorithm are required as a part of many low -rank algorithms, so the additional work required to estimate the rank can be even smaller in practice. Numerical experiments illustrate the speed and robustness of our rank estimator. (c) 2024 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http:// creativecommons .org /licenses /by /4 .0/).

关键词： Rank estimation Numerical rank randomized algorithm Mar & ccaron enko-Pastur rule

来源：评论

学校读者我要写书评

暂无评论

Efficient symmetry-based screening strategy to speed up randomized circle-detection

引用

PATTERN RECOGNITION LETTERS 2012年第16期33卷 2071-2076页

作者： Huang, Yong-Huai Chung, Kuo-Liang Yang, Wei-Ning Chiu, Shih-Hsuan Natl Taiwan Univ Sci & Technol Dept Informat Management Taipei 10672 Taiwan Jinwen Univ Sci & Technol Inst Comp & Commun Engn New Taipei City 23154 Taiwan Jinwen Univ Sci & Technol Dept Elect Engn New Taipei City 23154 Taiwan Natl Taiwan Univ Sci & Technol Dept Comp Sci & Informat Engn Taipei 10672 Taiwan Natl Taiwan Univ Sci & Technol Dept Mat Sci & Engn Taipei 10672 Taiwan

randomized approaches for circle detections are often used for the advantages of less computational time and memory requirements. However, randomized approaches involve examining a large number of candidate circles and may not be suitable for real-time applications. In this paper, a screening strategy based on the symmetric property of the circle is adopted to select the promising candidates for further investigation, resulting in substantial reduction in the computational time while maintaining the accuracy. Empirical results show that, under the same accuracy level, the proposed symmetry-based method achieves the improvement ratios of 40%-90% on the execution-time when compared to four state-of-the-art randomized methods. (c) 2012 Elsevier B.V. All rights reserved.

关键词： Circle detection Computation-saving Hough transform randomized algorithm Screening strategy

来源：评论

学校读者我要写书评

暂无评论

On the generally randomized extended Gauss-Seidel method

引用

APPLIED NUMERICAL MATHEMATICS 2022年 172卷 382-392页

作者： Wu, Nianci Xiang, Hua South Cent Univ Nationalities Sch Math & Stat Wuhan 430074 Peoples R China Wuhan Univ Sch Math & Stat Wuhan 430072 Peoples R China Wuhan Univ Hubei Key Lab Computat Sci Wuhan 430072 Peoples R China

The randomized extended Gauss-Seidel method is a popular representative among the iterative algorithm due to its simplicity for solving the inconsistent and consistent systems of linear equations, which builds the connection between the randomized Kaczmarz and Gauss-Seidel methods. In this work we develop a general version of the randomized extended Gauss-Seidel method, as well as some new iterative schemes. We prove that our algorithm can exponentially converge in expectation to the solutions of the consistent or inconsistent linear systems under two different sampling strategies. Numerical examples show that the proposed algorithm is feasible and effective, where the block method performs significantly better than the corresponding original form. (C) 2021 IMACS. Published by Elsevier B.V. All rights reserved.

关键词： randomized algorithm randomized extended Gauss-Seidel method Convergence analysis

来源：评论

学校读者我要写书评

暂无评论

randomized polygon search for planar motion detection

引用

PATTERN RECOGNITION LETTERS 1996年第10期17卷 1109-1115页

作者： Fermin, I Imiya, A Ichikawa, A CHIBA UNIV DEPT INFORMAT & COMP SCI INAGE KU CHIBA JAPAN

In this paper, we propose a randomized algorithm to estimate the motion parameters of a planar shape without knowing a priori the point-to-point correspondences. By randomly searching points on two shapes measured at different times, we determine the centroids, after which the algorithm proceeds to determine the rotation by randomly searching points on each shape that form congruent polygons.

关键词： rigid motion randomized algorithm point correspondences planar shape list matching congruence Hough transform

来源：评论

学校读者我要写书评

暂无评论

Feasibility of Polynomial-Time randomized Gathering for Oblivious Mobile Robots

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2013年第4期24卷 716-723页

作者： Izumi, Taisuke Izumi, Tomoko Kamei, Sayaka Ooshita, Fukuhito Nagoya Inst Technol Grad Sch Engn Showa Ku Nagoya Aichi 4668555 Japan Ritsumeikan Univ Coll Informat Sci & Engn Kusatsu Shiga 5258577 Japan Hiroshima Univ Dept Informat Engn Fac Engn Grad Sch Engn Hiroshima 7398527 Japan Osaka Univ Grad Sch Informat Sci & Technol Suita Osaka 5650871 Japan

We consider the problem of gathering n anonymous and oblivious mobile robots, which requires that all robots meet in finite time at a nonpredefined point. While the gathering problem cannot be solved deterministically without assuming any additional capabilities for the robots, randomized approaches easily allow it to be solvable. However, the randomized solutions currently known have a time complexity that is exponential in n with no additional assumption. This fact yields the following two questions: Is it possible to construct a randomized gathering algorithm with polynomial expected time? If it is not possible, what is the minimal additional assumption necessary to obtain such an algorithm? In this paper, we address these questions from the aspect of multiplicity-detection capabilities. We newly introduce two weaker variants of multiplicity detection, called local-strong and local-weak multiplicity, and investigate whether those capabilities permit a gathering algorithm with polynomial expected time or not. The contribution of this paper is to show that any algorithm only assuming local-weak multiplicity detection takes exponential number of rounds in expectation. On the other hand, we can obtain a constant-round gathering algorithm using local-strong multiplicity detection. These results imply that the two models of multiplicity detection are significantly different in terms of their computational power. Interestingly, these differences disappear if we take one more assumption that all robots are scattered (i.e., no two robots stay at the same location) initially. We can obtain a gathering algorithm that takes a constant number of rounds in expectation, assuming local-weak multiplicity detection and scattered initial configurations.

关键词： Distributed algorithm autonomous mobile robots gathering problem randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：