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

2015 IEEE 35th International Conference on Distributed Computing Systems

作者： Kentros, Sotirios Kari, Chadi Kiayias, Aggelos Russell, Alexander Salem State Univ Dept Comp Sci Salem MA 01970 USA Univ Pacific Sch Engn & Comp Sci Stockton CA 95211 USA Univ Athens Dept Informat & Telecommun GR-15784 Athens Greece Univ Connecticut Comp Sci & Engn Dept Storrs CT 06269 USA

ISBN: (纸本)9781467372145

We present a randomized algorithm for asynchronous task allocation, also known as the write-all or do-all problem. Our algorithm has work complexity O(n + k(2) log(3) k) with high probability, where n the number of tasks and k the number of processes that participate in the computation. Our solution uses O(n) shared memory space that supports atomic test-and-set operations and with high probability each participating process uses O(k) internal memory space. This is the first adaptive solution for the write-all problem that has work n plus some additive term which depends only on the number of participating processes k and not the size of the problem n.

关键词： distributed computing write-all randomized algorithms task allocation asynchronous shared memory

来源：评论

学校读者我要写书评

暂无评论

Scalable audio separation with light Kernel Additive Modelling 40

Scalable audio separation with light Kernel Additive Modelli...

引用

40th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015

作者： Liutkus, Antoine Fitzgerald, Derry Rafii, Zafar Inria Speech Processing Team Villers-lès-Nancy France NIMBUS Centre Cork Institute of Technology Ireland Gracenote Media Technology Lab EmeryvilleCA United States

ISBN: (纸本)9781467369978

Recently, Kernel Additive Modelling (KAM) was proposed as a unified framework to achieve multichannel audio source separation. Its main feature is to use kernel models for locally describing the spectrograms of the sources. Such kernels can capture source features such as repetitivity, stability over time and/or frequency, self-similarity, etc. KAM notably subsumes many popular and effective methods from the state of the art, including REPET and harmonic/percussive separation with median filters. However, it also comes with an important drawback in its initial form: its memory usage badly scales with the number of sources. Indeed, KAM requires the storage of the full-resolution spectrogram for each source, which may become prohibitive for full-length tracks or many sources. In this paper, we show how it can be combined with a fast compression algorithm of its parameters to address the scalability issue, thus enabling its use on small platforms or mobile devices. © 2015 IEEE.

关键词： Kernel Additive Modelling randomized algorithms sound source separation

来源：评论

学校读者我要写书评

暂无评论

Computational and Statistical Advances in Testing and Learning

Computational and Statistical Advances in Testing and Learni...

引用

作者： Aaditya Kumar Ramdas Carnegie Mellon University

学位级别：博士

This thesis makes fundamental computational and statistical advances in testing and esti- mation, making critical progress in theory and application of classical statistical methods like classification, regression and hypothesis testing, and understanding the relationships between them. Our work connects multiple fields in often counter-intuitive and surprising ways, lead- ing to new theory, new algorithms, and new insights, and ultimately to a cross-fertilization of varied fields like optimization, statistics and machine learning. The first of three thrusts has to do with active learning, a form of sequential learning from feedback-driven queries that often has a provable statistical advantage over passive learning. We unify concepts from two seemingly different areas - active learning and stochastic first- order optimization. We use this unified view to develop new lower bounds for stochastic optimization using tools from active learning and new algorithms for active learning using ideas from optimization. We also study the effect of feature noise, or errors-in-variables, on the ability to actively learn. The second thrust deals with the development and analysis of new convex optimization algorithms for classification and regression problems. We provide geometrical and convex analytical insights into the role of the margin in margin-based classification, and develop new greedy primal-dual algorithms for non-linear classification. We also develop a unified proof for convergence rates of randomized algorithms for the ordinary least squares and ridge regression problems in a variety of settings, with the purpose of investigating which algorithm should be utilized in different settings. Lastly, we develop fast state-of-the-art numerically stable algorithms for an important univariate regression problem called trend filtering with a wide variety of practical extensions. The last thrust involves a series of practical and theoretical advances in nonparametric hypothesis

关键词： active learning convex optimization hypothesis testing computation-statistics tradeoffs sequential analysis stochastic oracles randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Iterative randomized robust linear regression

Iterative randomized robust linear regression

引用

IEEE International Conference on Acoustics, Speech and Signal Processing

作者： Y. Kopsinis S. Chouvardas S. Theodoridis Dept. of Inf. & Telecommun. Univ. of Athens Athens Greece

ISBN: (纸本)9781467369985

A promising approach when dealing with massive data sets is to apply randomized dimensionality reduction and then operate in lower dimensions. This paper deals with the randomized linear regression task in the case where the available data are sporadically corrupted. Instead of relying to minimization of norms, which are robust to outliers, an alternative route is taken. Building upon the observation that outliers can be detected, while operating in a low dimensional randomized projections produced embedding, a mechanism for iteratively detecting and excluding corrupted data is proposed. As a result, the linear regression is performed using conventional LS approximation, without the need to resort to linear programming-based l_1 norm minimization tasks.

关键词： randomized algorithms Robust Regression

来源：评论

学校读者我要写书评

暂无评论

randomized distributed decision

引用

DISTRIBUTED COMPUTING 2014年第6期27卷 419-434页

作者： Fraigniaud, Pierre Goeoes, Mika Korman, Amos Parter, Merav Peleg, David Univ Paris Diderot CNRS Paris France Univ Toronto Dept Comp Sci Toronto ON Canada Weizmann Inst Sci IL-76100 Rehovot Israel

The paper tackles the power of randomization in the context of local distributed computing by analyzing the ability to "boost" the success probability of deciding a distributed language using a Monte-Carlo algorithm. We prove that, in many cases, the ability to increase the success probability for deciding distributed languages is rather limited. This contrasts with the sequential computing setting where boosting can systematically be achieved by repeating the randomized execution.

关键词： Distributed local algorithms randomized algorithms Complexity classes

来源：评论

学校读者我要写书评

暂无评论

An efficient distributed randomized algorithm for solving large dense symmetric indefinite linear systems

引用

PARALLEL COMPUTING 2014年第7期40卷 213-223页

作者： Baboulin, Marc Becker, Dulceneia Bosilca, George Danalis, Anthony Dongarra, Jack Univ Paris 11 Rech Informat Lab Inria F-91405 Orsay France Univ Tennessee Innovat Comp Lab Knoxville TN USA

randomized algorithms are gaining ground in high-performance computing applications as they have the potential to outperform deterministic methods, while still providing accurate results. We propose a randomized solver for distributed multicore architectures to efficiently solve large dense symmetric indefinite linear systems that are encountered, for instance, in parameter estimation problems or electromagnetism simulations. The contribution of this paper is to propose efficient kernels for applying random butterfly transformations and a new distributed implementation combined with a runtime (PaRSEC) that automatically adjusts data structures, data mappings, and the scheduling as systems scale up. Both the parallel distributed solver and the supporting runtime environment are innovative. To our knowledge, the randomization approach associated with this solver has never been used in public domain software for symmetric indefinite systems. The underlying runtime framework allows seamless data mapping and task scheduling, mapping its capabilities to the underlying hardware features of heterogeneous distributed architectures. The performance of our software is similar to that obtained for symmetric positive definite systems, but requires only half the execution time and half the amount of data storage of a general dense solver. (C) 2013 Elsevier B.V. All rights reserved.

关键词： randomized algorithms Distributed linear algebra solvers Symmetric indefinite systems LDLT factorization PaRSEC runtime

来源：评论

学校读者我要写书评

暂无评论

PARCUBE: Sparse Parallelizable CANDECOMP-PARAFAC Tensor Decomposition

引用

ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA 2015年第1期10卷 3-3页

作者： Papalexakis, Evangelos E. Faloutsos, Christos Sidiropoulos, Nicholas D. Carnegie Mellon Univ Sch Comp Sci Pittsburgh PA 15213 USA Univ Minnesota Dept ECE Minneapolis MN 55455 USA

How can we efficiently decompose a tensor into sparse factors, when the data do not fit in memory? Tensor decompositions have gained a steadily increasing popularity in data-mining applications;however, the current state-of-art decomposition algorithms operate on main memory and do not scale to truly large datasets. In this work, we propose PARCUBE, a new and highly parallelizable method for speeding up tensor decompositions that is well suited to produce sparse approximations. Experiments with even moderately large data indicate over 90% sparser outputs and 14 times faster execution, with approximation error close to the current state of the art irrespective of computation and memory requirements. We provide theoretical guarantees for the algorithm's correctness and we experimentally validate our claims through extensive experiments, including four different real world datasets (ENRON, LBNL, FACEBOOK and NELL), demonstrating its effectiveness for data-mining practitioners. In particular, we are the first to analyze the very large NELL dataset using a sparse tensor decomposition, demonstrating that PARCUBE enables us to handle effectively and efficiently very large datasets. Finally, we make our highly scalable parallel implementation publicly available, enabling reproducibility of our work.

关键词： algorithms Performance Tensors PARAFAC decomposition sparsity sampling randomized algorithms parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Fitness levels with tail bounds for the analysis of randomized search heuristics

引用

INFORMATION PROCESSING LETTERS 2014年第1-2期114卷 38-41页

作者： Witt, Carsten Tech Univ Denmark DTU Compute DK-2800 Lyngby Denmark

The fitness-level method, also called the method of f-based partitions, is an intuitive and widely used technique for the running time analysis of randomized search heuristics. It was originally defined to prove upper and lower bounds on the expected running time. Recently, upper tail bounds were added to the technique;however, these tail bounds only apply to running times that are at least twice as large as the expectation. We remove this restriction and supplement the fitness-level method with sharp tail bounds, including lower tails. As an exemplary application, we prove that the running time of randomized local search on ONEMAX is sharply concentrated around n In n - 0.1159...n. (C) 2013 Elsevier B.V. All rights reserved.

关键词： randomized algorithms randomized search heuristics Running time analysis Fitness-level method Tail bounds

来源：评论

学校读者我要写书评

暂无评论

Algorithmic theory of free solvable groups: randomized computations

引用

JOURNAL OF ALGEBRA 2014年 407卷 178-200页

作者： Ushakov, Alexander Stevens Inst Technol Hoboken NJ 07030 USA

We design new deterministic and randomized algorithms for computational problems in free solvable groups. In particular, we prove that the word problem and the power problem can be solved in quasi-linear time and the conjugacy problem can be solved in quasi-quartic time by Monte Carlo type algorithms. (c) 2014 Elsevier Inc. All rights reserved.

关键词： Solvable groups Metabelian groups Word problem Cyclic subgroup membership Power problem Conjugacy problem randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Revisiting the Nyström method for improved large-scale machine learning

The Journal of Machine Learning Research

引用

The Journal of Machine Learning Research 2016年第1期17卷

作者： Kevin Murphy Bernhard Schölkopf Alex Gittens Michael W. Mahoney Google MPI for Intelligent Systems International Computer Science Institute and Department of Statistics University of California Berkeley Berkeley CA

We reconsider randomized algorithms for the low-rank approximation of symmetric positive semi-definite (SPSD) matrices such as Laplacian and kernel matrices that arise in data analysis and machine learning applications. Our main results consist of an empirical evaluation of the performance quality and running time of sampling and projection methods on a diverse suite of SPSD matrices. Our results highlight complementary aspects of sampling versus projection methods; they characterize the effects of common data preprocessing steps on the performance of these algorithms; and they point to important differences between uniform sampling and nonuniform sampling methods based on leverage scores. In addition, our empirical results illustrate that existing theory is so weak that it does not provide even a qualitative guide to practice. Thus, we complement our empirical results with a suite of worst-case theoretical bounds for both random sampling and random projection methods. These bounds are qualitatively superior to existing bounds--e.g., improved additive-error bounds for spectral and Frobenius norm error and relative-error bounds for trace norm error--and they point to future directions to make these algorithms useful in even larger-scale machine learning applications.

关键词： Nyström approximation kernel methods low-rank approximation numerical linear algebra randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：