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

Finding local optima in quadratic optimization problems in RP

SOFT COMPUTING 2024年第1期28卷 495-508页

作者： Gao, Lunshan Wilfrid Laurier Univ Dept Phys & Comp Sci 75 Univ Ave W Waterloo ON N2L3C5 Canada

This paper describes a new randomized algorithm for calculating local optima in standard quadratic optimization problems (StQPs) over the standard simplex. The new algorithm transforms StQPs into a new form by using a fuzzification technique. This paper proves that: (1) the computational complexity of the new algorithm for computing local optima in StQPs is in the class of randomized polynomial time;(2) the solution of the new algorithm satisfies ? - d condition. Examples are given that demonstrate that the new algorithm outperforms IBM ILOG CPLEX (CPLEX). Numerical experiments indicate that for calculating the first local optima of StQPs, the average computational time of the new algorithm is one hundred time faster than that of CPLEX when the number of variables is 1000.

关键词： Standard quadratic optimization problem randomized algorithm randomized polynomial time Fuzzification Possibility distribution function Normalized possibility distribution function

来源：评论

学校读者我要写书评

暂无评论

Distributed Primal-Dual Proximal algorithms for Convex Optimization Involving Three Composite Functions

引用

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS 2024年第1期11卷 389-401页

作者： Ran, Liang Li, Huaqing Hu, Jinhui Lu, Qingguo Wang, Zheng Li, Zhe Chen, Guo Southwest Univ Coll Elect & Informat Engn Chongqing Key Lab Nonlinear Circuits & Intelligent Chongqing 400715 Peoples R China Cent South Univ Dept Automat Changsha 410083 Peoples R China Chongqing Univ Coll Comp Sci Chongqing 400044 Peoples R China Univ New South Wales Sch Elect Engn & Telecommun Sydney NSW 2052 Australia

This article develops a novel distributed primal-dua l proximal algorithm (PDPA-Dist) and its corresponding randomized version (Rand-PDPA-Dist) for solving convex optimization problems. The local objective consists of a smooth function and two possibly nonsmooth ones, with one involving a linear mapping. At each iteration, PDPA-Dist allows each agent to perform local computations by communicating with its neighbors, while Rand-PDPA-Dist is executed with a randomly and independently activated subset of agents. The proposed algorithms recover new distributed extensions of known centralized algorithms and existing distributed schemes, depending on certain special setups. Both PDPA-Dist and Rand-PDPA-Dist achieve exact linear convergence rates provided that local objective functions satisfy piecewise linear-quadratic or certain quadratic growth conditions. Finally, the performance and effectiveness of the proposed algorithms are demonstrated by resolving a distributed model predictive control (DMPC) problem.

关键词： Composite functions distributed convex optimization linear convergence primal-dual proximal algorithms randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

A random sampling algorithm for fully-connected tensor network decomposition with applications

引用

COMPUTATIONAL & APPLIED MATHEMATICS 2024年第4期43卷 1-22页

作者： Wang, Mengyu Cui, Honghua Li, Hanyu Chongqing Univ Coll Math & Stat Chongqing 401331 Peoples R China Xiamen Univ Wang Yanan Inst Studies Econ Fujian 361005 Peoples R China

Fully-connected tensor network (FCTN) decomposition is a generalization of the popular tensor train and tensor ring decompositions and has been applied to various fields with great success. The standard method for computing this decomposition is the well-known alternating least squares (ALS). However, it is very expensive, especially for large-scale tensors. To reduce the cost, we propose an ALS-based randomized algorithm. Specifically, by defining a new tensor product called subnetwork product and adjusting the sizes of FCTN factors suitably, the structure of the coefficient matrices of the ALS subproblems from FCTN decomposition is first figured out. Then, with the structure and the properties of subnetwork product, we devise the randomized algorithm based on leverage sampling. This algorithm enables sampling on FCTN factors and hence avoids the formation of full coefficient matrices of ALS subproblems. The computational complexity and numerical performance of our algorithm are presented. Experimental results show that it requires much less computation time to achieve similar accuracy compared with the deterministic ALS method. Further, we apply our algorithm to four famous problems, i.e., tensor-on-vector regression, multi-view subspace clustering, nonnegative tensor approximation and tensor completion, and the performances are quite decent.

关键词： Fully-connected tensor network decomposition Alternating least squares randomized algorithm Leverage sampling Tensor-on-vector regression Multi-view subspace clustering Nonnegative tensor approximation Tensor completion

来源：评论

学校读者我要写书评

暂无评论

Double-Tucker Decomposition and Its Computations

引用

NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS 2025年第1期32卷

作者： Wang, Mengyu Cui, Honghua Li, Hanyu Xiamen Univ Wang Yanan Inst Studies Econ Xiamen Fujian Peoples R China Chongqing Univ Coll Math & Stat Chongqing Peoples R China

The famous Tucker decomposition has been widely and successfully used in many fields. However, it often suffers from the curse of dimensionality due to the core tensor and large ranks. To tackle this issue, we introduce an additional core tensor into Tucker decomposition and propose the so-called double-Tucker (dTucker) decomposition. The additional core can share the ranks of the original Tucker decomposition and hence make the parameters of the new decomposition be reduced greatly. We employ the alternating least squares (ALS) method with explicit structures on coefficient matrices of the ALS subproblems to compute the dTucker decomposition. To figure out the structures, a new tensor product is defined. Its properties and the aforementioned structures together motivate an ALS-based randomized algorithm built on Kronecker sub-sampled randomized Fourier transform for our new decomposition. A special case of the algorithm leads to a more efficient leverage-based random sampling algorithm. These randomized algorithms can avoid forming the full coefficient matrices of ALS subproblems by implementing projecting and sampling on factor tensors. Numerical experiments including tensor reconstruction and multi-view subspace clustering are presented to test our decomposition and algorithms, which show that dTucker decomposition can effectively decrease the ranks of the classical one and hence the total parameters, and the randomized algorithms reduce running time greatly while maintaining similar accuracy. Moreover, the numerical results also show that our decomposition can even outperform the popular tensor train decomposition and the newly developed tensor wheel decomposition on compressing parameters.

关键词： alternating least squares double-Tucker decomposition Kronecker sub-sampled randomized Fourier transform leverage sampling multi-view subspace clustering randomized algorithm tensor reconstruction Tucker decomposition

来源：评论

学校读者我要写书评

暂无评论

XTRACE: MAKING THE MOST OF EVERY SAMPLE IN STOCHASTIC TRACE ESTIMATION

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2024年第1期45卷 1-23页

作者： Epperly, Ethan N. Tropp, Joel A. Webber, Robert J. CALTECH Div Comp & Math Sci Pasadena CA 91125 USA

The implicit trace estimation problem asks for an approximation of the trace of a square matrix, accessed via matrix-vector products (matvecs). This paper designs new randomized algorithms, XTRACE and XNYsTRACE, for the trace estimation problem by exploiting both variance reduction and the exchangeability principle. For a fixed budget of matvecs, numerical experiments show that the new methods can achieve errors that are orders of magnitude smaller than existing algorithms, such as the Girard-Hutchinson estimator or the Hutch++ estimator. A theoretical analysis confirms the benefits by offering a precise description of the performance of these algorithms as a function of the spectrum of the input matrix. The paper also develops an exchangeable estimator, XDiag, for approximating the diagonal of a square matrix using matvecs.

关键词： trace estimation low-rank approximation exchangeability variance reduction randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

A Simple Predicate to Expedite the Termination of a randomized Consensus algorithm 29

A Simple Predicate to Expedite the Termination of a Randomiz...

引用

IEEE 29th International Conference on Advanced Information Networking and Applications (IEEE AINA)

作者： Raynal, Michel Univ Rennes 1 Inst Univ France Campus Beaulieu F-35042 Rennes France Univ Rennes 1 IRISA F-35042 Rennes France

ISBN: (纸本)9781479979042

Consensus is one of the most important problems encountered in fault-tolerant distributed computing. Basically, consensus allows processes to agree on a common value. Unfortunately, no deterministic algorithm can solve this problem in an asynchronous message-passing system prone to process crash failures. One way to circumvent this impossibility, consists in enriching the system with random numbers and design a randomized algorithm. This paper considers such a consensus algorithm and presents a simple predicate that allows to expedite its termination.

关键词： Asynchronous distributed system Consensus Message-passing randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Single-pass randomized QLP decomposition for low-rank approximation

引用

CALCOLO 2022年第4期59卷 49-49页

作者： Ren, Huan Xiao, Guiyun Bai, Zheng-Jian Xiamen Univ Sch Math Sci Xiamen 360015 Peoples R China

As a special UTV decomposition, the QLP decomposition is an effective alternative of the singular value decomposition (SVD) for the low-rank approximation. In this paper, we propose a single-pass randomized QLP decomposition algorithm for computing a low-rank matrix approximation. Compared with the randomized QLP decomposition, the complexity of the proposed algorithm does not increase significantly and the data matrix needs to be accessed only once. Therefore, our algorithm is suitable for a large matrix stored outside of memory or generated by streaming data. In the error analysis, we give the matrix approximation error analysis. We also provide singular value approximation error bounds, which can track the target largest singular values of the data matrix with high probability. Numerical experiments are also reported to verify our results.

关键词： QLP decomposition randomized algorithm Single-pass Singular value Low-rank approximation

来源：评论

学校读者我要写书评

暂无评论

The equilibria of independent distributions on unbalanced game trees

引用

COMPUTATIONAL & APPLIED MATHEMATICS 2024年第5期43卷 1-16页

作者： Tanaka, Kazuyuki Peng, Ning Ning Peng, Weiguang Li, Wenjuan Beijing Inst Math Sci & Applicat Beijing Peoples R China Wuhan Univ Technol Dept Math Wuhan Peoples R China Southwest Univ Sch Math & Stat Chongqing Peoples R China Tohoku Univ Math Inst Sendai Japan

The work reported here is our first attempt to investigate the equilibria of independent distributions (ID) on unbalanced game trees, after a long series of studies on balanced AND-OR trees, e.g., Liu and Tanaka (Inform Process Lett 104(2):73-77, 2007;Liu and Tanaka (The computational complexity of game trees by eigen-distribution. In: Proceeding 436 of the 1st International Conference on COCOA, pp. 323-334, 2007;Suzuki and Niida (Ann Pure Appl Log 166(11):1150-1164, 2015;Peng et al. (Inform Process Lett 125:41-45, 2017;Suzuki (Ann Jpn Assoc Philos Sci 25:79-88, 2017;Inform Process Lett 139:13-17, 2018);Peng et al. (Methodol Comput Appl Probab 24:277-287, 2022). To handle an unbalanced tree, we decompose the tree into subtrees with different weights (= costs). The present research not only generalizes our previous results on balanced trees to unbalanced weighted trees, but also gives simpler inductive proofs and new perspectives for some old results. Our primary objective is to characterize the "eigen-distribution" d is an element of\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d \in $$\end{document} ID(r) for a weighted game tree (with a fixed probability for the root having value 0 as 0

关键词： Alpha-beta pruning algorithm randomized algorithm Game trees Eigen-distributions

来源：评论

学校读者我要写书评

暂无评论

A Fast algorithm for Rank-(L, M, N) Block Term Decomposition of Multi-Dimensional Data

引用

JOURNAL OF SCIENTIFIC COMPUTING 2024年第1期101卷 16页

作者： Zhang, Hao Huang, Ting-Zhu Zhao, Xi-Le Che, Maolin Univ Elect Sci & Technol China Res Ctr Image & Vis Comp Sch Math Sci Chengdu 611731 Sichuan Peoples R China Southwestern Univ Finance & Econ Sch Econ Math Chengdu 611130 Sichuan Peoples R China

Attribute to its powerful representation ability, block term decomposition (BTD) has recently attracted many views of multi-dimensional data processing, e.g., hyperspectral image unmixing and blind source separation. However, the popular alternating least squares algorithm for rank-(L, M, N) BTD (BTD-ALS) suffers expensive time and space costs from Kronecker products and solving low-rank approximation subproblems, hindering the deployment of BTD for real applications, especially for large-scale data. In this paper, we propose a fast sketching-based Kronecker product-free algorithm for rank-(L, M, N) BTD (termed as KPF-BTD), which is suitable for real-world multi-dimensional data. Specifically, we first decompose the original optimization problem into several rank-(L, M, N) approximation subproblems, and then we design the bilateral sketching to obtain the approximate solutions of these subproblems instead of the exact solutions, which allows us to avoid Kronecker products and rapidly solve rank-(L, M, N) approximation subproblems. As compared with BTD-ALS, the time and space complexities O(2(p+1)((ILR)-L-3+(ILR)-L-2-R-2+(ILR)-R-3)+(ILR)-L-3) and O(I-3) of KPF-BTD are significantly cheaper than O((ILR2)-L-3-R-6+(ILR)-L-3-R-3+(ILR)-L-3+(ILR2)-L-2-R-3+(ILR)-L-2-R-2) and O((ILR)-L-3-R-3) of BTD-ALS, where p << I. Moreover, we establish the theoretical error bound for KPF-BTD. Extensive synthetic and real experiments show KPF-BTD achieves substantial speedup and memory saving while maintaining accuracy (e.g., for a 150x150x150 synthetic tensor, the running time 0.2 seconds per iteration of KPF-BTD is significantly faster than 96.2 seconds per iteration of BTD-ALS while their accuracies are comparable).

关键词： Block term decomposition randomized algorithm Tensor sketching Multi-dimensional data processing

来源：评论

学校读者我要写书评

暂无评论

A Missing Data Reconstruction Method Using an Accelerated Least-Squares Approximation with randomized SVD

引用

algorithmS 2022年第6期15卷 190-190页

作者： Intawichai, Siriwan Chaturantabut, Saifon Thammasat Univ Fac Sci & Technol Dept Math & Stat Pathum Thani 12120 Thailand

An accelerated least-squares approach is introduced in this work by incorporating a greedy point selection method with randomized singular value decomposition (rSVD) to reduce the computational complexity of missing data reconstruction. The rSVD is used to speed up the computation of a low-dimensional basis that is required for the least-squares projection by employing randomness to generate a small matrix instead of a large matrix from high-dimensional data. A greedy point selection algorithm, based on the discrete empirical interpolation method, is then used to speed up the reconstruction process in the least-squares approximation. The accuracy and computational time reduction of the proposed method are demonstrated through three numerical experiments. The first two experiments consider standard testing images with missing pixels uniformly distributed on them, and the last numerical experiment considers a sequence of many incomplete two-dimensional miscible flow images. The proposed method is shown to accelerate the reconstruction process while maintaining roughly the same order of accuracy when compared to the standard least-squares approach.

关键词： singular value decomposition missing data approximation low-rank approximation least-squares method randomized algorithm discrete empirical interpolation method

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：