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

IEEE Annual Conference on Decision and Control

作者： Dmitry Krivokon Alexander Vakhitov Faculty of Mathematics and Mechanics St. Petersburg State University 198504 Universitetskii pr. 28 St. Petersburg Russia

ISBN: (纸本)9781467360890

Stochastic approximation algorithms (for example SPSA) provide a way to solve optimization problems in the presence of arbitrary but bounded disturbances. In this paper a problem of position estimation for a moving point using monocular projective observations is considered. We add random perturbations to camera position to produce an algorithm which makes estimates of point position demanding only that the point's velocity is bounded in time. This is superior to the methods currently available in the computer vision field which all consider very restricted cases of point movement (constant, movement in plane). We prove theoretical convergence of estimates and provide numerical simulation for the algorithm.

关键词： randomized algorithms Cameras Visual Fields position estimation Approximation algorithms Moving algorithms Arbitrary Bounded numerical simulation

来源：评论

学校读者我要写书评

暂无评论

Distributed matrix completion and robust factorization

The Journal of Machine Learning Research

引用

The Journal of Machine Learning Research 2015年第1期16卷

作者： Lester Mackey Ameet Talwalkar Michael I. Jordan Department of Statistics Stanford University Stanford CA Computer Science Department University of California Los Angeles Los Angeles CA Department of Electrical Engineering and Computer Science and Department of Statistics University of California Berkeley Berkeley CA

If learning methods are to scale to the massive sizes of modern data sets, it is essential for the field of machine learning to embrace parallel and distributed computing. Inspired by the recent development of matrix factorization methods with rich theory but poor computational complexity and by the relative ease of mapping matrices onto distributed architectures, we introduce a scalable divide-and-conquer framework for noisy matrix factorization. We present a thorough theoretical analysis of this framework in which we characterize the statistical errors introduced by the "divide" step and control their magnitude in the "conquer" step, so that the overall algorithm enjoys high-probability estimation guarantees comparable to those of its base algorithm. We also present experiments in collaborative filtering and video background modeling that demonstrate the near-linear to superlinear speed-ups attainable with this approach.

关键词： collaborative filtering divide-and-conquer matrix completion matrix factorization parallel and distributed algorithms randomized algorithms robust matrix factorization video surveillance

来源：评论

学校读者我要写书评

暂无评论

Inexactness and a future of computing

引用

PHILOSOPHICAL TRANSACTIONS OF THE ROYAL SOCIETY A-MATHEMATICAL PHYSICAL AND ENGINEERING SCIENCES 2014年第2018期372卷 5-5页

作者： Palem, Krishna V. Rice Univ Dept Comp Sci & ECE Houston TX 77005 USA

As pressures, notably from energy consumption, start impeding the growth and scale of computing systems, inevitably, designers and users are increasingly considering the prospect of trading accuracy or exactness. This paper is a perspective on the progress in embracing this somewhat unusual philosophy of innovating computing systems that are designed to be inexact or approximate, in the interests of realizing extreme efficiencies. With our own experience in designing inexact physical systems including hardware as a backdrop, we speculate on the rich potential for considering inexactness as a broad emerging theme if not an entire domain for investigation for exciting research and innovation. If this emerging trend to pursuing inexactness persists and grows, then we anticipate an increasing need to consider system co-design where application domain characteristics and technology features interplay in an active manner. A noteworthy early example of this approach is our own excursion into tailoring and hence co-designing floating point arithmetic units guided by the needs of stochastic climate models. This approach requires a unified effort between software and hardware designers that does away with the normal clean abstraction layers between the two.

关键词： approximation algorithms heuristics inexact computing information theory probabilistic CMOS randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

randomized EXTENDED KACZMARZ FOR SOLVING LEAST SQUARES

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2013年第2期34卷 773-793页

作者： Zouzias, Anastasios Freris, Nikolaos M. Univ Toronto Dept Comp Sci Toronto ON Canada Ecole Polytech Fed Lausanne Sch Comp & Commun Sci IC CH-1015 Lausanne Switzerland

We present a randomized iterative algorithm that exponentially converges in the mean square to the minimum l(2)-norm least squares solution of a given linear system of equations. The expected number of arithmetic operations required to obtain an estimate of given accuracy is proportional to the squared condition number of the system multiplied by the number of nonzero entries of the input matrix. The proposed algorithm is an extension of the randomized Kaczmarz method that was analyzed by Strohmer and Vershynin.

关键词： linear least squares minimum-length solution sparse matrix overdetermined system underdetermined system iterative method random sampling LAPACK randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Real-Time Streaming String-Matching

引用

ACM TRANSACTIONS ON algorithms 2014年第4期10卷 22-22页

作者： Breslauer, Dany Galil, Zvi Univ Haifa Caesarea Rothchild Inst Interdisciplinary Applica IL-31999 Haifa Israel Georgia Inst Technol Coll Comp Atlanta GA 30332 USA

This article presents a real-time randomized streaming string-matching algorithm that uses O(log m) space. The algorithm only makes one-sided small probability false-positive errors, possibly reporting phantom occurre... 详细信息

关键词： algorithms Theory String matching streaming algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Complexity of solving nonlinear equations in the deterministic, randomized and quantum settings

引用

APPLIED MATHEMATICS AND COMPUTATION 2013年 224卷 652-662页

作者： Gocwin, Maciej Kacewicz, Boleslaw AGH Univ Sci & Technol Fac Appl Math PL-30059 Krakow Poland

We consider the root finding of a real-valued function f defined on the d-dimensional unit cube. We assume that f has r continuous partial derivatives, with all partial derivatives of order r being Holder functions with the exponent rho. We study the epsilon-complexity of this problem in three settings: deterministic, randomized and quantum. It is known that with the root error criterion the deterministic epsilon-complexity is infinite, i.e., the problem is unsolvable. We show that the same holds in the randomized and quantum settings. Under the residual error criterion, we show that the deterministic and randomized epsilon-complexity is of order epsilon(-d/(r+rho)). In the quantum setting, the epsilon-complexity is shown to be of order epsilon(-d/(2(r+rho))). This means that a quadratic speed-up is achieved on a quantum computer. (C) 2013 Elsevier Inc. All rights reserved.

关键词： Nonlinear equations Deterministic algorithms randomized algorithms Quantum algorithms Optimality Complexity

来源：评论

学校读者我要写书评

暂无评论

Distributed Selfish Load Balancing on Networks

引用

ACM TRANSACTIONS ON algorithms 2014年第1期11卷 2-2页

作者： Berenbrink, Petra Hoefer, Martin Sauerwald, Thomas Simon Fraser Univ Dept Comp Sci Burnaby BC V5A 1S6 Canada Max Planck Inst Informat D-66123 Saarbrucken Germany Univ Cambridge Comp Lab Cambridge CB3 0FD England

We study distributed load balancing in networks with selfish agents. In the simplest model considered here, there are n identical machines represented by vertices in a network and m >> n selfish agents that unilaterally decide to move from one vertex to another if this improves their experienced load. We present several protocols for concurrent migration that satisfy desirable properties such as being based only on local information and computation and the absence of global coordination or cooperation of agents. Our main contribution is to show rapid convergence of the resulting migration process to states that satisfy different stability or balance criteria. In particular, the convergence time to a Nash equilibrium is only logarithmic in m and polynomial in n, where the polynomial depends on the graph structure. In addition, we show reduced convergence times to approximate Nash equilibria. Finally, we extend our results to networks of machines with different speeds or to agents that have different weights and show similar results for convergence to approximate and exact Nash equilibria.

关键词： Distributed computing randomized algorithms load balancing algorithmic game theory

来源：评论

学校读者我要写书评

暂无评论

New Formulations for Choice Network Revenue Management

引用

INFORMS JOURNAL ON COMPUTING 2014年第2期26卷 401-413页

作者： Talluri, Kalyan ICREA Barcelona 08005 Spain Univ Pompeu Fabra Barcelona 08005 Spain

Models incorporating more realistic models of customer behavior, as customers choosing from an offer set, have recently become popular in assortment optimization and revenue management. The dynamic program for these models is intractable and approximated by a deterministic linear program called the choice deterministic linear program (CDLP), which has an exponential number of columns. Column generation has been proposed but finding an entering column is NP-hard when segment consideration sets overlap. In this paper we propose a new approach called segment-based deterministic concave program (SDCP) based on segments and their consideration sets. SDCP is a relaxation of CDLP and hence forms a looser upper bound on the dynamic program, but coincides with CDLP for the case of nonoverlapping segments. If the number of elements in a consideration set for a segment is not very large, SDCP can be applied to any discrete-choice model of consumer behavior. We tighten the SDCP bound by (i) simulations, called the randomized concave programming method, and (ii) by adding cuts to a recent compact formulation (SBLP) of the problem for a latent multinomial-choice model (MNL) of demand. This latter approach turns out to be very effective, essentially obtaining CDLP value, even for overlapping segments. By formulating the problem as a separation problem, we give insight into why CDLP is easy for the MNL with nonoverlapping consideration sets and why generalizations of MNL pose difficulties. Numerical conclusions that we derive from the present paper are the following: (a) The randomized linear programming approach that obtains significant tightening of the linear program upper bound under an older independent-class model seems to have relatively little effect for the choice case;(b) for the MNL choice model, the SBLP+ formulation we give here for overlapping segments is very fast and is potentially scalable to industrial-size problems.

关键词： assortment optimization randomized algorithms network revenue management

来源：评论

学校读者我要写书评

暂无评论

SeeSite: Characterizing Relationships between Splice Junctions and Splicing Enhancers

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2014年第4期11卷 648-656页

作者： Lo, Christine Kakaradov, Boyko Lokshtanov, Daniel Boucher, Christina Univ Calif San Diego La Jolla CA 92093 USA Univ Calif San Diego Bioinformat Grad Program La Jolla CA 92093 USA Colorado State Univ Dept Comp Sci Ft Collins CO 80523 USA

RNA splicing is a cellular process driven by the interaction between numerous regulatory sequences and binding sites, however, such interactions have been primarily explored by laboratory methods since computational tools largely ignore the relationship between different splicing elements. Current computational methods identify either splice sites or other regulatory sequences, such as enhancers and silencers. We present a novel approach for characterizing co-occurring relationships between splice site motifs and splicing enhancers. Our approach relies on an efficient algorithm for approximately solving Consensus Sequence with Outliers, an NP-complete string clustering problem. In particular, we give an algorithm for this problem that outputs near-optimal solutions in polynomial time. To our knowledge, this is the first formulation and computational attempt for detecting co-occurring sequence elements in RNA sequence data. Further, we demonstrate that SeeSite is capable of showing that certain ESEs are preferentially associated with weaker splice sites, and that there exists a co-occurrence relationship with splice site motifs.

关键词： RNA splicing exon splicing enhansers randomized algorithms PTAS EPTAS

来源：评论

学校读者我要写书评

暂无评论

randomized SOLUTIONS TO CONVEX PROGRAMS WITH MULTIPLE CHANCE CONSTRAINTS

引用

SIAM JOURNAL ON OPTIMIZATION 2013年第4期23卷 2479-2501页

作者： Schildbach, Georg Fagiano, Lorenzo Morari, Manfred Swiss Fed Inst Technol Automat Control Lab Zurich Switzerland Univ Calif Santa Barbara Dept Mech Engn Santa Barbara CA 93106 USA

The scenario-based optimization approach ("scenario approach") provides an intuitive way of approximating the solution to chance-constrained optimization programs, based on finding the optimal solution under a finite number of sampled outcomes of the uncertainty ("scenarios"). A key merit of this approach is that it neither requires explicit knowledge of the uncertainty set, as in robust optimization, nor of its probability distribution, as in stochastic optimization. The scenario approach is also computationally efficient because it only requires the solution to a convex optimization program, even if the original chance-constrained problem is nonconvex. Recent research has obtained a rigorous foundation for the scenario approach, by establishing a direct link between the number of scenarios and bounds on the constraint violation probability. These bounds are tight in the general case of an uncertain optimization problem with a single chance constraint. This paper shows that the bounds can be improved in situations where the chance constraints have a limited "support rank," meaning that they leave a linear subspace unconstrained. Moreover, it shows that also a combination of multiple chance constraints, each with individual probability level, is admissible. As a consequence of these results, the number of scenarios can be reduced from that prescribed by the existing theory for problems with the indicated structural property. This leads to an improvement in the objective value and a reduction in the computational complexity of the scenario approach. The proposed extensions have many practical applications, in particular, high-dimensional problems such as multistage uncertain decision problems or design problems of large-scale systems.

关键词： uncertain optimization chance constraints randomized algorithms convex optimization scenario approach multistage decision problems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：