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

Generative modeling via tensor train sketching

APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS 2023年第1期67卷

作者： Hur, YoonHaeng Hoskins, Jeremy G. Lindsey, Michael Stoudenmire, E. M. Khoo, Yuehaw Univ Chicago Dept Stat Chicago IL 60637 USA NYU Courant Inst Math Sci Dept Math New York NY USA Flatiron Inst Ctr Computat Quantum Phys New York NY USA

In this paper, we introduce a sketching algorithm for constructing a tensor train representation of a probability density from its samples. Our method deviates from the standard recursive SVD-based procedure for constructing a tensor train. Instead, we formulate and solve a sequence of small linear systems for the individual tensor train cores. This approach can avoid the curse of dimensionality that threatens both the algorithmic and sample complexities of the recovery problem. Specifically, for Markov models under natural conditions, we prove that the tensor cores can be recovered with a sample complexity that scales logarithmically in the dimensionality. Finally, we illustrate the performance of the method with several numerical experiments.& COPY;2023 Elsevier Inc. All rights reserved.

关键词： Tensor decompositions Tensor train randomized algorithm Generative modeling High-dimensional function approximation

来源：评论

学校读者我要写书评

暂无评论

Multidimensional phase recovery and interpolative decomposition butterfly factorization

引用

JOURNAL OF COMPUTATIONAL PHYSICS 2020年 412卷 109427-109427页

作者： Chen, Ze Zhang, Juan Ho, Kenneth L. Yang, Haizhao Natl Univ Singapore Dept Math Singapore Singapore Xiangtan Univ Dept Math & Computat Sci Xiangtan Peoples R China Flatiron Inst Ctr Computat Math New York NY USA Purdue Univ Dept Math W Lafayette IN 47907 USA

This paper focuses on the fast evaluation of the matrix-vector multiplication (matvec) g= Kf for K is an element of C-NxN, which is the discretization of a multidimensional oscillatory integral transform g(x) = similar to K(x,xi) f(xi)d xi with a kernel function K(x, xi) = e(2 pi i Phi(x,xi)), where Phi(x, xi) is a piecewise smooth phase function with x and xi in R-d for d = 2 or 3. A new framework is introduced to compute Kfwith O ( Nlog(N)) time and memories complexity in the case that only indirect access to the phase function Phi is available. This framework consists of two main steps: 1) an O (Nlog(N)) algorithm for recovering the multidimensional phase function Phi from indirect access is proposed;2) a multidimensional interpolative decomposition butterfly factorization (MIDBF) is designed to evaluate the matvec Kfwith an O (Nlog( N)) complexity once Phi is available. Numerical results are provided to demonstrate the effectiveness of the proposed framework. (C) 2020 Elsevier Inc. All rights reserved.

关键词： Data-sparse matrix Butterfly factorization Interpolative decomposition Operator compression randomized algorithm Matrix completion

来源：评论

学校读者我要写书评

暂无评论

Sublinear message bounds of authenticated implicit Byzantine agreement

引用

THEORETICAL COMPUTER SCIENCE 2024年 1022卷

作者： Kumar, Manish Molla, Anisur Rahaman IIT Madras Dept Comp Sci & Engn Chennai 600036 India Indian Stat Inst Cryptol & Secur Res Unit Kolkata 700108 India

This paper studies the message complexity of authenticated Byzantine agreement (BA) in synchronous, fully-connected distributed networks under an honest majority. We focus on the so-called implicit Byzantine agreement problem where each node starts with an input value and at the end a non-empty subset of the honest nodes should agree on a common input value by satisfying the BA properties (i.e., there can be undecided nodes)(3). We show that a sublinear (in n, number of nodes) message complexity BA protocol under honest majority is possible in the standard PKI model when the nodes have access to an unbiased global coin and hash function. In particular, we present a randomized Byzantine agreement algorithm which, with high probability achieves implicit agreement, uses O(root n) messages, and runs in O(1) rounds while tolerating (1/2-& varepsilon;)n Byzantine nodes for any fixed & varepsilon;>0, the notation O hides a O(polylogn) factor(4). The algorithm requires standard cryptographic setup PKI and hash function with a static Byzantine adversary. The algorithm works in the CONGEST model and each node does not need to know the identity of its neighbors, i.e., works in the KT0 model. The message complexity (and also the time complexity) of our algorithm is optimal up to a polylog n factor, as we show a Omega(n) lower bound on the message complexity. We further extend the result to Byzantine subset agreement, where a non-empty subset of nodes should agree on a common value. Lastly, we analyze several relevant results that follow from the construction of the main result. To the best of our knowledge, this is the first sublinear message complexity result of Byzantine agreement. A quadratic message lower bound is known for any deterministic BA protocol (due to Dolev-Reischuk [JACM 1985]). The existing randomized BA protocols have at least quadratic message complexity in the honest majority setting. Our result shows the power of a global coin in achieving significant improv

关键词： Distributed algorithm randomized algorithm Byzantine agreement Message complexity Global coin Cryptographic assumptions

来源：评论

学校读者我要写书评

暂无评论

A fast sketching-based algorithm for rank-(L, L, 1) block term decomposition

引用

APPLIED MATHEMATICS LETTERS 2022年第0期133卷

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

The rank-(L, L, 1) block term decomposition (BTD) of the tensor has recently received increasing attention in diverse high-order data processing, e.g., hyperspectral image restoration and blind source separation. However, the standard alternating least squares algorithm for the rank-(L, L, 1) BTD (BTD-ALS) is computationally expensive, which hinders its application on real large-scale data. In this paper, we propose a fast sketching-based algorithm for the rank-(L, L, 1) BTD (FastBTD) to address the computational burden of BTD-ALS. Since the dominant cost of BTD-ALS at each iteration is the sequence of large-scale least squares subproblems, we first project these original subproblems into the low-dimensional subspace by the tensor sketching operator. Then, we can fastly obtain the approximate solutions of the original subproblems by solving these sketched small-scale subproblems at each iteration of FastBTD. The computational complexity of FastBTD (O(2JILR + JIR)) is significantly lower than that of BTD-ALS (O(2I(3)LR + (IR)-R-3)) for solving the least squares subproblems at each iteration, when J << I-2. Moreover, we provide the theoretical error bound for FastBTD. Extensive experiments on both synthetic and real data demonstrate that FastBTD achieves substantial speedup while maintaining accuracy compared with BTD-ALS. (C) 2022 Elsevier Ltd. All rights reserved.

关键词： Block term decomposition randomized algorithm Tensor sketching High-order data processing

来源：评论

学校读者我要写书评

暂无评论

PARALLEL HASHING - AN EFFICIENT IMPLEMENTATION OF SHARED MEMORY

引用

JOURNAL OF THE ACM 1988年第4期35卷 876-892页

作者： KARLIN, AR UPFAL, E IBM CORP ALMADEN RES CTRALMADENCA 95120

A central issue in the theory of parallel computation is the gap between the ideal models that utilize shared memory and the feasible models that consist of a bounded-degree network of processors sharing no common memory. This problem has been widely studied. Here a tight bound for the probabilistic complexity of this problem is established. The solution in this paper is based on a probabilistic scheme for implementing shared memory on a bounded-degree network of processors. This scheme, which we term parallel has/zing, enables n processors to store and retrieve an arbitrary set of n data items in O(logn) parallel steps. The items’ locations are specified by a function chosen randomly from a small class of universal hash functions. A hash function in this class has a small description and can therefore be efficiently distributed among the processors. A deterministic lower bound for the point-to-point communication model is also presented. © 1988, ACM. All rights reserved.

关键词： Feasible model parallel algorithm probabilistic computation randomized algorithm routing simulation between models theoretical model

来源：评论

学校读者我要写书评

暂无评论

A probabilistic algorithm for aggregating vastly undersampled large Markov chains

引用

PHYSICA D-NONLINEAR PHENOMENA 2021年 416卷 132799-132799页

作者： Bittracher, Andreas Schuette, Christof Free Univ Berlin Dept Math & Comp Sci Berlin Germany Zuse Inst Berlin Berlin Germany

Model reduction of large Markov chains is an essential step in a wide array of techniques for understanding complex systems and for efficiently learning structures from high-dimensional data. We present a novel aggregation algorithm for compressing such chains that exploits a specific low rank structure in the transition matrix which, e.g., is present in metastable systems, among others. It enables the recovery of the aggregates from a vastly undersampled transition matrix which in practical applications may gain a speedup of several orders of magnitude over methods that require the full transition matrix. Moreover, we show that the new technique is robust under perturbation of the transition matrix. The practical applicability of the new method is demonstrated by identifying a reduced model for the large-scale traffic flow patterns from real-world taxi trip data. (C) 2020 The Authors. Published by Elsevier B.V.

关键词： Markov chain Aggregation Sparse sampling Metastability randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Pass-efficient methods for compression of high-dimensional turbulent flow data

引用

JOURNAL OF COMPUTATIONAL PHYSICS 2020年 423卷 109704-109704页

作者： Dunton, Alec M. Jofre, Lluis Iaccarino, Gianluca Doostan, Alireza Univ Colorado Appl Math Boulder CO 80309 USA Stanford Univ Ctr Turbulence Res Stanford CA 94305 USA Tech Univ Catalonia BarcelonaTech Dept Fluid Mech Barcelona 08019 Spain Univ Colorado Smead Aerosp Engn Sci Boulder CO 80309 USA

The future of high-performance computing, specifically on future Exascale computers, will presumably see memory capacity and bandwidth fail to keep pace with data generated, for instance, from massively parallel partial differential equation (PDE) systems. Current strategies proposed to address this bottleneck entail the omission of large fractions of data, as well as the incorporation of in situ compression algorithms to avoid overuse of memory. To ensure that post-processing operations are successful, this must be done in a way that a sufficiently accurate representation of the solution is stored. Moreover, in situations where the input/output system becomes a bottleneck in analysis, visualization, etc., or the execution of the PDE solver is expensive, the number of passes made over the data must be minimized. In the interest of addressing this problem, this work focuses on the utility of pass-efficient, parallelizable, low-rank, matrix decomposition methods in compressing high-dimensional simulation data from turbulent flows. A particular emphasis is placed on using coarse representation of the data - compatible with the PDE discretization grid - to accelerate the construction of the low-rank factorization. This includes the presentation of a novel single-pass matrix decomposition algorithm for computing the so-called interpolative decomposition. The methods are described extensively and numerical experiments on two turbulent channel flow data are performed. In the first (unladen) channel flow case, compression factors exceeding 400 are achieved while maintaining accuracy with respect to first- and second-order flow statistics. In the particle-laden case, compression factors of 100 are achieved and the compressed data is used to recover particle velocities. These results show that these compression methods can enable efficient computation of various quantities of interest in both the carrier and disperse phases. (C) 2020 Elsevier Inc. All rights reserved.

关键词： Big-data compression Interpolative decomposition Low-rank approximation Particle-laden turbulence randomized algorithm Single-pass algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved stochastic configuration networks with vision patch fusion method for industrial image classification

引用

INFORMATION SCIENCES 2024年 670卷

作者： Li, Ruilin Jiao, Wenhua Zhu, Yongjun China Univ Min & Technol Sch Informat & Control Engn Xuzhou 221000 Jiangsu Peoples R China China Univ Min & Technol Artificial Intelligence Res Inst Xuzhou 221000 Jiangsu Peoples R China

This paper contributes to the advancement of stochastic configuration neural networks (SCN) in the field of visual applications. The proposed image classification randomized algorithm is an extension of deep stochastic configuration networks (DeepSCN), known as an improved SCN with vision patch fusion (Vi-SCN). Compared to existing two dimensional stochastic configuration networks (2DSCN) and DeepSCN, we have developed an incremental modeling method that employs a stochastic configuration patch fusion method. This method extracts randomly fused image features from three-channel high-resolution image data, improving the network's ability to extract features. Moreover, we have introduced a strategy for dynamically determining the depth structure of the network, enabling flexible adjustments to the network structure and the number of nodes in each layer based on the complexity of image recognition tasks. Through a series of comparisons on four image classification benchmark datasets, we assess the superior learning performance of our design compared to 2DSCN and DeepSCN. Furthermore, to evaluate the performance of Vi-SCN in practical visual application scenarios, we collect three industrial datasets with distinct characteristics. Vi-SCN demonstrate outstanding performance in all three tasks, showing its significant potential in image recognition.

关键词： Stochastic configuration networks Image classification randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Adaptive work-stealing with parallelism feedback

引用

ACM TRANSACTIONS ON COMPUTER SYSTEMS 2008年第3期26卷 7:1-7:32页

作者： Agrawal, Kunal Leiserson, Charles E. He, Yuxiong Hsu, Wen Jing MIT Cambridge MA 02139 USA Nanyang Technol Univ Singapore 639798 Singapore

Multiprocessor scheduling in a shared multiprogramming environment can be structured as two-level scheduling, where a kernel-level job scheduler allots processors to jobs and a user-level thread scheduler schedules the work of a job on its allotted processors. We present a randomized work-stealing thread scheduler for fork-join multithreaded jobs that provides continual parallelism feedback to the job scheduler in the form of requests for processors. Our A-STEAL algorithm is appropriate for large parallel servers where many jobs share a common multiprocessor resource and in which the number of processors available to a particular job may vary during the job's execution. Assuming that the job scheduler never allots a job more processors than requested by the job's thread scheduler, A-STEAL guarantees that the job completes in near-optimal time while utilizing at least a constant fraction of the allotted processors. We model the job scheduler as the thread scheduler's adversary, challenging the thread scheduler to be robust to the operating environment as well as to the job scheduler's administrative policies. For example, the job scheduler might make a large number of processors available exactly when the job has little use for them. To analyze the performance of our adaptive thread scheduler under this stringent adversarial assumption, we introduce a new technique called trim analysis, which allows us to prove that our thread scheduler performs poorly on no more than a small number of time steps, exhibiting near-optimal behavior on the vast majority. More precisely, suppose that a job has work T-1 and span T-infinity. On a machine with P processors, A-STEAL completes the job in an expected duration of O(T-1/(P) over tilde + T-infinity + L lg P) time steps, where L is the length of a scheduling quantum, and (P) over tilde denotes the O(T-infinity + L lg P)-trimmed availability. This quantity is the average of the processor availability over all time steps except the

关键词： algorithms performance theory experimentation adaptive scheduling adversary span instantaneous parallelism job scheduling multiprocessing multiprogramming parallelism feedback parallel computation processor allocation randomized algorithm thread scheduling two-level scheduling space sharing trim analysis work work-stealing

来源：评论

学校读者我要写书评

暂无评论

Fast Matrix Rank algorithms and Applications

引用

JOURNAL OF THE ACM 2013年第5期60卷 31-31页

作者： Cheung, Ho Yee Kwok, Tsz Chiu Lau, Lap Chi Univ So Calif Dept Comp Sci Los Angeles CA 90089 USA Chinese Univ Hong Kong Dept Comp Sci & Engn Hong Kong Hong Kong Peoples R China

We consider the problem of computing the rank of an m x n matrix A over a field. We present a randomized algorithm to find a set of r = rank(A) linearly independent columns in (O) over tilde(vertical bar A vertical bar + r(omega)) field operations, where vertical bar A vertical bar denotes the number of nonzero entries in A and omega < 2.38 is the matrix multiplication exponent. Previously the best known algorithm to find a set of r linearly independent columns is by Gaussian elimination, with deterministic running time O(mnr(omega-2)). Our algorithm is faster when r < max{m, n}, for instance when the matrix is rectangular. We also consider the problem of computing the rank of a matrix dynamically, supporting the operations of rank one updates and additions and deletions of rows and columns. We present an algorithm that updates the rank in (O) over tilde (mn) field operations. We show that these algorithms can be used to obtain faster algorithms for various problems in exact linear algebra, combinatorial optimization and dynamic data structure.

关键词： algorithms Theory Combinatorial optimization exact linear algebra matrix rank randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：