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

CUR matrix decompositions for improved data analysis

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA 2009年第3期106卷 697-702页

作者： Mahoney, Michael W. Drineas, Petros Stanford Univ Dept Math Stanford CA 94305 USA Rensselaer Polytech Inst Dept Comp Sci Troy NY 12180 USA

Principal components analysis and, more generally, the Singular Value Decomposition are fundamental data analysis tools that express a data matrix in terms of a sequence of orthogonal or uncorrelated vectors of decreasing importance. Unfortunately, being linear combinations of up to all the data points, these vectors are notoriously difficult to interpret in terms of the data and processes generating the data. In this article, we develop CUR matrix decompositions for improved data analysis. CUR decompositions are low-rank matrix decompositions that are explicitly expressed in terms of a small number of actual columns and/or actual rows of the data matrix. Because they are constructed from actual data elements, CUR decompositions are interpretable by practitioners of the field from which the data are drawn (to the extent that the original data are). We present an algorithm that preferentially chooses columns and rows that exhibit high "statistical leverage" and, thus, in a very precise statistical sense, exert a disproportionately large "influence" on the best low-rank fit of the data matrix. By selecting columns and rows in this manner, we obtain improved relative-error and constant-factor approximation guarantees in worst-case analysis, as opposed to the much coarser additive-error guarantees of prior work. In addition, since the construction involves computing quantities with a natural and widely studied statistical interpretation, we can leverage ideas from diagnostic regression analysis to employ these matrix decompositions for exploratory data analysis.

关键词： randomized algorithms singular value decomposition principal components analysis interpretation statistical leverage

来源：评论

学校读者我要写书评

暂无评论

Tell Me Who I Am: An Interactive Recommendation System

引用

THEORY OF COMPUTING SYSTEMS 2009年第2期45卷 261-279页

作者： Alon, Noga Awerbuch, Baruch Azar, Yossi Patt-Shamir, Boaz Tel Aviv Univ Sch Math IL-69978 Tel Aviv Israel Inst Adv Study Princeton NJ 08540 USA Johns Hopkins Univ Dept Comp Sci Baltimore MD 21218 USA Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel Tel Aviv Univ Sch Elect Engn IL-69978 Tel Aviv Israel Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel

We consider a model of recommendation systems, where each member from a given set of players has a binary preference to each element in a given set of objects: intuitively, each player either likes or dislikes each object. However, the players do not know their preferences. To find his preference of an object, a player may probe it, but each probe incurs unit cost. The goal of the players is to learn their complete preference vector (approximately) while incurring minimal cost. This is possible if many players have similar preference vectors: such a set of players with similar "taste" may split the cost of probing all objects among them, and share the results of their probes by posting them on a public billboard. The problem is that players do not know a priori whose taste is close to theirs. In this paper we present a distributed randomized peer-to-peer algorithm in which each player outputs a vector which is close to the best possible approximation of the player's real preference vector after a polylogarithmic number of rounds. The algorithm works under adversarial preferences. Previous algorithms either made severely limiting assumptions on the structure of the preference vectors, or had polynomial overhead.

关键词： Recommendation systems Collaborative filtering randomized algorithms Electronic commerce Probes Billboard

来源：评论

学校读者我要写书评

暂无评论

Neighbor Discovery in Wireless Networks and the Coupon Collector's Problem 09

Neighbor Discovery in Wireless Networks and the Coupon Colle...

引用

15th Annual ACM International Conference on Mobile Computing and Networking (MobiCom 2009)

作者： Vasudevan, Sudarshan Towsley, Don Goeckel, Dennis Khalili, Ramin Univ Massachusetts Amherst MA 01003 USA

ISBN: (纸本)9781605587028

Neighbor discovery is one of the first steps in the initialization of a wireless ad hoc network. In this paper, we design and analyze practical algorithms for neighbor discovery in wireless networks. We first consider an ALOHA-like neighbor discovery algorithm in a synchronous system, proposed in an earlier work. When nodes do not have a collision detection mechanism, we show that this algorithm reduces to the classical Coupon Collector's Problem. Consequently, we show that each node discovers all its n neighbors in an expected time equal to ne(ln n + c), for some constant c. When nodes have a collision detection mechanism, we propose an algorithm based on receiver status feedback which yields a Inn improvement over the ALOHA-like algorithm. Our algorithms do not require nodes to have any estimate of the number of neighbors. In particular, we show that not knowing n results in no more than a factor of two slow-down in the algorithm performance. In the absence of node synchronization, we develop asynchronous neighbor discovery algorithms that are only a factor of two slower than their synchronous counterparts. We show that our algorithms can achieve neighbor discovery despite allowing nodes to begin execution at different time instants. Furthermore, our algorithms allow each node to detect when to terminate the neighbor discovery phase.

关键词： Ad Hoc Networks Sensor Networks Initialization Neighbor Discovery randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

COMPLEXITY OF STOQUASTIC FRUSTRATION-FREE HAMILTONIANS

引用

SIAM JOURNAL ON COMPUTING 2009年第4期39卷 1462-1485页

作者： Bravyi, Sergey Terhal, Barbara IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA

We study several problems related to properties of nonnegative matrices that arise at the boundary between quantum and classical probabilistic computation. Our results are twofold. First, we identify a large class of quantum Hamiltonians describing systems of qubits for which the adiabatic evolution can be efficiently simulated on a classical probabilistic computer. These are stoquastic local Hamiltonians with a "frustration-free" ground-state. A Hamiltonian belongs to this class iff it can be represented as H = Sigma(a) H-a where (1) every term H-a acts nontrivially on a constant number of qubits, (2) every term H-a has real nonpositive off-diagonal matrix elements in the standard basis, and (3) the ground-state of H is a ground-state of every term H-a. Second, we generalize the Cook-Levin theorem proving NP-completeness of the satisfiability problem to the complexity class MA (Merlin-Arthur games)-a probabilistic analogue of NP. Specifically, we construct a quantum version of the k-SAT problem which we call "stoquastic k-SAT" such that stoquastic k-SAT is contained in MA for any constant k, and any promise problem in MA is Karp-reducible to stoquastic 6-SAT. This result provides the first nontrivial example of a MA-complete promise problem.

关键词： adiabatic quantum computing nonnegative matrices randomized algorithms Merlin-Arthur games

来源：评论

学校读者我要写书评

暂无评论

Scheduling on Unrelated Machines under Tree-Like Precedence Constraints

Scheduling on Unrelated Machines under Tree-Like Precedence ...

引用

8th International Workshop on Approximation algorithms for Combinatorial Optimization Problems/9th International Workshop on Randomization and Computation

作者： Kumar, V. S. Anil Marathe, Madhav V. Parthasarathy, Srinivasan Srinivasan, Aravind Virginia Tech Virginia Bioinformat Inst Blacksburg VA 24061 USA IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA Univ Maryland Dept Comp Sci College Pk MD 20742 USA Univ Maryland Inst Adv Comp Studies College Pk MD 20742 USA Virginia Tech Dept Comp Sci Blacksburg VA 24061 USA

We present polylogarithmic approximations for the R vertical bar prec vertical bar C-max and R vertical bar prec vertical bar Sigma(j) w(j)C(j) problems, when the precedence constraints are "treelike"-i.e., when the undirected graph underlying the precedences is a forest. These are the first non-trivial generalizations of the job shop scheduling problem to scheduling with precedence constraints that are not just chains. These are also the first non-trivial results for the weighted completion time objective on unrelated machines with precedence constraints of any kind. We obtain improved bounds for the weighted completion time and flow time for the case of chains with restricted assignment-this generalizes the job shop problem to these objective functions. We use the same lower bound of "congestion + dilation", as in other job shop scheduling approaches (e.g. Shmoys, Stein and Wein, SIAM J. Comput. 23, 617-632, 1994). The first step in our algorithm for the R vertical bar prec vertical bar C-max problem with treelike precedences involves using the algorithm of Lenstra, Shmoys and Tardos to obtain a processor assignment with the congestion + dilation value within a constant factor of the optimal. We then show how to generalize the random-delays technique of Leighton, Maggs and Rao to the case of trees. For the special case of chains, we show a dependent rounding technique which leads to a bicriteria approximation algorithm for minimizing the flow time, a notoriously hard objective function.

关键词： Precedence-constrained scheduling Job-shop scheduling Approximation algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Coordinated Three-Dimensional Robotic Self-Assembly

Coordinated Three-Dimensional Robotic Self-Assembly

引用

IEEE International Conference on Robotics and Biomimetics (ROBIO)

作者： Kelly, Jonathan Zhang, Hong Univ Southern Calif Dept Comp Sci Los Angeles CA 90089 USA Univ Alberta Dept Comp Sci Edmonton AB T6G 2E1 Canada

ISBN: (纸本)9781424426782

Nature has demonstrated that geometrically interesting and functionally useful structures can be built in an entirely distributed fashion. We present a biologically-inspired model and several algorithms for three-dimensional self-assembly, suitable for implementation by very simple reactive robots. The robots, which we call assembly components, have limited local sensing capabilities and operate without centralized control. We consider the problem of maintaining coordination of the assembly process over time, and introduce the concept of an assembly ordering to describe constraints on the sequence in which components may attach to a growing structure. We prove the sufficient properties of such an ordering to guarantee production of a desired end result. The set of ordering constraints can be expressed as a directed acyclic graph;we develop a graph algorithm that is able to generate ordering constraints for a wide variety of structures. We then give a procedure for encoding the graph in a set of local assembly rules. Finally, we show that our previous results for the optimization of rule sets for two-dimensional structures can be readily extended to three dimensions.

关键词： Self-assembly multi-robot coordination graph theory optimization randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

An Improved Algorithm for Online Unit Clustering

引用

13th Annual International Conference on Computing and Combinatorics (COCOON 2007)

作者： Zarrabi-Zadeh, Hamid Chan, Timothy M. Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada

ISBN: (纸本)9783540735441

We revisit the online unit clustering problem in one dimension which we recently introduced at WAOA'06: given a sequence of n points on the line, the objective is to partition the points into a minimum number of subsets, each enclosable by a unit interval. We present a new randomized online algorithm that achieves expected competitive ratio 11/6 against oblivious adversaries, improving the previous ratio of 15/8. This immediately leads to improved upper bounds for the problem in two and higher dimensions as well.

关键词： Online algorithms randomized algorithms Unit clustering

来源：评论

学校读者我要写书评

暂无评论

A Stable Random-Contact Algorithm for Peer-to-Peer File Sharing

A Stable Random-Contact Algorithm for Peer-to-Peer File Shar...

引用

4th International Workshop on Self-Organizing Systems (IWSOS 2009)

作者： Reittu, Hannu VTT Tech Res Ctr Finland Espoo Finland

ISBN: (纸本)9783642108648

We consider a Bit Torrent type file sharing algorithm with randomized chunk copying process. The system functions in completely distributed way without any 'Tracker', just relying on randomness. In such case the stability becomes an issue. It may happen, say, that some chunk becomes rare. This problem can persist and cause accumulation of peers in the system;resulting in unstable system. The considered algorithms result in processes similar to urn-processes. The rare chunk phenomenon corresponds to Polya-urn type process, where common chunks are favored. However, some urn-processes like the Friedman-urn can provide good balance by favoring rare chunks in copying process. Recently, we showed that an algorithm based on Friedman-urn is efficient in two chunk case. We generalize tins algorithm for the more realistic case of many chunks. It shows good performance in terms of balance of chunks in an open system with constant flow of incoming peers. Further, the system is able to cope with instances like 'flash crowd', with large burst of incoming peers. The open system can also quickly reach equilibrium after an initial imbalance, when the system starts from a state with one rare chunk. We constructed a simplified model, assuming a good balance of chunks, and get results surprisingly close to simulations for Friedman-urn based random process.

关键词： file-sharing urn-models randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

An experimental study of distributed robot coordination

An experimental study of distributed robot coordination

引用

9th International Conference on Intelligent Autonomous Systems (IAS-9)

作者： Carpin, Stefano Pagello, Enrico Univ Calif Sch Engn Merced CA 95344 USA Univ Padua Dept Informat Engn I-35100 Padua Italy

ISBN: (纸本)1586035959

Coordinating the path of multiple robots along assigned paths is a computationally hard problem with great potential for applications. We here provide a detailed experimental study of a randomized algorithm for scheduling priorities that we have developed, and also compare it with exact and approximated solutions. It turns out that for problems of reasonable size our algorithm exhibits an appealing compromise between speed and quality. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Multi-robot systems Intelligent mobility randomized algorithms Motion planning

来源：评论

学校读者我要写书评

暂无评论

Testing embeddability between metric spaces

引用

International Journal of Foundations of Computer Science 2009年第2期20卷 313-329页

作者： Chang, Ching-Lueh Lyuu, Yuh-Dauh Ti, Yen-Wu Dept. Computer Science Information and Engineering National Taiwan University Taipei 106 Roosevelt Road Taiwan Dept. Computer Science Information and Engineering National Taiwan University Taipei 106 Taiwan

Let L 0 be real numbers, (M, d) be a finite metric space and (N, ρ) be a metric space. A query to a metric space consists of a pair of points and asks for the distance between these points. We study the number of qu... 详细信息

Let L < 1, ε > 0 be real numbers, (M, d) be a finite metric space and (N, ρ) be a metric space. A query to a metric space consists of a pair of points and asks for the distance between these points. We study the number of queries to metric spaces (M, d) and (N, ρ) needed to decide whether (M, d) is L-bilipschitz embeddable into (N, ρ) or ε-far from being L-bilipschitz embeddable into N, ρ). When (M, d) is ε-far from being L-bilipschitz embeddable into (N, ρ), we allow an o(1) probability of error (i.e., returning the wrong answer "L-bilipschitz embeddable"). However, no error is allowed when (M, d) is L-bilipschitz embeddable into (N, ρ). That is, algorithms with only one-sided errors are studied in this paper. When |M| ≤ |N| are both finite, we give an upper bound of $O(√ln |N|}{ε |M|}}\, (|M|2+|N|2))$ on the number of queries for determining with one-sided error whether (M, d) is L-bilipschitz embeddable into (N, ρ) or ε-far from being L-bilipschitz embeddable into (N, ρ). For the special case of finite |M| = |N|, the above upper bound evaluates to $O(|N|{3/2} {{{\ln |N|} \over \epsilon }} )$. We also prove a lower bound of Ω(|N|^3/2) for the special case when |M| = |N| are finite and L = 1, which coincides with testing isometry between finite metric spaces. For finite |M| = |N|, the upper and lower bounds thus match up to a multiplicative factor of at most $√ln |N|}{ε}}$, which depends only sublogarithmically in |N|. We also investigate the case when (N, ρ) is not necessarily finite. Our results are based on techniques developed in an earlier work on testing graph isomorphism. © 2009 World Scientific Publishing Company.

关键词： Graph isomorphism L-bilipschitz embed-dable Metric space Property testing Query complexity randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：