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

On the randomized multiple row-action methods for solving linear least-squares problems

NUMERICAL algorithmS 2024年 1-28页

作者： Zuo, Qian Wu, Nian-Ci Liu, Chengzhi Wang, Yatian Peking Univ Ctr Frontiers Comp Studies Beijing 100871 Peoples R China Peking Univ Sch Comp Sci Beijing 10087 Peoples R China South Cent Minzu Univ Sch Math & Stat Wuhan 430074 Peoples R China Hunan Univ Humanities Sci & Technol Sch Math & Finance Loudi 417000 Peoples R China Wuhan Univ Sch Math & Stat Wuhan 430072 Peoples R China

The randomized row-action method is a popular representative of the iterative algorithm because of its efficiency in solving the overdetermined and consistent systems of linear equations. In this paper, we present an extended randomized multiple row-action method to solve a given overdetermined and inconsistent linear system and analyze its computational complexities at each iteration. We prove that the proposed method can linearly converge in the mean square to the least-squares solution with a minimum Euclidean norm. Several numerical studies are presented to corroborate our theoretical findings. The real-world applications, such as image reconstruction and large noisy data fitting in computer-aided geometric design, are also presented for illustration purposes.

关键词： randomized algorithm Row-action method Convergence analysis Real-world application

来源：评论

学校读者我要写书评

暂无评论

A randomized Singular Value Decomposition for Third-Order Oriented Tensors

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2023年第1期197卷 358-382页

作者： Ding, Minghui Wei, Yimin Xie, Pengpeng Ocean Univ China Sch Math Sci Qingdao 266100 Peoples R China Fudan Univ Sch Math Sci Shanghai 200433 Peoples R China Fudan Univ Key Lab Math Nonlinear Sci Shanghai 200433 Peoples R China

The oriented singular value decomposition (O-SVD) proposed by Zeng and Ng provides a hybrid approach to the t-product-based third-order tensor singular value decomposition with the transformation matrix being a factor matrix of the higher-order singular value decomposition. Continuing along this vein, this paper explores realizing the O-SVD efficiently by drawing a connection to the tensor-train rank-1 decomposition and gives a truncated O-SVD. Motivated by the success of probabilistic algorithms, we develop a randomized version of the O-SVD and present its detailed error analysis. The new algorithm has advantages in efficiency while keeping good accuracy compared with the current tensor decompositions. Our claims are supported by numerical experiments on several oriented tensors from real applications.

关键词： Oriented tensor Singular value decomposition Truncation randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

randomized algorithms for fast computation of low rank tensor ring model

引用

MACHINE LEARNING-SCIENCE AND TECHNOLOGY 2021年第1期2卷

作者： Ahmadi-Asl, Salman Cichocki, Andrzej Huy Phan, Anh Asante-Mensah, Maame G. Musavian Ghazani, Mirfarid Tanaka, Toshihisa Oseledets, Ivan Skolkovo Inst Sci & Technol SKOLTECH CDISE Moscow Russia Nicolaus Copernicus Univ PL-87100 Torun Poland Tokyo Univ Agr & Technol Tokyo Japan

randomized algorithms are efficient techniques for big data tensor analysis. In this tutorial paper, we review and extend a variety of randomized algorithms for decomposing large-scale data tensors in Tensor Ring (TR) format. We discuss both adaptive and nonadaptive randomized algorithms for this task. Our main focus is on the random projection technique as an efficient randomized framework and how it can be used to decompose large-scale data tensors in the TR format. Simulations are provided to support the presentation and efficiency, and performance of the presented algorithms are compared.

关键词： Tensor Ring-Tensor Train (TR-TT) decompositions randomized algorithm random projection

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithms for Maximization of k-Submodular Function Under a Matroid Constraint

引用

Tsinghua Science and Technology 2024年第6期29卷 1633-1641页

作者： Yuezhu Liu Yunjing Sun Min Li School of Mathematics and Statistics Shandong Normal UniversityJinan 250014China

In this paper,we design a deterministic 1/3-approximation algorithm for the problem of maximizing non-monotone k-submodular function under a matroid *** order to reduce the complexity of this algorithm,we also present a randomized 1/3-approximation algorithm with the probability of 1−ε,whereεis the probability of algorithm ***,we design a streaming algorithm for both monotone and non-monotone objective k-submodular functions.

关键词： k-submodular matroid constraint deterministic algorithm randomized algorithm streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

Solving the system of nonsingular tensor equations via randomized Kaczmarz-like method

引用

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 2023年 421卷

作者： Wang, Xuezhong Che, Maolin Mo, Changxin Wei, Yimin Hexi Univ Sch Math & Stat Zhangye 734000 Peoples R China Southwest Univ Finance & Econ Sch Math Chengdu 611130 Peoples R China Chongqing Normal Univ Sch Math Sci Chongqing 401331 Peoples R China Fudan Univ Sch Math Sci Shanghai 200433 Peoples R China Fudan Univ Key Lab Math Nonlinear Sci Shanghai 200433 Peoples R China

A great deal of attention has been paid to solve the system of tensor equations in recent years for its applications in various fields. In this paper, the Kaczmarz-like method, which is an effective approach for solving linear equations, is considered to deal with the system of tensor equations with nonsingular coefficient tensors. To reach this goal, two algorithms, i.e., the randomized Kaczmarz-like algorithm and its relaxed version, are proposed. The convergence analysis of these two approaches are given based on matrix SVD and the local tangential cone condition. Moreover, we present estimations of the convergence rate. Several numerical examples are presented to validate the theoretical results and reliability as well as effectiveness.(c) 2022 Elsevier B.V. All rights reserved.

关键词： Kaczmarz method randomized algorithm The system of tensor equations Convergence rate Convergence analysis

来源：评论

学校读者我要写书评

暂无评论

The method of randomized Bregman projections for stochastic feasibility problems

引用

NUMERICAL algorithmS 2023年第3期93卷 1269-1307页

作者： Kostic, Vladimir R. Salzo, Saverio Ist Italiano Tecnol Via Melen83 I-16152 Genoa Italy Univ Novi Sad Fac Sci Dept Math & Informat Trg Dositeja Obradovica 4 Novi Sad 21000 Serbia

In this work, we study the method of randomized Bregman projections for stochastic convex feasibility problems, possibly with an infinite number of sets, in Euclidean spaces. Under very general assumptions, we prove almost sure convergence of the iterates to a random almost common point of the sets. We then analyze in depth the case of affine sets showing that the iterates converge Q-linearly and providing also global and local rates of convergence. This work generalizes recent developments in randomized methods for the solution of linear systems based on orthogonal projection methods. We provided several applications: sketch & project methods for solving linear systems of equations, positive definite matrix completion problem, gossip algorithms for networks consensus, the assessment of robust stability of dynamical systems, and computational solutions for multimarginal optimal transport.

关键词： Stochastic convex feasibility problem Bregman projection method Linear convergence randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Single-pass randomized algorithms for LU decomposition

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2020年第0期595卷 101-122页

作者： Li, Hanyu Yin, Shuheng Chongqing Univ Coll Math & Stat Chongqing 401331 Peoples R China

In this paper, we present some single-pass randomized algorithms to compute LU decomposition. These algorithms need only one pass over the original matrix and hence are very suitable for extremely large and high-dimensional matrix stored outside of core memory or generated in a streaming fashion. Rigorous error bounds and complexity of these algorithms are provided. Numerical experiments show that these single-pass algorithms have the similar accuracy and runtime (excluding the cost of matrix transfer) compared with the state-of-the-art randomized algorithms for LU decomposition. (C) 2020 Elsevier Inc. All rights reserved.

关键词： LU decomposition randomized algorithm Single-pass Error bound

来源：评论

学校读者我要写书评

暂无评论

Improved lower bound for estimating the number of defective items

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2025年第2期49卷 1-19页

作者： Bshouty, Nader H. Technion Israel Inst Technol Hefa Israel

Consider a set of items, X, with a total of n items, among which a subset, denoted as I subset of X, consists of defective items. In the context of group testing, a test is conducted on a subset of items Q, where Q subset of X. The result of this test is positive, yielding 1, if Q includes at least one defective item, that is if Q boolean AND I not equal empty set. It is negative, yielding 0, if no defective items are present in Q. We introduce a novel method for deriving lower bounds in the context of non-adaptive randomized group testing. For any given constant j, any non-adaptive randomized algorithm that, with probability at least 2/3, estimates the number of defective items |I| within a constant factor requires at least Omega (log n/ log log center dot center dot center dot(j) log n) tests. Our result almost matches the upper bound of O(log n) and addresses the open problem posed by Damaschke and Sheikh Muhammad in (Combinatorial Optimization and Applications - 4th International Conference, COCOA 2010, pp 117-130, 2010;Discrete Math Alg Appl 2(3):291-312, 2010). Furthermore, it enhances the previously established lower bound of Omega(log n/log log n) by Ron and Tsur (ACM Trans Comput Theory 8(4): 15:1-15:19, 2016), and independently by Bshouty (30th International Symposium on algorithms and Computation, ISAAC 2019, LIPIcs, vol 149, pp 2:1-2:9, 2019). For estimation within a non-constant factor alpha(n), we show: If a constant j exists such that alpha>log log center dot center dot center dot(j) log n, then any non-adaptive randomized algorithm that, with probability at least 2/3, estimates the number of defective items |I| to within a factor alpha requires at least Omega(log n / log alpha). In this case, the lower bound is tight.

关键词： Group testing randomized algorithm Estimation

来源：评论

学校读者我要写书评

暂无评论

randomized Quaternion QLP Decomposition for Low-Rank Approximation

引用

JOURNAL OF SCIENTIFIC COMPUTING 2022年第3期92卷 80-80页

作者： Ren, Huan Ma, Ru-Ru Liu, Qiaohua Bai, Zheng-Jian Xiamen Univ Sch Math Sci Xiamen 360015 Peoples R China Suzhou Univ Sci & Technol Sch Math Sci Suzhou 215009 Peoples R China Shanghai Univ Dept Math Shanghai 200444 Peoples R China Xiamen Univ Fujian Prov Key Lab Math Modeling & High Performa Xiamen 361005 Peoples R China

The low-rank approximation of a quaternion matrix has attracted growing attention in many applications including color image processing and signal processing. In this paper, based on quaternion normal distribution random sampling, we propose a randomized quaternion QLP decomposition algorithm for computing a low-rank approximation to a quaternion data matrix. For the theoretical analysis, we first present convergence results of the quaternion QLP decomposition, which provides slightly tighter upper bounds than the existing ones for the real QLP decomposition. Then, for the randomized quaternion QLP decomposition, the matrix approximation error and the singular value approximation error analyses are also established to show the proposed randomized algorithm can track the singular values of the quaternion data matrix with high probability. Finally, we present some numerical examples to illustrate the effectiveness and reliablity of the proposed algorithm.

关键词： Quaternion data matrix Low-rank approximation Quaternion QLP decomposition randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Streaming Histogram Publication over Weighted Sliding Windows Under Differential Privacy

引用

Tsinghua Science and Technology 2024年第6期29卷 1674-1693页

作者： Xiujun Wang Lei Mo Xiao Zheng Zhe Dang School of Computer Science and Technology Anhui University of TechnologyMa’anshan 243032China Institute for Artificial Intelligence Hefei Comprehensive National Science CenterHefei 230088China Baosight Software(Anhui)Co.Ltd. Ma’anshan 243000China School of Electrical Engineering and Computer Science Washington State UniversityPullman 99164WAUSA

Continuously publishing histograms in data streams is crucial to many real-time applications,as it provides not only critical statistical information,but also reduces privacy leaking *** the importance of elements usually decreases over time in data streams,in this paper we model a data stream by a sequence of weighted sliding windows,and then study how to publish histograms over these windows *** existing literature can hardly solve this problem in a real-time way,because they need to buffer all elements in each sliding window,resulting in high computational overhead and prohibitive storage *** this paper,we overcome this drawback by proposing an online algorithm denoted by Efficient Streaming Histogram Publishing(ESHP)to continuously publish histograms over weighted sliding ***,our method first creates a novel sketching structure,called Approximate-Estimate Sketch(AESketch),to maintain the counting information of each histogram interval at every time instance;then,it creates histograms that satisfy the differential privacy requirement by smartly adding appropriate noise values into the sketching *** experimental results and rigorous theoretical analysis demonstrate that the ESHP method can offer equivalent data utility with significantly lower computational overhead and storage costs when compared to other existing methods.

关键词： differential privacy randomized algorithm streaming data publication weighted sliding window approximate statistics data usability computational complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：