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

Benchmarking principal component analysis for large-scale single-cell RNA-sequencing

GENOME BIOLOGY 2020年第1期21卷 9-9页

作者： Tsuyuzaki, Koki Sato, Hiroyuki Sato, Kenta Nikaido, Itoshi RIKEN Ctr Biosyst Dynam Res Lab Bioinformat Res Wako Saitama 3510198 Japan Japan Sci & Technol Agcy PRESTO Chiyoda Ku 5-3 Yonbancho Tokyo 1028666 Japan Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Sakyo Ku Yoshida Honmachi Kyoto 6068501 Japan Univ Tokyo Grad Sch Agr & Life Sci Dept Biotechnol Bunkyo Ku Tokyo 1138657 Japan Univ Tsukuba Sch Integrat & Global Majors SIGMA Masters Doctoral Program Life Sci Innovat T LSI Bioinformat Course 1-1-1 Tennodai Tsukuba Ibaraki 3058577 Japan

Background Principal component analysis (PCA) is an essential method for analyzing single-cell RNA-seq (scRNA-seq) datasets, but for large-scale scRNA-seq datasets, computation time is long and consumes large amounts of memory. Results In this work, we review the existing fast and memory-efficient PCA algorithms and implementations and evaluate their practical application to large-scale scRNA-seq datasets. Our benchmark shows that some PCA algorithms based on Krylov subspace and randomized singular value decomposition are fast, memory-efficient, and more accurate than the other algorithms. Conclusion We develop a guideline to select an appropriate PCA implementation based on the differences in the computational environment of users and developers.

关键词： Single-cell RNA-seq Cellular heterogeneity Dimension reduction Principal component analysis Online incremental algorithm randomized algorithm Out-of-core Sparse data format R Python Julia

来源：评论

学校读者我要写书评

暂无评论

Network Size Estimation in Small-World Networks under Byzantine Faults 33

Network Size Estimation in Small-World Networks under Byzant...

引用

33rd IEEE International Parallel and Distributed Processing Symposium (IPDPS)

作者： Chatterjee, Soumyottam Pandurangan, Gopal Robinson, Peter Univ Houston Dept Comp Sci Houston TX 77204 USA McMaster Univ Dept Comp & Software Hamilton ON Canada

ISBN: (纸本)9781728112466

We study the fundamental problem of counting the number of nodes in a sparse network (of unknown size) under the presence of a large number of Byzantine nodes. We assume the full information model where the Byzantine nodes have complete knowledge about the entire state of the network at every round (including random choices made by all the nodes), have unbounded computational power, and can deviate arbitrarily from the protocol. Essentially all known algorithms for fundamental Byzantine problems (e.g., agreement, leader election, sampling) studied in the literature assume the knowledge (or at least an estimate) of the size of the network. It is non-trivial to design algorithms for Byzantine problems that work without knowledge of the network size, especially in bounded-degree (expander) networks where the local views of all nodes are (essentially) the same and limited, and Byzantine nodes can quite easily fake the presence/absence of non-existing nodes. To design truly local algorithms that do not rely on any global knowledge (including network size), estimating the size of the network under Byzantine nodes is an important first step. Our main contribution is a randomized distributed algorithm that estimates the size of a network under the presence of a large number of Byzantine nodes. In particular, our algorithm estimates the size of a sparse, "small-world", expander network with up to O(n(1-delta)) Byzantine nodes, where n is the (unknown) network size and delta > 0 can be be any arbitrarily small (but fixed) constant. Our algorithm outputs a (fixed) constant factor estimate of log(n) with high probability;the correct estimate of the network size will be known to a large fraction ((1 - epsilon)-fraction, for any fixed positive constant) of the honest nodes. Our algorithm is fully distributed, lightweight, and simple to implement, runs in O (log(3) n) rounds, and requires nodes to send and receive messages of only small-sized messages per round;any node's local co

关键词： distributed algorithm counting byzantine behavior randomized algorithm small-world network expander

来源：评论

学校读者我要写书评

暂无评论

Asymptotic Efficiency of Distributed Random Sampling algorithm 38

Asymptotic Efficiency of Distributed Random Sampling Algorit...

引用

38th Chinese Control Conference (CCC)

作者： Liu, Qian He, Xingkang Fang, Haitao Chinese Acad Sci Acad Math & Syst Sci LSC Beijing 100190 Peoples R China Univ Chinese Acad Sci Sch Math Sci Beijing 100049 Peoples R China KTH Royal Inst Technol Sch Elect Engn & Comp Sci ACCESS Linnaeus Ctr SE-10044 Stockholm Sweden

ISBN: (纸本)9789881563972

In this paper, we focus on estimating the distribution of underlying parameter over random networks through reconstructing the empirical distribution of initial samples, which can be viewed as a particular average consensus problem. A class of quantized communication protocol, in which neighbors exchange information randomly selected based on the current estimate, is considered. To improve the convergence rate of this distributed random sampling algorithm, we introduce the Polyak average scheme, and show that asymptotic efficiency can be achieved through the averaging technique under proper conditions. The results show that the minimum limit covariance matrix of estimation error can be reached. i.e., the proposed algorithm achieves the highest possible rate of convergence. Finally, we provide a numerical simulation to validate the theoretical results of this work.

关键词： Average consensus distributed computation randomized algorithm asymptotic efficiency

来源：评论

学校读者我要写书评

暂无评论

Solving Simple Stochastic Games with Few Random Nodes Faster Using Bland's Rule 36

Solving Simple Stochastic Games with Few Random Nodes Faster...

引用

36th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Auger, David Coucheney, Pierre Strozecki, Yann Univ Versailles St Quentin En Yvelines DAVID Lab Versailles France

ISBN: (纸本)9783959771009

The best algorithm so far for solving Simple Stochastic Games is Ludwig's randomized algorithm [21] which works in expected 2(O(root n)) time. We first give a simpler iterative variant of this algorithm, using Bland's rule from the simplex algorithm, which uses exponentially less random bits than Ludwig's version. Then, we show how to adapt this method to the algorithm of Gimbert and Horn [15] whose worst case complexity is O(k!), where k is the number of random nodes. Our algorithm has an expected running time of 2(O(k)), and works for general random nodes with arbitrary outdegree and probability distribution on outgoing arcs.

关键词： simple stochastic games randomized algorithm parametrized complexity strategy improvement Bland's rule

来源：评论

学校读者我要写书评

暂无评论

VECTOR ADDRESSING FOR NON-SEQUENTIAL SAMPLING IN FIR IMAGE FILTERING 26

VECTOR ADDRESSING FOR NON-SEQUENTIAL SAMPLING IN FIR IMAGE F...

引用

26th IEEE International Conference on Image Processing (ICIP)

作者： Fukushima, Norishige Tsubokawa, Teppei Maeda, Yoshihiro Nagoya Inst Technol Nagoya Aichi Japan

ISBN: (纸本)9781538662496

Image filtering is fundamental in image processing. The acceleration is essential since image resolution has highly increased. For the acceleration, image subsampling is a general approach for any filtering. However, this approach has a drawback in accuracy due to image aliasing. Several papers moderate this problem by subsampling image or filtering kernel non-sequential sampling. In this paper, we improve the sampling combined with image and kernel subsampling. We also accelerate the work of non-sequential sampling by vector addressing of hardware acceleration. Experimental results show that the proposed method accelerate bilateral filtering and adaptive Gaussian filtering. Also, the proposed vector addressing accelerate both filters.

关键词： randomized algorithm randomized subsampling edge-preserving filtering vector addressing

来源：评论

学校读者我要写书评

暂无评论

Low-rank approximation of large-scale matrices via randomized methods

引用

JOURNAL OF SUPERCOMPUTING 2018年第2期74卷 830-844页

作者： Hatamirad, Sarvenaz Pedram, Mir Mohsen Kharazmi Univ Dept Elect & Comp Engn Fac Engn Tehran Iran

Decomposition of a matrix into low-rank matrices is a powerful tool for scientific computing and data analysis. The purpose is to obtain a low-rank matrix by decomposition of the original matrix into a product of smaller and lower-rank matrices or by randomly projecting the matrix down to a lower-dimensional space. Such decomposition requires less storage and computational burden. The focus of this paper is on randomized methods which try as much as possible to preserve the original matrix properties by applying the subspace sampling. In many applications, randomized algorithms in terms of accuracy, stability and speed are much better than the classical decomposition algorithms. In this study, we propose a sparse orthogonal transformation matrix to reduce the dimension of the data. The results show that compared with the most accurate methods, the transformation speed is much faster and can save a lot of memory in the case of huge matrices.

关键词： Matrix approximation Dimension reduction randomized algorithm Johnson-Lindenstrauss lemma Random matrix Column subset selection Big data

来源：评论

学校读者我要写书评

暂无评论

Dynamic Set Cover: Improved algorithms and Lower Bounds 2019

Dynamic Set Cover: Improved Algorithms and Lower Bounds

引用

51st Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Abboud, Amir Addanki, Raghavendra Grandoni, Fabrizio Panigrahi, Debmalya Saha, Barna IBM Almaden Res Ctr San Jose CA 95120 USA Univ Massachusetts Amherst Amherst MA USA IDSIA USI SUPSI Manno Switzerland Duke Univ Durham NC USA

ISBN: (纸本)9781450367059

We give new upper and lower bounds for the dynamic set cover problem. First, we give a (1 + epsilon)f-approximation for fully dynamic set cover in O(f(2) log n/epsilon(5)) (amortized) update time, for any epsilon > 0, where f is the maximum number of sets that an element belongs to. In the decremental setting, the update time can be improved to O(f(2)/epsilon(5)), while still obtaining an (1 + epsilon)f-approximation. These are the first algorithms that obtain an approximation factor linear in f for dynamic set cover, thereby almost matching the best bounds known in the offline setting and improving upon the previous best approximation of O(f(2)) in the dynamic setting. To complement our upper bounds, we also show that a linear dependence of the update time on f is necessary unless we can tolerate much worse approximation factors. Using the recent distributed PCP-framework, we show that any dynamic set cover algorithm that has an amortized update time of O(f(1-epsilon)) must have an approximation factor that is Omega(n(delta)) for some constant delta > 0 under the Strong Exponential Time Hypothesis.

关键词： dynamic algorithm randomized algorithm set cover competitive ratio

来源：评论

学校读者我要写书评

暂无评论

randomized k-set agreement in crash-prone and Byzantine asynchronous systems

引用

THEORETICAL COMPUTER SCIENCE 2018年 709卷 80-97页

作者： Mostefaoui, Achour Moumen, Hamouma Raynal, Michel Univ Nantes LINA F-44322 Nantes France Univ Batna Batna Algeria Inst Univ France Paris France Univ Rennes IRISA F-35042 Rennes France

k-Set agreement is a central problem of fault-tolerant distributed computing. Considering a set of n processes, where up to t may commit failures, let us assume that each process proposes a value. The problem consists in defining an algorithm such that each non-faulty process decides a value, at most k different values are decided, and the decided values satisfy some context-depending validity condition. algorithms solving k-set agreement in synchronous message-passing systems have been proposed for different failure models (mainly process crashes, and process Byzantine failures). Differently, k-set agreement cannot be solved in failure-prone asynchronous message-passing systems when t > k. To circumvent this impossibility an asynchronous system must be enriched with additional computational power. Assuming t > k, this paper presents two distributed algorithms that solve k-set agreement in asynchronous message-passing systems where up to t processes may commit crash failures (first algorithm) or more severe Byzantine failures (second algorithm). To circumvent k-set agreement impossibility, this article considers that the underlying system is enriched with the computability power provided by randomization. Interestingly, the algorithm that copes with Byzantine failures is signature-free, and ensures that no value proposed only by Byzantine processes can be decided by a non-faulty process. Both algorithms share basic design principles. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Asynchronous system Broadcast abstraction Byzantine process Coin Crash failure Distributed algorithm k-Set agreement Message-passing system randomized algorithm Signature-free algorithm

来源：评论

学校读者我要写书评

暂无评论

randomized Polynomial-Time Identity Testing for Noncommutative Circuits

引用

THEORY OF COMPUTING 2019年 15卷 1-36页

作者： Arvind, Vikraman Joglekar, Pushkar S. Mukhopadhyay, Partha Raja, S. Inst Math Sci HBNI Chennai Tamil Nadu India Vishwakarma Inst Technol Pune Maharashtra India Chennai Math Inst Chennai Tamil Nadu India Indian Inst Technol Tirupati Tirupati Andhra Pradesh India

In this paper we show that black-box polynomial identity testing (PIT) for n-variate noncommutative polynomials f of degree D with at most t nonzero monomials can be done in randomized poly(n, log t, log D) time, and consequently in randomized poly(n, log t, s) time if f is computable by a circuit of size s. This result makes progress on a question that has been open for over a decade. Our algorithm is based on efficiently isolating a monomial using nondeterministic automata. The above result does not yield an efficient randomized PIT for noncommutative circuits in general, as noncommutative circuits of size s can compute polynomials with a double-exponential (in s) number of monomials. As a first step, we consider a natural class of homogeneous noncommutative circuits, that we call +-regular circuits, and give a white-box polynomial-time deterministic PIT for them. These circuits can compute noncommutative polynomials with number of monomials double-exponential in the circuit size. Our algorithm combines some new structural results for +-regular circuits with known PIT results for noncommutative algebraic branching programs, a rank bound for commutative depth-3 identities, and an equivalence testing problem for words. Finally, we solve the black-box PIT problem for depth-3 +-regular circuits in randomized polynomial time. In particular, we show if f is a nonzero noncommutative polynomial in n variables over the field F computed by a depth-3 +-regular circuit of size s, then f cannot be a polynomial identity for the matrix algebra M-s(F) when F is sufficiently large depending on the degree of f.

关键词： algebraic complexity non-commutative computation polynomial identity testing randomized algorithm Polynomial Identity Lemma

来源：评论

学校读者我要写书评

暂无评论

Faster k-SAT algorithms using Biased-PPSZ 2019

Faster k-SAT Algorithms using Biased-PPSZ

引用

51st Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Hansen, Thomas Dueholm Kaplan, Haim Zamir, Or Zwick, Uri Univ Copenhagen Copenhagen Denmark Tel Aviv Univ Tel Aviv Israel

ISBN: (纸本)9781450367059

The PPSZ algorithm, due to Paturi, Pudlak, Saks and Zane, is currently the fastest known algorithm for the k-SAT problem, for every k > 3. For 3-SAT, a tiny improvement over PPSZ was obtained by Hertli. We introduce a biased version of the PPSZ algorithm using which we obtain an improvement over PPSZ for every k >= 3. For k = 3 we also improve on Herli's result and get a much more noticeable improvement over PPSZ, though still relatively small. In particular, for Unique 3-SAT, we improve the current bound from 1.308(n) to 1.307(n).

关键词： satisfiability randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：