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

randomized selection in n + C + o(n) comparisons

INFORMATION PROCESSING LETTERS 2003年第3期88卷 95-100页

作者： Gerbessiotis, AV Siniolakis, CJ New Jersey Inst Technol CS Dept Newark NJ 07102 USA Amer Coll Greece Athens 15342 Greece

In this paper we present a randomized selection algorithm that with high probability 1 - 1/n(rho), for any constant p > 1 requires n + C + o(n) comparisons to determine the Cth order statistic of n keys thus matching a corresponding lower bound on the average number of comparisons required. Low order terms in the number of comparisons performed can also be reduced by extending the algorithm of Floyd and Rivest and analyzing its resulting performance more carefully. (C) 2003 Elsevier B.V. All rights reserved.

关键词： randomized algorithms selection

来源：评论

学校读者我要写书评

暂无评论

A note on randomized mutual search

引用

INFORMATION PROCESSING LETTERS 1999年第5-6期71卷 187-191页

作者： Lotker, Z Patt-Shamir, B Tel Aviv Univ Dept Elect Engn IL-69978 Tel Aviv Israel

In Mutual Search, recently introduced by Buhrman et al. (1998), static agents are searching for each other: each agent is assigned one of n locations, and the computations proceed by agents sending queries from their location to other locations, until one of the queries arrives at the other agent. The cost of a search is the number of queries made. The best known bounds for randomized protocols using private coins are (1) a protocol with worst-case expected cost of [(n + 1)/2], and (2) a lower bound of (n - 1)/8 queries for randomized protocols which make only a bounded number of coin-tosses. In this paper we strictly improve the lower bound, and present a new upper bound for shared random coins. Specifically, we first prove that the worst-case expected cost of any randomized protocol for two-agent mutual search is at least (Ir + 1)/3. This is an improvement both in terms of number of queries and in terms of applicability. We also give a randomized algorithm for mutual search with worst-case expected cost of (n + 1)/3. This algorithm works under the assumption that the agents share a random bit string. This bound shows that no better lower bound can be obtained using our technique. (C) 1999 Published by Elsevier Science B.V. All rights reserved.

关键词： algorithms two-agent mutual search randomized algorithms upper bound lower bound

来源：评论

学校读者我要写书评

暂无评论

randomized Algorithm to Determine the Eigenvector of a Stochastic Matrix with Application to the PageRank Problem

引用

AUTOMATION AND REMOTE CONTROL 2011年第2期72卷 342-352页

作者： Nazin, A. V. Polyak, B. T. Russian Acad Sci Trapeznikov Inst Control Sci Moscow Russia

Consideration was given to estimation of the eigenvector corresponding to the greatest eigenvalue of a stochastic matrix. There exist numerous applications of this problem arising at ranking the results of search, coordination of the multiagent system actions, network control, and data analysis. The standard technique for its solution comes to the power method with an additional regularization of the original matrix. A new randomized algorithm was proposed, and a uniform-over the entire class of the stochastic matrices of a given size-upper boundary of the convergence rate was validated. It is given by C root ln(N)/n, where C is an absolute constant, N is size, and n is the number of iterations. This boundary seems promising because ln(N) is smallish even for a very great size. The algorithm relies on the mirror descent method for the problems of convex stochastic optimization. Applicability of the method to the PageRank problem of ranking the Internet pages was discussed.

关键词： randomized algorithms Eigenvector Stochastic one-piece run

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

randomized Dimensionality Reduction for k-Means Clustering

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2015年第2期61卷 1045-1062页

作者： Boutsidis, Christos Zouzias, Anastasios Mahoney, Michael W. Drineas, Petros Yahoo Labs New York NY 10036 USA Univ Toronto Dept Comp Sci Toronto ON M5S 2J7 Canada IBM Res Lab CH-8803 Zurich Switzerland Univ Calif Berkeley Dept Stat Berkeley CA 94720 USA Rensselaer Polytech Inst Dept Comp Sci Troy NY 12180 USA

We study the topic of dimensionality reduction for k-means clustering. Dimensionality reduction encompasses the union of two approaches: 1) feature selection and 2) feature extraction. A feature selection-based algorithm for k-means clustering selects a small subset of the input features and then applies k-means clustering on the selected features. A feature extraction-based algorithm for k-means clustering constructs a small set of new artificial features and then applies k-means clustering on the constructed features. Despite the significance of k-means clustering as well as the wealth of heuristic methods addressing it, provably accurate feature selection methods for k-means clustering are not known. On the other hand, two provably accurate feature extraction methods for k-means clustering are known in the literature;one is based on random projections and the other is based on the singular value decomposition (SVD). This paper makes further progress toward a better understanding of dimensionality reduction for k-means clustering. Namely, we present the first provably accurate feature selection method for k-means clustering and, in addition, we present two feature extraction methods. The first feature extraction method is based on random projections and it improves upon the existing results in terms of time complexity and number of features needed to be extracted. The second feature extraction method is based on fast approximate SVD factorizations and it also improves upon the existing results in terms of time complexity. The proposed algorithms are randomized and provide constant-factor approximation guarantees with respect to the optimal k-means objective value.

关键词： Clustering dimensionality reduction randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

A randomized algorithm for nonlinear model structure selection

引用

AUTOMATICA 2015年 60卷 227-238页

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

The identification of polynomial Nonlinear Autoregressive [Moving Average] models with exogenous variables (NAR[MA]X) is typically carried out with incremental model building techniques that progressively select the terms to include in the model. The Model Structure Selection (MSS) turns out to be the hardest task of the identification process due to the difficulty of correctly evaluating the importance of a generic term. As a result, classical MSS methods sometimes yield unsatisfactory models, that are unreliable over long-range prediction horizons. The MSS problem is here recast into a probabilistic framework based on which a randomized algorithm for MSS is derived, denoted RaMSS. The method introduces a tentative probability distribution over models and progressively updates it by extracting useful information on the importance of each term from sampled model structures. The proposed method is validated over models with different characteristics by means of Monte Carlo simulations, which show its advantages over classical and competitor probabilistic MSS methods in terms of both reliability and computational efficiency. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： Model identification Nonlinear models Polynomial NARX models randomized algorithms Regressor selection Prediction error minimization methods

来源：评论

学校读者我要写书评

暂无评论

Fast randomized point location without preprocessing in two- and three-dimensional Delaunay triangulations

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 1999年第1-2期12卷 63-83页

作者： Mücke, EP Saias, I Zhu, B Univ Calif Los Alamos Natl Lab Los Alamos NM USA

This paper studies the point location problem in Delaunay triangulations without preprocessing and additional storage. The proposed procedure finds the query point by simply "walking through" the triangulation, after selecting a "good starting point" by random sampling. The analysis generalizes and extends a recent result for d = 2 dimensions by proving this procedure takes expected time close to O(n(1/(d+1))) for point location in Delaunay triangulations of n random points in d = 3 dimensions. Empirical results in both two and three dimensions show that this procedure is efficient in practice. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： computational geometry geometric computing randomized algorithms Delaunay triangulations point location three dimensional

来源：评论

学校读者我要写书评

暂无评论

A randomized NONMONOTONE BLOCK PROXIMAL GRADIENT METHOD FOR A CLASS OF STRUCTURED NONLINEAR PROGRAMMING

引用

SIAM JOURNAL ON NUMERICAL ANALYSIS 2017年第6期55卷 2930-2955页

作者： Lu, Zhaosong Xiao, Lin Simon Fraser Univ Dept Math Burnaby BC V5A 1S6 Canada Microsoft Res Machine Learning Grp One Microsoft Way Redmond WA 98052 USA

We propose a randomized nonmonotone block proximal gradient (RNBPG) method for minimizing the sum of a smooth (possibly nonconvex) function and a block-separable (possibly nonconvex nonsmooth) function. At each iteration, this method randomly picks a block according to any prescribed probability distribution and solves typically several associated proximal subproblems that usually have a closed-form solution, until a certain progress on objective value is achieved. In contrast to the usual randomized block coordinate descent method [P. Richtarik and M. Takac, Math. Program., 144 (2014), pp. 1-38;A. Patrascu and I. Necoara, J. Global Optim., 61 (2015), pp. 19-46], our method has a nonmonotone flavor and uses variable stepsizes that can partially utilize the local curvature information of the smooth component of objective function. We show that any accumulation point of the solution sequence of the method is a stationary point of the problem almost surely and the method is capable of finding an approximate stationary point with high probability. We also establish a sublinear rate of convergence for the method in terms of the minimal expected squared norm of certain proximal gradients over the iterations. When the problem under consideration is convex, we show that the expected objective values generated by RNBPG converge to the optimal value of the problem. Under some assumptions, we further establish a sublinear and linear rate of convergence on the expected objective values generated by a monotone version of RNBPG. Finally, we conduct some preliminary experiments to test the performance of RNBPG on the l(1)-regularized least-squares problem, a dual support vector machine problem in machine learning, the l(0)-regularized least-squares problem, and a regularized matrix completion model. The computational results demonstrate that our method substantially outperforms the randomized block coordinate descent method with fixed or variable stepsizes.

关键词： nonconvex composite optimization randomized algorithms block coordinate gradient method nonmonotone line search

来源：评论

学校读者我要写书评

暂无评论

ON THE OPTIMALITY OF randomized ALPHA-BETA SEARCH

引用

SIAM JOURNAL ON COMPUTING 1995年第1期24卷 138-147页

作者： ZHANG, YJ Southern Methodist Univ Dallas TX United States

It is shown that the expected number of leaves evaluated by randomized alpha-beta search for evaluating uniform game trees of degree d and height h is O((B-d)(h)), where B-d = d/2 + Ind + O(1). It was shown by Saks and Wigderson [Proceedings of 27th Annual Symposium on Foundations of Computer Science (1986), pp. 29-38] that the optimal branching factor of randomized algorithms for evaluating uniform trees of degree d is Bd = (d-1+root d(2)+14d+1)/4=d/2+O(1). As B-d/B*(d)=1+O(lnd/d), randomized alpha-beta search is asymptotically optimal for evaluating uniform game trees as the degree of tree increases.

关键词： GAME-TREE EVALUATION ALPHA-BETA SEARCH randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

AN IMPROVED ANALYSIS AND UNIFIED PERSPECTIVE ON DETERMINISTIC AND randomized LOW-RANK MATRIX APPROXIMATION

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2023年第2期44卷 559-591页

作者： Demmel, James Grigori, Laura Rusciano, Alexander Univ Calif Berkeley Dept Math Comp Sci Berkeley CA 94720 USA Univ Paris Sorbonne Univ Inria Lab Jacques Louis LionsCNRS F-75005 Paris France Univ Calif Berkeley Dept Math Berkeley CA 94709 USA

We introduce a Generalized LU Factorization (GLU) for low-rank matrix approx-imation. We relate this to past approaches and extensively analyze its approximation properties. The established deterministic guarantees are combined with sketching ensembles satisfying Johnson-Lindenstrauss properties to present complete bounds. Particularly good performance is shown for the subsampled randomized Hadamard transform (SRHT) ensemble. Moreover, the factorization is shown to unify and generalize many past algorithms, sometimes providing strictly better approx-imations. It also helps to explain the effect of sketching on the growth factor during Gaussian elimination.

关键词： low-rank approximation spectrum preserving kernel approximation randomized algorithms deterministic algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：