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

Pass-efficient truncated UTV for low-rank approximations

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

作者： Ji, Ying Feng, Yuehua Dong, Yongxin Shanghai Univ Engn Sci Sch Math Phys & Stat Shanghai 201620 Peoples R China East China Univ Polit Sci & Law Sch Law & Criminal Justice Shanghai 201620 Peoples R China

We propose the pass-efficient truncated UTV algorithm, a faster variant of the TUXV algorithm for low-rank approximations. Compared with the TUXV algorithm, data transfer and the complexity of the proposed algorithm are reduced. Therefore, our algorithm is suitable for large matrices stored out of memory or generated by streaming data. We also develop residual error upper bounds and singular value approximation error bounds for the pass-efficient truncated UTV algorithm. Numerical experiments are reported to demonstrate the efficiency and effectiveness of our algorithm.

关键词： SVD randomized algorithm Low-rank approximation UTV factorization Pass-efficient

来源：评论

学校读者我要写书评

暂无评论

UTV decomposition of dual matrices and its applications

引用

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

作者： Xu, Renjie Wei, Tong Wei, Yimin Yan, Hong Fudan Univ Sch Math Sci Shanghai 200433 Peoples R China Fudan Univ Inst Sci & Technol Brain Inspired Intelligence Shanghai 200433 Peoples R China Fudan Univ Sch Math Sci Shanghai Key Lab Contemporary Appl Math Shanghai 200433 Peoples R China City Univ Hong Kong Ctr Intelligent Multidimens Data Anal Dept Elect Engn Hong Kong Peoples R China

Matrix factorization in the context of dual numbers has found applications, in recent years, in fields such as kinematics and computer graphics. In this paper, we develop an efficient approach for handling large-scale data low-rank approximation problems using the UTV decomposition of dual matrices (DUTV). Theoretically, we propose an explicit expression for the DUTV and provide necessary and sufficient conditions for its existence. During this process, we also discovered that the general low-rank model for dual matrices can be solved by the Sylvester equation. In numerical experiments, the DUTV algorithm outperforms the dual matrix SVD algorithm in terms of speed and maintains effective performance in wave recognition. Subsequently, we utilize the DUTV algorithm to validate brain functional circuits in large-scale task-state functional magnetic resonance imaging data. Successfully identifying three types of wave signals, the DUTV method provides substantial empirical evidence for cognitive neuroscience theories.

关键词： Dual matrices UTV decomposition Low-rank approximation randomized algorithm Traveling wave identification Brain dynamics

来源：评论

学校读者我要写书评

暂无评论

Tracking tensor ring decompositions of streaming tensors

引用

COMPUTATIONAL & APPLIED MATHEMATICS 2025年第1期44卷 1-30页

作者： Yu, Yajie Li, Hanyu Chongqing Univ Coll Math & Stat Chongqing 401331 Peoples R China Chongqing Univ Key Lab Nonlinear Anal & its Applicat Minist Educ Chongqing Peoples R China

Tensor ring (TR) decomposition is an efficient approach to discover the hidden low-rank patterns in higher-order tensors, and streaming tensors are becoming highly prevalent in real-world applications. In this paper, we investigate how to track TR decompositions of streaming tensors. An efficient algorithm is first proposed. Then, based on this algorithm and randomized sketching techniques, we present a randomized streaming TR decomposition. The proposed algorithms make full use of the structure of TR decomposition, and the randomized version can allow any sketching type. Theoretical results on sketch size are provided. In addition, the complexity analyses for the obtained algorithms are also given. We compare our proposals with the existing batch methods using both real and synthetic data. Numerical results show that they have better performance in computing time with maintaining similar accuracy.

关键词： Tensor ring decomposition Streaming tensor randomized algorithm Alternating least squares Kronecker sub-sampled randomized Fourier transform Uniform sampling Importance sampling Leverage score

来源：评论

学校读者我要写书评

暂无评论

An L-DEIM induced high order tensor interpolatory decomposition

引用

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 2025年 453卷

作者： Cao, Zhengbang 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

This paper derives the CUR-type factorization for tensors in the Tucker format based on a new variant of the discrete empirical interpolation method known as L-DEIM. This novel sampling technique allows us to construct an efficient algorithm for computing the structure-preserving decomposition, which significantly reduces the computational cost. For large-scale datasets, we incorporate the random sampling technique with the L-DEIM procedure to further improve efficiency. Moreover, we propose randomized algorithms for computing a hybrid decomposition, which yield interpretable factorization and provide a smaller approximation error than the tensor CUR factorization. We provide comprehensive analysis of probabilistic errors associated with our proposed algorithms, and present numerical results that demonstrate the effectiveness of our methods.

关键词： CUR decomposition L-DEIM Low-rank approximation Tucker decomposition randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

SVD-based algorithms for fully-connected tensor network decomposition

引用

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

作者： Wang, Mengyu Li, Hanyu Chongqing Univ Coll Math & Stat Chongqing Peoples R China Chongqing Univ Key Lab Nonlinear Anal & its Applicat Minist Educ Beijing Peoples R China

The popular fully-connected tensor network (FCTN) decomposition has achieved successful applications in many fields. A standard method to this decomposition is the alternating least squares. However, it often converges slowly and suffers from issues of numerical stability. In this work, we investigate the SVD-based algorithms for FCTN decomposition to tackle the aforementioned deficiencies. On the basis of a result about FCTN-ranks, a deterministic algorithm, namely FCTN-SVD, is first proposed, which can approximate the FCTN decomposition under a fixed accuracy. Then, we present the randomized version of the algorithm. Both synthetic and real data are used to test our algorithms. Numerical results show that they perform much better than the existing methods, and the randomized algorithm can indeed yield acceleration on FCTN-SVD. Moreover, we also apply our algorithms to tensor-on-vector regression and achieve quite decent performance.

关键词： Fully-connected tensor network decomposition SVD randomized algorithm Alternating least squares Sketching

来源：评论

学校读者我要写书评

暂无评论

Scheduling periodic messages on a shared link without buffering

引用

JOURNAL OF SCHEDULING 2024年第5期27卷 461-484页

作者： Guiraud, Mael Strozecki, Yann CESI Nanterre LINEACT BP 60293 Blvd Seine F-92006 Nanterre France Univ Versailles St Quentin DAVID Lab 45 Ave Etats Unis F-78000 Versailles France

Cloud RAN, a novel architecture for modern mobile networks, relocates processing units from antenna to distant data centers. This shift introduces the challenge of ensuring low latency for the periodic messages exchanged between antennas and their respective processing units. In this study, we tackle the problem of devising an efficient periodic message assignment scheme under the constraints of fixed message size and period without contention nor buffering. We address this problem by modeling it on a common network topology, wherein contention arises from a single shared link servicing multiple antennas. While reminiscent of coupled task scheduling, the introduction of periodicity adds a unique dimension to the problem. We study how the problem behaves with regard to the load of the shared link, and we focus on proving that, for load as high as possible, a solution always exists and it can be found in polynomial time. The main contributions of this article are two polynomial time algorithms, which find a solution for messages of any size and load at most 2/5 or for messages of size one and load at most phi-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi - 1$$\end{document}, the golden ratio conjugate. We also prove that a randomized greedy algorithm finds a solution on almost all instances with high probability, shedding light on the effectiveness of greedy algorithms in practical applications.

关键词： Periodic scheduling Greedy algorithm randomized algorithm Experimental algorithms C-RAN

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：