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

The Journal of Machine Learning Research 2022年第1期23卷 6185-6204页

作者： Samuel Herrmann Cristina Zucca Institut de Mathématiques de Bourgogne (IMB) UMR 5584 CNRS Université de Bourgogne Franche-Comté Dijon France Department of Mathematics 'G. Peano' University of Torino Turin Italy

In order to describe or estimate different quantities related to a specific random variable, it is of prime interest to numerically generate such a variate. In specific situations, the exact generation of random variables might be either momentarily unavailable or too expensive in terms of computation time. It therefore needs to be replaced by an approximation procedure. As was previously the case, the ambitious exact simulation of first exit times for diffusion processes was unreachable though it concerns many applications in different fields like mathematical finance, neuroscience or reliability. The usual way to describe first exit times was to use discretization schemes, that are of course approximation procedures. Recently, Herrmann and Zucca (Herrmann and Zucca, 2020) proposed a new algorithm, the so-called GDET-algorithm (General Diffusion Exit Time), which permits to simulate exactly the first exit time for one-dimensional diffusions. The only drawback of exact simulation methods using an acceptance-rejection sampling is their time consumption. In this paper the authors highlight an acceleration procedure for the GDET-algorithm based on a multi-armed bandit model. The efficiency of this acceleration is pointed out through numerical examples.

关键词： exit time Brownian motion diffusion processes rejection sampling exact simulation multi-armed bandit randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Practical Sketching algorithms for Low-Rank Tucker Approximation of Large Tensors

引用

JOURNAL OF SCIENTIFIC COMPUTING 2023年第2期95卷 52-52页

作者： Dong, Wandi Yu, Gaohang Qi, Liqun Cai, Xiaohao Hangzhou Dianzi Univ Dept Math Hangzhou Peoples R China Huawei Theory Res Lab Hong Kong Peoples R China Univ Southampton Sch Elect & Comp Sci Southampton England

Low-rank approximation of tensors has been widely used in high-dimensional data analysis. It usually involves singular value decomposition (SVD) of large-scale matrices with high computational complexity. Sketching is an effective data compression and dimensionality reduction technique applied to the low-rank approximation of large matrices. This paper presents two practical randomized algorithms for low-rank Tucker approximation of large tensors based on sketching and power scheme, with a rigorous error-bound analysis. Numerical experiments on synthetic and real-world tensor data demonstrate the competitive performance of the proposed algorithms.

关键词： Tensor sketching randomized algorithm Tucker decomposition Subspace power iteration High-dimensional data

来源：评论

学校读者我要写书评

暂无评论

Sufficient Dimension Reduction via Random-Partitions for the Large-p-Small-n Problem

引用

BIOMETRICS 2019年第1期75卷 245-255页

作者： Hung, Hung Huang, Su-Yun Natl Taiwan Univ Inst Epidemiol & Prevent Med Taipei Taiwan Acad Sinica Inst Stat Sci Taipei Taiwan

Sufficient dimension reduction (SDR) continues to be an active field of research. When estimating the central subspace (CS), inverse regression based SDR methods involve solving a generalized eigenvalue problem, which can be problematic under the large-p-small-n situation. In recent years, new techniques have emerged in numerical linear algebra, called randomized algorithms or random sketching, for high-dimensional and large scale problems. To overcome the large-p-small-n SDR problem, we combine the idea of statistical inference with random sketching to propose a new SDR method, called integrated random-partition SDR (iRP-SDR). Our method consists of the following three steps: (i) Randomly partition the covariates into subsets to construct an envelope subspace with low dimension. (ii) Obtain a sketch of the CS by applying a conventional SDR method within the constructed envelope subspace. (iii) Repeat the above two steps many times and integrate these multiple sketches to form the final estimate of the CS. After describing the details of these steps, the asymptotic properties of iRP-SDR are established. Unlike existing methods, iRP-SDR does not involve the determination of the structural dimension until the last stage, which makes it more adaptive to a high-dimensional setting. The advantageous performance of iRP-SDR is demonstrated via simulation studies and a practical example analyzing EEG data.

关键词： Distance correlation screening randomized algorithm Random-partition Random sketching Sufficient dimension reduction Sure screening property

来源：评论

学校读者我要写书评

暂无评论

Approximate NFA universality and related problems motivated by information theory

引用

THEORETICAL COMPUTER SCIENCE 2023年第1期972卷

作者： Konstantinidis, Stavros Mastnak, Mitja Moreira, Nelma Reis, Rogerio St Marys Univ Math & CS 923 Robie Str Halifax NS B3H 3C3 Canada Univ Porto Fac Ciencias CMUP & DM DCC Rua Campo Alegre P-4169007 Porto Portugal

In coding and information theory, it is desirable to construct maximal codes that can be either variable length codes or error control codes of fixed length. However deciding code maximality boils down to deciding whether a given NFA is universal, and this is a hard problem (including the case of whether the NFA accepts all words of a fixed length). On the other hand, it is acceptable to know whether a code is 'approximately' maximal, which then boils down to whether a given NFA is 'approximately' universal. Here we introduce the notion of a (1 - & epsilon;)-universal automaton and present polynomial randomized approximation algorithms to test NFA universality and related hard automata problems, for certain natural probability distributions on the set of words. We also conclude that the randomization aspect is necessary, as approximate universality remains hard for any fixed polynomially computable & epsilon;.& COPY;2023 Elsevier B.V. All rights reserved.

关键词： NFA universality Approximation randomized algorithm PSPACE hard

来源：评论

学校读者我要写书评

暂无评论

Quantized Feedback Stabilization of Sampled-Data Switched Linear Systems

引用

IFAC Proceedings Volumes 2014年第3期47卷 9979-9984页

作者： Masashi Wakaiki Yutaka Yamamoto Graduate School of Informatics Kyoto University Kyoto 606-8501 Japan

We propose a stability analysis method for sampled-data switched linear systems with quantization. The available information to the controller is limited: the quantized state and switching signal at each sampling time. Switching between sampling times can produce the mismatch of the modes between the plant and the controller. Moreover, the coarseness of quantization makes the trajectory wander around, not approach, the origin. Hence the trajectory may leave the desired neighborhood if the mismatch leads to instability of the closed-loop system. For the stability of the switched systems, we develop a sufficient condition characterized by the total mismatch time . The relationship between the mismatch time and the dwell time of the switching signal is also discussed.

关键词： Quantization sampled-data control switched systems Lyapunov function randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

A Self-Stabilizing algorithm for Maximal Matching in Anonymous Networks

引用

PARALLEL PROCESSING LETTERS 2016年第4期26卷 1650016-1650016页

作者： Cohen, Johanne Lefevre, Jonas Maamra, Khaled Pilard, Laurence Sohier, Devan Univ Paris Saclay Univ Paris Sud CNRS LRI Paris France Univ Paris Saclay Ecole Polytech CNRS LIX Paris France Univ Paris Saclay Univ Versailles St Quentin LI PaRAD Paris France

We propose a self-stabilizing algorithm for computing a maximal matching in an anonymous network. The complexity is O(n(2)) moves with high probability, under the adversarial distributed daemon. Among all adversarial distributed daemons and with the anonymous assumption, our algorithm provides the best known complexity. Moreover, the previous best known algorithm working under the same daemon and using identity has a O(m) complexity leading to the same order of growth than our anonymous algorithm. Finally, we do not make the common assumption that a node can determine whether one of its neighbors points to it or to another node, and still we present a solution with the same asymptotic behavior.

关键词： randomized algorithm self-stabilization maximal matching anonymous network

来源：评论

学校读者我要写书评

暂无评论

Rounding arrangements dynamically

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 1998年第2期8卷 157-178页

作者： Guibas, LJ Marimont, DH Stanford Univ Dept Comp Sci Stanford CA 94305 USA Xerox Corp Palo Alto Res Ctr Palo Alto CA 94304 USA

We describe a robust, dynamic algorithm to compute the arrangement of a set of line segments in the plane, and its implementation. The algorithm is robust because, following Greene(7) and Hobby,(11) it rounds the endpoints and intersections of all line segments to representable points, but in a way that is globally topologically consistent. The algorithm is dynamic because, following Mulmuley,(16) it uses a randomized hierarchy of vertical cell decompositions to make locating points, and inserting and deleting line segments,, efficient. Our algorithm is novel because it marries the robustness of the Greene and Hobby algorithms with Mulmuley's dynamic algorithm in a way that preserves the desirable properties of each.

关键词： arrangement vertical trapezoidal decomposition dynamic data structure randomized algorithm robustness rounding

来源：评论

学校读者我要写书评

暂无评论

Criticality and Covered Area Fraction in Confetti and Voronoi Percolation

引用

JOURNAL OF STATISTICAL PHYSICS 2022年第1期186卷 1-1页

作者： Ghosh, Partha Pratim Roy, Rahul Indian Stat Inst New Delhi India

Using the randomized algorithm method developed by Duminil-Copin et al. (Probab Theory Relat Fields 173(1-2):479-90, 2019), we exhibit sharp phase transition for the confetti percolation model. This provides an alternate proof, than that of Ahlberg et al. (Probab Theory Relat Fields 172(1-2):525-581, 2018), for the critical parameter for percolation in this model to be 1/2 when the radius of the underlying shapes for the distinct colours arise from the same distribution. In addition, we study the covered area fraction for this model, which is akin to the covered volume fraction in continuum percolation. Modulo a certain 'transitivity condition', this study allows us to calculate exact critical parameter for percolation when the underlying shapes for different colours may be of different sizes. Similar results are also obtained for the Poisson Voronoi percolation model when different coloured points have different growth speeds.

关键词： Confetti percolation Voronoi percolation randomized algorithm Boolean model Covered area fraction

来源：评论

学校读者我要写书评

暂无评论

ON THE COMPLEXITY OF COMPUTING OPTIMAL SOLUTIONS

引用

International Journal of Foundations of Computer Science 1991年第3期2卷 207-220页

作者： ZHI-ZHONG CHEN SEINOSUKE TODA Department of Computer Science and Information Mathematics University of Electro-Communications Chofugaoka 1–5–1 Chufo-shi Tokyo 182 Japan

We study the computational complexity of computing optimal solutions (the solutions themselves, not just their cost) for NP optimization problems where the costs of feasible solutions are bounded above by a polynomial in the length of their instances (we simply denote by NPOP such an NP optimization problem). It is of particular interest to find a computational structure (or equivalently, a complexity class) which. captures that complexity, if we consider the problems of computing optimal solutions for NPOP’s as a class of functions giving those optimal solutions. In this paper, we will observe that the class of functions computable in polynomial-time with one free evaluation of unbounded parallel queries to NP oracle sets, captures that complexity. We first show that for any NPOP Π, there exists a polynomial-time bounded randomized algorithm which, given an instance of Π, uses one free evaluation of parallel queries to an NP oracle set and outputs some optimal solution of the instance with very high probability. We then show that for several natural NPOP’s, any function giving those optimal solutions is at least as computationally hard as all functions in . To show the hardness results, we introduce a property of NPOP’s, called paddability , and we show a general result that if Π is a paddable NPOP and its associated decision problem is NP-hard, then all functions in are computable in polynomial-time with one free evaluation of an arbitrary function giving optimal solutions for instances of Π. The hardness results are applications of this general result. Among the NPOP’s, we include MAXIMUM CLIQUE, MINIMUM COLORING, LONGEST PATH, LONGEST CYCLE, 0–1 TRAVELING SALESPERSON, and 0–1 INTEGER PROGRAMMING.

关键词： Polynomial paddability truth-table reducibility randomized algorithm non-deterministic polynomial time optimization problem computational complexity theory

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：