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

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

来源：评论

学校读者我要写书评

暂无评论

Enlarged GKB and RSVD for KP approximations illustrated for mixed precision ℓ1 image restoration

引用

Numerical algorithms 2025年 1-23页

作者： Alsubhi, Abdulmajeed Renaut, Rosemary A. School of Mathematical and Statistical Sciences Arizona State University Tempe 85287 AZ United States Department of Mathematics Faculty of Science Islamic University of Madinah Madinah 42351 Saudi Arabia

The singular value decomposition (SVD) of a reordering of a matrix A can be used to determine an efficient Kronecker product (KP) sum approximation to A. We present the use of an approximate truncated SVD (TSVD) to find the KP approximation, and contrast using a randomized singular value decomposition algorithm (RSVD), a new enlarged Golub Kahan Bidiagonalization algorithm (EGKB) and the exact TSVD. The EGKB algorithm enlarges the Krylov subspace beyond a given rank for the desired approximation. A suitable rank is determined using an automatic stopping test. We also contrast the use of single and double precision arithmetic to find the approximate TSVDs. To illustrate the accuracy and efficiency in terms of memory and computational cost of these approximate KPs, we consider the solution of the total variation regularized image deblurring problem using the split Bregman algorithm implemented in double precision. Together with an efficient implementation for the reordering of A we demonstrate that the approximate KP sum can be obtained using a TSVD, and that the new EGKB algorithm contrasts favorably with the use of the RSVD. These results verify that it is feasible to use single precision when estimating a KP sum from an approximate TSVD. © The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2025.

关键词： Golub Kahan Bidiagonalization Isotropic Kronecker Product randomized algorithm Single and double precision Split Bregman ℓ1 regularization

来源：评论

学校读者我要写书评

暂无评论

A randomized QoS Routing algorithm On Networks with Inaccurate Link-State Information

A Randomized QoS Routing Algorithm On Networks with Inaccura...

引用

2000 International Conference on Communication Technology(WCC2000·ICCT2000)

作者： Wang Jianxin Wang Weiping Chen Jianer Chen Songqiao College of Information Engineering Central South University of Technology Changsha

ISBN: (纸本)0780363949

The quality of network services is directly affected by QoS routing algorithms,and QoS routing algorithms rely heavily on network state information specifying the resource availability at network nodes and *** practice,the network state information is not always accurate because it does not update in time. This paper proposes a randomized QoS routing algorithm on networks with inaccurate link-state information,and develops a simulation environment. Our algorithm reduces computational cost and protocol *** tests demonstrate that our algorithm performs very well in practice.

关键词： QoS network routing 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

来源：评论

学校读者我要写书评

暂无评论

Low-rank approximation algorithm using sparse projection and its applications

引用

Computational and Applied Mathematics 2025年第4期44卷

作者： Xiao, Han Yue-Hua, Feng Yong-xin, Dong School of Mathematics Physics and Statistics Shanghai University of Engineering Science Shanghai201620 China School of Law and Criminal Justice East China University of Political Science and Law Shanghai201620 China

We propose two random low-rank approximation algorithms based on sparse projection, SEMHMT and SEMTropp. Compared with HMT and Tropp algorithms, we mainly introduce Sparse Embedding Matrix (SEM) as sparse projection to speed up the computation. We analyze the convergence of the algorithms and compare the complexity of the proposed algorithms with the prototype algorithms. In addition, we expand these two algorithms to Tucker and TT formats of nonnegative tensors. By employing NSTHOSVD and NTTSVD with alternating projection, we preserve the nonnegativity of the original data, allowing for more efficient handling of large nonnegative tensor data. In numerical experiments, We first test the algorithms on matrix and verify its effectiveness. Then we apply them to Hilbert tensor, Multidimensional Gaussian mixture, and Hyperspectral image, and achieve good performance in terms of running speed and nonnegative preservation. © The Author(s) under exclusive licence to Sociedade Brasileira de Matemática Aplicada e Computacional 2025.

关键词： Low-rank approximation randomized algorithm Sparse embedding matrix Subspace iterative Tensor decomposition

来源：评论

学校读者我要写书评

暂无评论

Node2binary: Compact Graph Node Embeddings using Binary Vectors 25

Node2binary: Compact Graph Node Embeddings using Binary Vect...

引用

34th ACM Web Conference, WWW 2025

作者： Talukder, Niloy Gyurek, Croix Al Hasan, Mohammad Indiana University Indianapolis Indianapolis IN United States University of Waterloo Waterloo ON Canada

ISBN: (纸本)9798400712746

With the adoption of deep learning models to low-power, small-memory edge devices, energy consumption and storage usage of such models have become a key concern. The problem exacerbates even further with ever-growing data and equally-matched bulkier models. This concern is particularly pronounced for graph data due to its quadratic storage, irregular (non-grid) geometry, and very large size. Typical graph data, such as road networks, infrastructure networks, and social networks, easily exceeds millions of nodes, and several gigabytes of storage is needed just to store the node embedding vectors, let alone the model parameters. In recent years, the memory issue has been addressed by moving away from memory-intensive double precision floating-point arithmetic towards single-precision or even half-precision, often by trading-off marginally small performance. Along this effort, we propose Node2binary, which embeds graph nodes in as few as 128 binary bits, thereby reducing the memory footprint of vertex embedding vectors by several orders of magnitude. Node2binary leverages a fast community detection algorithm to convert the given graph into a hierarchical partition tree and then find embeddings of graph vertices in binary space by solving a combinatorial optimization (CO) task over the tree edges. CO is NP-hard, but Node2binary uses an innovative combination of discrete gradient descent and randomization to solve this task effectively and efficiently. Extensive experiments over four real-world graphs show that Node2binary achieves competitive performance compared to the state-of-the art graph embedding methods in both node classification and link prediction tasks. © 2025 Copyright held by the owner/author(s).

关键词： Binary Space Embedding Discrete Gradient Descent Graph Embedding randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

randomized algorithms for Parameterized Kidney Exchange Problem

Randomized Algorithms for Parameterized Kidney Exchange Prob...

引用

2015全国理论计算机科学学术年会

作者： Mugang Lin Jianxin Wang Qilong Feng School of Information Science and Engineering Central South UniversityChangsha 410083China Departm School of Information Science and Engineering Central South UniversityChangsha 410083China

Kidney exchange programs have been established in several countries to organize kidney exchanges between incompatible patient-donor *** core of these programs are algorithms to solve kidney exchange problem, which can be modeled as finding a maximum weight packing of vertex-disjoint cycles with length at most some small constant L (typically 2 ≤ L ≤ 5) in a directed *** generally, the objective function is maximizing the number of possible kidney *** this paper, we study the random methods for the kidney exchange problem involving only 2-cycle and 3-cycle ***, we formal the kidney exchange problem as a parameterized *** then we propose a randomized parameterized algorithm of running time O*(5.63k3 · 22k2) by randomly partitioning the ***, by using the random divide-and-conquer technique, another randomized algorithm of running time O* (k2[log k2/2.k3[logk3]/2.42k3.22k2) is given for the parameterized kidney ***,our randomized algorithms can be extended to solve the general kidney exchange problem.

关键词： Kidney exchange problem randomized algorithm Parameterized algorithm

来源：评论

学校读者我要写书评

暂无评论

An Improved randomized Circle Detection algorithm Using in Printed Circuit Board Locating Mark

引用

Applied Mathematics 2019年第10期10卷 848-861页

作者： Jingkun Liu Qi Fan Chengyi University College Jimei UniversityXiamenChina Xiamen Sinic-Tek Intelligent Technology Co. Ltd.XiamenChina

This paper presents an improved randomized Circle Detection (RCD) algorithm with the characteristic of circularity to detect randomized circle in images with complex background, which is not based on the Hough Transform. The experimental results denote that this algorithm can locate the circular mark of Printed Circuit Board (PCB).

关键词： Circle Detection randomized algorithm Characteristic of Circularity Printed Circuit Board

来源：评论

学校读者我要写书评

暂无评论

Fault Detection for Non-Gaussian Stochastic Distribution Systems Based on randomized algorithms

引用

IEEE TRANSACTIONS ON INSTRUMENTATION AND MEASUREMENT 2022年 71卷

作者： Zhao, Zhen Liu, Peter Xiaoping Gao, Jinfeng Zhejiang Sci Tech Univ Sch Mech Engn & Automat Hangzhou 310018 Peoples R China Carleton Univ Dept Syst & Comp Engn Ottawa ON K1S 5B6 Canada

This article presents a new fault detection scheme for stochastic distribution systems with non-Gaussian variables based on a probabilistic framework. The available information is the output probability density function (pdf) rather than the measured outputs themselves. The square-root B-spline function is utilized to formulate the output pdfs. Probabilistic parameter models are developed to characterize system uncertainties and faults. An observer is designed to detect the multiplicative and additive faults. The randomized algorithm is adopted to design the threshold to achieve an optimal balance between the false alarm rate (FAR) and the fault detection rate (FDR). The effectiveness of the proposed method is demonstrated and compared against existing work by utilizing a continuous stirred tank reactor system.

关键词： Uncertainty Probabilistic logic Fault detection Stochastic processes Probability density function Robustness Mathematical models Fault detection non-Gaussian stochastic system probabilistic robustness randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

randomized Robust Subspace Recovery and Outlier Detection for High Dimensional Data Matrices

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2017年第6期65卷 1580-1594页

作者： Rahmani, Mostafa Atia, George K. Univ Cent Florida Dept Elect & Comp Engn Orlando FL 32816 USA

This paper explores and analyzes two randomized designs for robust principal component analysis employing lowdimensional data sketching. In one design, a data sketch is constructed using random column sampling followed by lowdimensional embedding, while in the other, sketching is based on random column and rowsampling. Both designs are shown to bring about substantial savings in complexity andmemory requirements for robust subspace learning over conventional approaches that use the full scale data. A characterization of the sample and computational complexity of both designs is derived in the context of two distinct outliermodels, namely, sparse and independent outlier models. The proposed randomized approach can provably recover the correct subspace with computational and sample complexity which depend only weakly on the size of the data (only through the coherence parameters). The results of the mathematical analysis are confirmed through numerical simulations using both synthetic and real data.

关键词： Big data column/row sampling low rank matrix outlier detection randomized algorithm random embedding robust PCA sketching subspace learning

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：