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

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 SELF-ASSEMBLY FOR EXACT SHAPES

引用

SIAM JOURNAL ON COMPUTING 2010年第8期39卷 3521-3552页

作者： Doty, David Univ Western Ontario Dept Comp Sci London ON N6A 5B7 Canada

Working in Winfree's abstract tile assembly model, we show that a constant-sized tile assembly system can be programmed through relative tile concentrations to build an n x n square with high probability for any sufficiently large n. This answers an open question of Kao and Schweller [Automata, Languages and Programming, Lecture Notes in Comput. Sci. 5125, Springer, Berlin, 2008, pp. 370-384], who showed how to build an approximately n x n square using tile concentration programming and asked whether the approximation could be made exact with high probability. We show how this technique can be modified to answer another question of Kao and Schweller by showing that a constant-sized tile assembly system can be programmed through tile concentrations to assemble arbitrary finite scaled shapes, which are shapes modified by replacing each point with a c x c block of points for some integer c. Furthermore, we exhibit a smooth trade-off between specifying bits of n via tile concentrations versus specifying them via hard-coded tile types, which allows tile concentration programming to be employed for specifying a fraction of the bits of "input" to a tile assembly system, under the constraint that concentrations can be specified to only a limited precision. Finally, to account for some unrealistic aspects of the tile concentration programming model, we show how to modify the construction to use only concentrations that are arbitrarily close to uniform.

关键词： self-assembly molecular computation randomized algorithm tile concentration programming

来源：评论

学校读者我要写书评

暂无评论

Locally guided randomized elections in trees:: The totally fair case

引用

INFORMATION AND COMPUTATION 2005年第1期198卷 40-55页

作者： Métivier, Y Saheb-Djahromi, N Zemmari, A Univ Bordeaux 1 LaBRI ENSEIRB F-33405 Talence France

We design and analyze a randomized one-passage election algorithm in trees based on a result of Angluin in [Proceedings of the 12th Symposium on Theory of Computing, 1980, pp. 82]. The election process is a distributed elimination scheme which removes leaves one-by-one reducing the tree to a single vertex, called the leader (or elected vertex). We define a locally computable parameter guiding randomly the elimination process. As a particular instance, we provide a parameter assignment in a Markovian type random process in which all vertices have the same chance of being elected. (c) 2005 Elsevier Inc. All rights reserved.

关键词： distributed algorithm election probabilistic analysis randomized algorithm stochastic process

来源：评论

学校读者我要写书评

暂无评论

randomized nonnegative matrix factorization

引用

PATTERN RECOGNITION LETTERS 2018年 104卷 1-7页

作者： Erichson, N. Benjamin Mendible, Ariana Wihlborn, Sophie Kutz, J. Nathan Univ Washington Dept Appl Math Seattle WA 98195 USA Fidel Int London England

Nonnegative matrix factorization (NMF) is a powerful tool for data mining. However, the emergence of 'big data' has severely challenged our ability to compute this fundamental decomposition using deterministic algorithms. This paper presents a randomized hierarchical alternating least squares (HALS) algorithm to compute the NMF. By deriving a smaller matrix from the nonnegative input data, a more efficient nonnegative decomposition can be computed. Our algorithm scales to big data applications while attaining a near-optimal factorization, i.e., the algorithm scales with the target rank of the data rather than the ambient dimension of measurement space. The proposed algorithm is evaluated using synthetic and real world data and shows substantial speedups compared to deterministic HALS. (c) 2018 Elsevier B.V. All rights reserved.

关键词： NMF randomized algorithm Dimension reduction

来源：评论

学校读者我要写书评

暂无评论

randomized Boolean decision trees: Several remarks

引用

THEORETICAL COMPUTER SCIENCE 1998年第2期207卷 329-342页

作者： Vereshchagin, NK Moscow MV Lomonosov State Univ Fac Mech & Math Dept Math Log Moscow 119899 Russia

Assume we want to show that (a) the cost of any randomized decision tree computing a given Boolean function is at least c. To this end, it suffices to prove that (b) there is a probability distribution over the set of all assignments to variables of that function with respect to which the average cost of any deterministic decision tree computing that function is at least c. Yao (1977) showed that this method is universal for proving lower bounds for randomized errorless decision trees, that is, that (a) is equivalent to (b), In the present paper we prove that this is the case also for randomized decision trees which are allowed to make errors. This gives the positive answer to the question posed in Yao (1977), In the second part of the paper we exhibit an example when randomized directional decision trees (defined in Yao (1977)) to evaluate read once formulae are not optimal. We construct a formula F-n of n Boolean variables such that the cost of the optimal directional decision tree computing F-n is Omega(n(alpha)) and there is an undirectional randomized decision tree computing F-n of cost O(n(beta)) for some beta < alpha. (C) 1998-Elsevier Science B,V. All rights reserved.

关键词： Boolean decision trees randomized algorithm directional algorithms undirectional algorithms

来源：评论

学校读者我要写书评

暂无评论

COMPUTING LOW-RANK APPROXIMATIONS OF LARGE-SCALE MATRICES WITH THE TENSOR NETWORK randomized SVD

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2018年第3期39卷 1221-1244页

作者： Batselier, Kim Yu, Wenjian Daniel, Luca Wong, Ngai Univ Hong Kong Dept Elect & Elect Engn Hong Kong Peoples R China Tsinghua Univ Dept Comp Sci & Technol BNRist Beijing 100084 Peoples R China MIT Dept Elect Engn & Comp Sci Cambridge MA 02139 USA

We propose a new algorithm for the computation of a singular value decomposition (SVD) low-rank approximation of a matrix in the matrix product operator (MPO) format, also called the tensor train matrix format. Our tensor network randomized SVD (TNrSVD) algorithm is an MPO implementation of the randomized SVD algorithm that is able to compute dominant singular values and their corresponding singular vectors. In contrast to the state-of-the-art tensor-based alternating least squares SVD (ALS-SVD) and modified alternating least squares SVD (MALS-SVD) matrix approximation methods, TNrSVD can be up to 13 times faster while achieving better accuracy. In addition, our TNrSVD algorithm also produces accurate approximations in particular cases where both ALS-SVD and MALS-SVD fail to converge. We also propose a new algorithm for the fast conversion of a sparse matrix into its corresponding MPO form, which is up to 509 times faster than the standard tensor train SVD method while achieving machine precision accuracy. The efficiency and accuracy of both algorithms are demonstrated in numerical experiments.

关键词： curse of dimensionality low-rank tensor approximation matrix factorization matrix product operator singular value decompositon (SVD) tensor network tensor train (TT) decomposition randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Planar motion detection by randomized triangle matching

引用

PATTERN RECOGNITION LETTERS 1997年第8期18卷 741-749页

作者： Fermin, I Imiya, A Chiba Univ Dept Informat & Comp Sci Inage Ku Chiba 263 Japan

This paper proposes a randomized algorithm for the estimation of the planar motion parameters of a bounded closed set. By randomly searching triangles on two shapes measured at different times, the algorithm solves the rigid motion equation using correspondences between edges of triangles which are detected using a random search and a voting procedure. (C) 1997 Elsevier Science B.V.

关键词： rigid motion Hough transform randomized algorithm point correspondences planar shape triangle search geometric probing

来源：评论

学校读者我要写书评

暂无评论

randomized Approximation for the Set Multicover Problem in Hypergraphs

引用

algorithmICA 2016年第2期74卷 574-588页

作者： El Ouali, Mourad Munstermann, Peter Srivastav, Anand Univ Kiel Dept Comp Sci D-24118 Kiel Germany

Let b is an element of N->= 1 and let H = (V, epsilon) be a hypergraph with maximum vertex degree Delta and maximum edge size l. A set b-multicover in H is a set of edges C subset of epsilon such that every vertex in V belongs to at least edges in C SET b-MULTICOVER is the problem of finding a set b-multicover of minimum cardinality, and for b=1 it is the fundamental set cover problem. Peleg et al. (algorithmica 18(1):44-66, 1997) gave a randomized algorithm achieving an approximation ratio of delta . (1-(c/n)(1/delta)), where delta := Delta-b+1 and c > 0 is a constant. As this ratio depends on the instance size n and tends to delta as n tends to infinity, it remained an open problem whether an approximation ratio of delta alpha with a constant alpha < 1 can be proved. In fact, the authors conjectured that for any fixed Delta and b, the problem is not approximable within a ratio smaller than delta, unless p = NP. We present a randomized algorithm of hybrid type for SET b-MULTICOVER, b >= 2, combining LP-based randomized rounding with greedy repairing, and achieve an approximation ratio of delta. (1- 11(Delta-b)/72l)) for hypergraphs with maximum edge size l is an element of Omicron (max {(nb)(1/5),n(1/4)}) . In particular, for all hypergraphs where l is constant, we get an alpha delta-ratio with constant alpha < 1. Hence the above stated conjecture does not hold for hypergraphs with constant l and we have identified the boundedness of the maximum hyperedge size as a relevant parameter responsible for approximations below delta.

关键词： Combinatorial optimization Approximation algorithms randomized algorithm Hypergraphs Set cover and set multicover

来源：评论

学校读者我要写书评

暂无评论

randomized TENSOR WHEEL DECOMPOSITION

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2024年第3期46卷 A1714-A1746页

作者： Wang, Mengyu Yu, Yajie Li, Hanyu Chongqing Univ Coll Math & Stat Chongqing 401331 Peoples R China

Tensor wheel (TW) decomposition is an elegant compromise of the popular tensor ring decomposition and fully connected tensor network decomposition, and it has many applications. In this work, we investigate the computation of this decomposition. Three randomized algorithms based on random sampling or random projection are proposed. Specifically, by defining a new tensor product called the subwheel product, the structures of the coefficient matrices of the alternating least squares subproblems from the minimization problem of TW decomposition are first figured out. Then, using the structures and the properties of the subwheel product, a random sampling algorithm based on leverage sampling and two random projection algorithms respectively based on Kronecker subsampled randomized Fourier transform and TensorSketch are derived. These algorithms can implement the sampling and projection on TW factors and hence can avoid forming the full coefficient matrices of subproblems. We present the complexity analysis and numerical performance on synthetic data, real data, and image reconstruction for our algorithms. Experimental results show that, compared with the deterministic algorithm in the literature, they need much less computing time while achieving similar accuracy and reconstruction effect. We also apply the proposed algorithms to tensor completion and find that the sampling-based algorithm always has excellent performance and the projection-based algorithms behave well when the sampling rate is higher than 50\%.

关键词： tensor wheel decomposition randomized algorithm alternating least squares lever- age sampling Kronecker subsampled randomized Fourier transform TensorSketch

来源：评论

学校读者我要写书评

暂无评论

randomized approximation of Sobolev embeddings, III

引用

JOURNAL OF COMPLEXITY 2009年第5期25卷 473-507页

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

We continue the study of randomized approximation of embeddings between Sobolev spaces on the basis of function values. The source space is a Sobolev space with nonnegative smoothness order;the target space has negative smoothness order. The optimal order of approximation (in some cases only up to logarithmic factors) is determined. Extensions to Besov and Bessel potential spaces are given and a problem recently posed by Novak and Wozniakowski is partially solved. The results are applied to the complexity analysis of weak solution of elliptic PDE. (C) 2009 Elsevier Inc. All rights reserved.

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：