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

A randomized Approach to Probabilistic Footprint Estimation of a Space Debris Uncontrolled Reentry

IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS 2017年第10期18卷 2657-2666页

作者： Falsone, Alessandro Prandini, Maria Politecn Milan Dipartimento Elettron Informaz & Bioingn I-20133 Milan Italy

This paper studies the problem of characterizing the region of the airspace that will be occupied by a space debris during an uncontrolled reentry (footprint), with the final goal of supporting the air traffic controllers in their task of guiding aircraft safely from their origin to their destination. Given the various sources of uncertainty affecting the debris dynamics, the reentry process is characterized probabilistically and the problem of determining the footprint is formulated in terms of a chance-constrained optimization program, which is solved via a simulation-based method. When observations of the debris initial position and radar measurements of the aircraft prior to the reentry event are available, nonlinear filtering techniques can be adopted and the posterior probability distribution of the debris position as well as of the wind field affecting the reentry process can be integrated in the chance-constraint formulation so as to obtain an enhanced estimate of the footprint. Simulation results show the efficacy of the approach.

关键词： randomized algorithms nonlinear filtering air traffic control uncontrolled debris reentry

来源：评论

学校读者我要写书评

暂无评论

On-line randomized call control revisited

引用

SIAM JOURNAL ON COMPUTING 2001年第1期31卷 86-112页

作者： Leonardi, S Marchetti-Spaccamela, A Presciutti, A Rosén, A Univ Roma La Sapienza Dipartimento Informat Sistemist I-00198 Rome Italy Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

We consider the problem of on-line call admission and routing on trees and meshes. Previous work gave randomized on-line algorithms for these problems and proved that they have optimal ( up to constant factors) competitive ratios. However, these algorithms can obtain very low profit with high probability. We investigate the question of devising for these problems on-line competitive algorithms that also guarantee a good solution with good probability. We give a new family of randomized algorithms with asymptotically optimal competitive ratios and good probability to get a profit close to the expectation. We complement these results by providing bounds on the probability of any optimally competitive randomized on-line algorithm for the problems we consider to get a profit close to the expectation. To the best of our knowledge, this is the rst study of the relationship between the tail distribution and the competitive ratio of randomized on-line benefit algorithms.

关键词： on-line algorithms competitive analysis randomized algorithms call admission control

来源：评论

学校读者我要写书评

暂无评论

randomized Receding Horizon Navigation

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2010年第11期55卷 2640-2644页

作者： Tanner, Herbert G. Piovesan, Jorge L. Univ Delaware Dept Mech Engn Newark DE 19716 USA Univ New Mexico K&A Wireless LLC Albuquerque NM 87112 USA

The note combines (weak) control Lyapunov function-based nonlinear receding horizon control, with randomized optimization. This approach is applied to the problem of robot navigation in the presence of state and input constraints. It is shown that under certain conditions, relaxing the definiteness requirements on the terminal cost function allows one to select control inputs through a Monte-Carlo optimization scheme in a way that preserves the stability and convergence properties of the closed loop system. While the particular randomized optimization scheme used here can be substituted for the nonlinear optimal control method of choice, the introduction of randomization in receding horizon optimization is anticipated to offer additional trade-offs between performance and computation speed compared to the fixed-overhead nonlinear optimal control strategies typically employed.

关键词： Model predictive control (MPC) randomized algorithms robot navigation

来源：评论

学校读者我要写书评

暂无评论

SOLVING THE SATISFIABILITY PROBLEM BY USING randomized APPROACH

引用

INFORMATION PROCESSING LETTERS 1992年第4期41卷 187-190页

作者： WU, LC TANG, CY NATL TSING HUA UNIV INST COMP SCIHSINCHU 30043TAIWAN

In this paper we propose a randomized algorithm which can solve the satisfiability problem with the probability of failure not exceeding epsilon in polynomial average time.

关键词： ANALYSIS OF algorithms DESIGN OF algorithms randomized algorithms SATISFIABILITY PROBLEM

来源：评论

学校读者我要写书评

暂无评论

Decoding by Sampling: A randomized Lattice Algorithm for Bounded Distance Decoding

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2011年第9期57卷 5933-5945页

作者： Liu, Shuiyin Ling, Cong Stehle, Damien Univ London Imperial Coll Sci Technol & Med Dept Elect & Elect Engn London SW7 2AZ England U Lyon CNRS Lab LIP ENS LyonINRIAUCBL F-69364 Lyon 07 France

Despite its reduced complexity, lattice reduction-aided decoding exhibits a widening gap to maximum-likelihood (ML) performance as the dimension increases. To improve its performance, this paper presents randomized lattice decoding based on Klein's sampling technique, which is a randomized version of Babai's nearest plane algorithm [i.e., successive interference cancelation (SIC)] and samples lattice points from a Gaussian-like distribution over the lattice. To find the closest lattice point, Klein's algorithm is used to sample some lattice points and the closest among those samples is chosen. Lattice reduction increases the probability of finding the closest lattice point, and only needs to be run once during preprocessing. Further, the sampling can operate very efficiently in parallel. The technical contribution of this paper is twofold: we analyze and optimize the decoding radius of sampling decoding resulting in better error performance than Klein's original algorithm, and propose a very efficient implementation of random rounding. Of particular interest is that a fixed gain in the decoding radius compared to Babai's decoding can be achieved at polynomial complexity. The proposed decoder is useful for moderate dimensions where sphere decoding becomes computationally intensive, while lattice reduction-aided decoding starts to suffer considerable loss. Simulation results demonstrate near-ML performance is achieved by a moderate number of samples, even if the dimension is as high as 32.

关键词： Bounded distance decoding lattice decoding lattice reduction randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Compressed randomized UTV Decompositions for Low-Rank Matrix Approximations

引用

IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING 2018年第6期12卷 1155-1169页

作者： Kaloorazi, Maboud F. de Lamare, Rodrigo C. Pontifical Catholic Univ Rio de Janeiro Ctr Telecommun Studies CETUC BR-22451000 Rio De Janeiro Brazil Univ York Dept Elect York YO10 5DD N Yorkshire England

Low-rankmatrix approximations play a fundamental role in numerical linear algebra and signal processing applications. This paper introduces a novel rank-revealing matrix decomposition algorithm termed compressed randomized UTV (CoR-UTV) decomposition along with a CoR-UTV variant aided by the power method technique. CoR-UTV is primarily developed to compute an approximation to a low-rank input matrix by making use of random sampling schemes. Given a large and dense matrix of size m x n with numerical rank k, where k << min{m, n}, CoRUTV requires a few passes over the data, and runs in O(mnk) floating-point operations. Furthermore, CoR-UTV can exploit modern computational platforms and, consequently, can be optimized for maximum efficiency. CoR-UTV is simple and accurate, and outperforms reported alternative methods in terms of efficiency and accuracy. Simulations with synthetic data as well as real data in image reconstruction and robust principal component analysis applications support our claims.

关键词： Matrix computations low-rank approximations UTV decomposition randomized algorithms dimension reduction matrix decomposition image reconstruction robust PCA

来源：评论

学校读者我要写书评

暂无评论

On randomized Approximation for Finding a Level Ideal of a Poset and the Generalized Median Stable Matchings

引用

MATHEMATICS OF OPERATIONS RESEARCH 2012年第2期37卷 356-371页

作者： Kijima, Shuji Nemoto, Toshio Kyushu Univ Grad Sch Informat Sci & Elect Engn Fukuoka 8190395 Japan Bunkyo Univ Grad Sch Informat & Commun Chigasaki Kanagawa 2538550 Japan

This study is concerned with finding a level ideal (LI) of a partially ordered set (poset). Given a finite poset P. the level of each element p is an element of P is defined as the number of ideals that do not include p, then the problem is to find the ith LI-the ideal consisting of elements whose levels are less than a given integer i. The concept of a level ideal is naturally derived from the generalized median stable matchings, introduced by Teo and Sethuraman [Teo, C. P., J. Sethuraman. 1998. The geometry of fractional stable matchings and its applications. Math. Oper Res. 23(4) 874-891] in the context of "fairness" of matchings in a stable marriage problem. Cheng [Cheng, C. T. 2010. Understanding the generalized median stable matchings. Algorithmica 58(1) 34-51] showed that finding the ith LI is #P-hard when i = Theta(N), where N is the total number of ideals of P. This paper shows that finding the ith LI is #P-hard even if i = Theta(N-1/c), where c is an arbitrary constant at least one. Meanwhile, we present a polynomial time exact algorithm when i = O((log N)(c')), where c' is an arbitrary positive constant. We also devise two randomized approximation schemes for the ideals of a poset, by using an oracle of an almost-uniform sampler.

关键词： randomized algorithms stable marriage order ideals #P-hard randomized approximation scheme (FPRAS)

来源：评论

学校读者我要写书评

暂无评论

A lower bound for integer multiplication on randomized ordered read-once branching programs

引用

INFORMATION AND COMPUTATION 2003年第1期186卷 78-89页

作者： Ablayev, F Karpinski, M Univ Bonn Inst Informat Dept Comp Sci DE-53117 Bonn Germany Max Planck Inst Math D-5300 Bonn Germany

We prove an exponential lower bound 2(Omega(n/log n)) on the size of any randomized ordered read-once branching program computing integer multiplication. Our proof depends on proving a new lower bound on Yao's randomized one-way communication complexity of certain Boolean functions. It generalizes to some other models of randomized branching programs. In contrast, we prove that testing integer multiplication, contrary even to a non-deterministic situation, can be computed by randomized ordered read-once branching program in polynomial size. It is also known that computing the latter problem with deterministic read-once branching programs is as hard as factoring integers. (C) 2003 Elsevier Science (USA). All rights reserved.

关键词： deterministic and randomized branching programs OBDD complexity lower bounds integer multiplication randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Adaptive randomized Dimension Reduction on Massive Data

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2017年第1期18卷 5134-5163页

作者： Darnell, Gregory Georgiev, Stoyan Mukherjee, Sayan Engelhardt, Barbara E. Princeton Univ Lewis Sigler Inst Princeton NJ 08544 USA Google Palo Alto CA 94043 USA Duke Univ Dept Stat Sci Durham NC 27708 USA Duke Univ Dept Math Durham NC 27708 USA Duke Univ Dept Comp Sci Durham NC 27708 USA Princeton Univ Dept Comp Sci Ctr Stat & Machine Learning Princeton NJ 08540 USA

The scalability of statistical estimators is of increasing importance in modern applications. One approach to implementing scalable algorithms is to compress data into a low dimensional latent space using dimension reduction methods. In this paper, we develop an approach for dimension reduction that exploits the assumption of low rank structure in high dimensional data to gain both computational and statistical advantages. We adapt recent randomized low-rank approximation algorithms to provide an efficient solution to principal component analysis (PCA), and we use this efficient solver to improve estimation in large-scale linear mixed models (LMM) for association mapping in statistical genomics. A key observation in this paper is that randomization serves a dual role, improving both computational and statistical performance by implicitly regularizing the covariance matrix estimate of the random effect in an LMM. These statistical and computational advantages are highlighted in our experiments on simulated data and large-scale genomic studies.

关键词： dimension reduction generalized eigendecompositon low-rank genomics linear mixed models supervised random projections randomized algorithms Krylov subspace methods

来源：评论

学校读者我要写书评

暂无评论

Distributed Sketching for randomized Optimization: Exact Characterization, Concentration, and Lower Bounds

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2023年第6期69卷 3850-3879页

作者： Bartan, Burak Pilanci, Mert Stanford Univ Dept Elect Engn Stanford CA 94305 USA

We consider distributed optimization methods for problems where forming the Hessian is computationally challenging and communication is a significant bottleneck. We leverage randomized sketches for reducing the problem dimensions as well as preserving privacy and improving straggler resilience in asynchronous distributed systems. We derive novel approximation guarantees for classical sketching methods and establish tight concentration results that serve as both upper and lower bounds on the error. We then extend our analysis to the accuracy of parameter averaging for distributed sketches. Furthermore, we develop unbiased parameter averaging methods for randomized second order optimization in regularized problems that employ sketching of the Hessian. Existing works do not take the bias of the estimators into consideration, which limits their application to massively parallel computation. We provide closed-form formulas for regularization parameters and step sizes that provably minimize the bias for sketched Newton directions. Additionally, we demonstrate the implications of our theoretical findings via large scale experiments on a serverless cloud computing platform.

关键词： Sketching distributed optimization randomized algorithms convex optimization regularized least squares second order optimization large scale problems differential privacy

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：