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

Finding Structure with Randomness: Probabilistic algorithms for Constructing Approximate Matrix Decompositions

SIAM REVIEW 2011年第2期53卷 217-288页

作者： Halko, N. Martinsson, P. G. Tropp, J. A. Univ Colorado Dept Appl Math Boulder CO 80309 USA CALTECH Pasadena CA 91125 USA

Low-rank matrix approximations, such as the truncated singular value decomposition and the rank-revealing QR decomposition, play a central role in data analysis and scientific computing. This work surveys and extends recent research which demonstrates that randomization offers a powerful tool for performing low-rank matrix approximation. These techniques exploit modern computational architectures more fully than classical methods and open the possibility of dealing with truly massive data sets. This paper presents a modular framework for constructing randomized algorithms that compute partial matrix decompositions. These methods use random sampling to identify a subspace that captures most of the action of a matrix. The input matrix is then compressed-either explicitly or implicitly-to this subspace, and the reduced matrix is manipulated deterministically to obtain the desired low-rank factorization. In many cases, this approach beats its classical competitors in terms of accuracy, robustness, and/or speed. These claims are supported by extensive numerical experiments and a detailed error analysis. The specific benefits of randomized techniques depend on the computational environment. Consider the model problem of finding the k dominant components of the singular value decomposition of an m x n matrix. (i) For a dense input matrix, randomized algorithms require O(mnlog(k)) floating-point operations (flops) in contrast to O(mnk) for classical algorithms. (ii) For a sparse input matrix, the flop count matches classical Krylov subspace methods, but the randomized approach is more robust and can easily be reorganized to exploit multiprocessor architectures. (iii) For a matrix that is too large to fit in fast memory, the randomized techniques require only a constant number of passes over the data, as opposed to O(k) passes for classical algorithms. In fact, it is sometimes possible to perform matrix approximation with a single pass over the data.

关键词： dimension reduction eigenvalue decomposition interpolative decomposition Johnson-Lindenstrauss lemma matrix approximation parallel algorithm pass-efficient algorithm principal component analysis randomized algorithm random matrix rank-revealing QR factorization singular value decomposition streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

A Cloud-Based Parallel Space-Saving algorithm for Big Networking Data

引用

IEEE ACCESS 2018年 6卷 45886-45898页

作者： He, Dazhong Yang, Yang Liu, Jun Beijing Univ Posts & Telecommun Ctr Data Sci Beijing 100876 Peoples R China Beijing Univ Posts & Telecommun Sch Informat & Commun Engn Beijing 100876 Peoples R China Beijing Univ Posts & Telecommun Beijing Lab Adv Informat Networks Beijing 100876 Peoples R China Beijing Univ Posts & Telecommun Beijing Key Lab Network Syst Architecture & Conve Beijing 100876 Peoples R China

As the network continues to evolve, completely analyzing the traffic requires immeasurable resources. In situations of processing enormous streaming data, the most significant k items (Top-k) are more interesting, and some streaming algorithms are deployed due to relatively limited memory and also limited processing time per item. Space-saving is such one of the most popular algorithms for computation of frequent and Top-k elements in data streams. In this paper, this algorithm is implemented in the cloud for analyzing big networking data, and an empirical formula of the counter number is derived for efficiently maintaining Top-k items. Meanwhile, easily understandable proof manner is presented to prove the merging ability of Space-saving algorithm, and some experiments are conducted to affirm the effectiveness of the algorithm.

关键词： Network traffic Top-k streaming algorithm parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

A general framework of hierarchical clustering and its applications

引用

INFORMATION SCIENCES 2014年 272卷 29-48页

作者： Cai, Ruichu Zhang, Zhenjie Tung, Anthony K. H. Dai, Chenyun Hao, Zhifeng Guangdong Univ Technol Fac Comp Sci Guangzhou Guangdong Peoples R China Illinois Singapore Pte Adv Digital Sci Ctr Singapore Singapore Natl Univ Singapore Sch Comp Singapore 117548 Singapore Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

Hierarchical clustering problem is a traditional topic in computer science, which aims to discover a consistent hierarchy of clusters with different granularities. One of the most important open questions on hierarchical clustering is the identification of the meaningful clustering levels in the hierarchical structure. In this paper, we answer this question from algorithmic point of view. In particular, we derive a quantitative analysis on the impact of the low-level clustering costs on high level clusters, when agglomerative algorithms are run to construct the hierarchy. This analysis enables us to find meaningful clustering levels, which are independent of the clusters hierarchically beneath it. We thus propose a general agglomerative hierarchical clustering framework, which automatically constructs meaningful clustering levels. This framework is proven to be generally applicable to any k-clustering problem in any a-relaxed metric space, in which strict triangle inequality is relaxed within some constant factor a. To fully utilize the hierarchical clustering framework, we conduct some case studies on k-median and k-means clustering problems, in both of which our framework achieves better approximation factor than the state-of-the-art methods. We also extend our framework to handle the data stream clustering problem, which allows only one scan on the whole data set. By incorporating our framework into Guha's data stream clustering algorithm, the clustering quality is greatly enhanced with only small extra computation cost incurred. The extensive experiments show that our proposal is superior to the distance based agglomerative hierarchical clustering and data stream clustering algorithms on a variety of data sets. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Clustering Hierarchical k-Means k-Median streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

Computing The Maximum Exponent in a Stream

引用

algorithmICA 2022年第3期84卷 742-756页

作者： Merkurev, Oleg Shur, Arseny M. Ural Fed Univ Ekaterinburg Russia

We consider the streaming version of the following problem: given an input string s of length n, find the maximum exponent of a substring of s. We prove that any algorithm deciding, w.h.p., whether a string contains a square, uses memory of size Omega(n), and thus does not satisfy the limitations of the streaming model. Thus the considered problem has no exact solution in the streaming model. Our main result is a Monte Carlo algorithm which computes the maximum exponent up to an additive errors epsilon < 1 /2: it outputs a number a such that s has a substring of exponent alpha but no substrings of exponent alpha + epsilon or higher. The algorithm uses O(log(2)n/epsilon) words of memory and performs O(log n) operations, including dictionary operations, per input symbol.

关键词： Stringology streaming algorithm Periodic string Exponent Gapped repeat

来源：评论

学校读者我要写书评

暂无评论

Random indexing of multidimensional data

引用

KNOWLEDGE AND INFORMATION SYSTEMS 2017年第1期52卷 267-290页

作者： Sandin, Fredrik Emruli, Blerim Sahlgren, Magnus Lulea Univ Technol EISLAB S-97187 Lulea Sweden SICS Swedish ICT S-72213 Vasteras Sweden SICS Swedish ICT S-16429 Kista Sweden

Random indexing (RI) is a lightweight dimension reduction method, which is used, for example, to approximate vector semantic relationships in online natural language processing systems. Here we generalise RI to multidimensional arrays and therefore enable approximation of higher-order statistical relationships in data. The generalised method is a sparse implementation of random projections, which is the theoretical basis also for ordinary RI and other randomisation approaches to dimensionality reduction and data representation. We present numerical experiments which demonstrate that a multidimensional generalisation of RI is feasible, including comparisons with ordinary RI and principal component analysis. The RI method is well suited for online processing of data streams because relationship weights can be updated incrementally in a fixed-size distributed representation, and inner products can be approximated on the fly at low computational cost. An open source implementation of generalised RI is provided.

关键词： Data mining Random embeddings Dimensionality reduction Sparse coding Semantic similarity streaming algorithm Natural language processing

来源：评论

学校读者我要写书评

暂无评论

PRACTICAL SKETCHING algorithmS FOR LOW-RANK MATRIX APPROXIMATION

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2017年第4期38卷 1454-1485页

作者： Tropp, Joel A. Yurtsever, Alp Udell, Madeleine Cevher, Volkan CALTECH Comp & Math Sci Pasadena CA 91125 USA Ecole Polytech Fed Lausanne CH-1015 Lausanne Switzerland Cornell Univ Ithaca NY 14853 USA

This paper describes a suite of algorithms for constructing low-rank approximations of an input matrix from a random linear image, or sketch, of the matrix. These methods can preserve structural properties of the input matrix, such as positive-semidefiniteness, and they can produce approximations with a user-specified rank. The algorithms are simple, accurate, numerically stable, and provably correct. Moreover, each method is accompanied by an informative error bound that allows users to select parameters a priori to achieve a given approximation quality. These claims are supported by numerical experiments with real and synthetic data.

关键词： dimension reduction matrix approximation numerical linear algebra randomized algorithm single-pass algorithm sketching streaming algorithm subspace embedding

来源：评论

学校读者我要写书评

暂无评论

New Bounds for the CLIQUE-GAP Problem Using Graph Decomposition Theory

引用

algorithmICA 2018年第2期80卷 652-667页

作者： Braverman, Vladimir Liu, Zaoxing Singh, Tejasvam Vinodchandran, N. V. Yang, Lin F. Johns Hopkins Univ Baltimore MD 21218 USA Univ Nebraska Lincoln Lincoln NE 68588 USA

Halldrsson et al (ICALP proceedings of the 39th international colloquium conference on automata, languages, and programming, vol part I, Springer, pp 449-460, 2012) investigated the space complexity of the following problem CLIQUE-GAP(r, s): given a graph stream G, distinguish whether or , where is the clique-number of G. In particular, they give matching upper and lower bounds for CLIQUE-GAP(r, s) for any r and , for some constant c. The space complexity of the CLIQUE-GAP problem for smaller values of s is left as an open question. In this paper, we answer this open question. Specifically, for any r and for , we prove that the space complexity of CLIQUE-GAP problem is . Our lower bound is based on a new connection between graph decomposition theory (Chung et al in Studies in pure mathematics, Birkhauser, Basel, pp 95-101, 1983;Chung in SIAM J Algebr Discrete Methods 2(1):1-12, 1981) and the multi-party set disjointness problem in communication complexity.

关键词： Communication complexity Clique streaming algorithm Graph decomposition Triangle counting

来源：评论

学校读者我要写书评

暂无评论

A New Method for Per-Flow Traffic Measurement

引用

IEICE TRANSACTIONS ON COMMUNICATIONS 2011年第8期E94B卷 2386-2389页

作者： Yoon, MyungKeun Kookmin Univ Dept Comp Engn Seoul South Korea

Per-flow traffic measurement is essential for network management;billing, traffic engineering, mitigating denial of service attacks, to mention just a few. In this field, the fundamental problem is that the size of expensive SRAM is too small to hold traffic data from high-speed networks. In this paper, we propose a new method for per-flow traffic measurement, which is based on the virtual vector that was originally designed for the problem of spread estimation. We modify the original virtual vector and show that this simple change yields a highly effective per-flow traffic estimator. Experiments show that our proposed scheme outperforms the state-of-the-art method in terms of both processing time and space requirement.

关键词： traffic monitoring network management streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

Maximizing the Differences Between a Monotone DR-Submodular Function and a Linear Function on the Integer Lattice

引用

Journal of the Operations Research Society of China 2024年第3期12卷 795-807页

作者： Zhen-Ning Zhang Dong-Lei Du Ran Ma Dan Wu Department of Operations Research and Information Engineering Beijing University of TechnologyBeijing100124China Faculty of Management University of New BrunswickFrederictonNB E3B 9Y2Canada School of Management Engineering Qingdao University of TechnologyQingdao266525ShandongChina School of Mathematics and Statistics Henan University of Science and TechnologyLuoyang471023HenanChina

In this paper,we investigate the maximization of the differences between a nonnegative monotone diminishing return submodular(DR-submodular)function and a nonnegative linear function on the integer *** it is almost unapproximable for maximizing a submodular function without the condition of nonnegative,we provide weak(bifactor)approximation algorithms for this problem in two online settings,*** the unconstrained online model,we combine the ideas of single-threshold greedy,binary search and function scaling to give an efficient algorithm with a 1/2 weak approximation *** the online streaming model subject to a cardinality constraint,we provide a one-pass(3-√5)/2 weak approximation ratio streaming *** memory complexity is(k log k/ε),and the update time for per element is(log^(2)k/ε).

关键词： Submodular maximization DR-submodular Integer lattice Single-threshold greedy algorithm streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

ON APPROXIMATING MATRIX NORMS IN DATA STREAMS

引用

SIAM JOURNAL ON COMPUTING 2019年第6期48卷 1643-1697页

作者： Li, Yi Nguyen, Huy L. Woodruff, David P. Nanyang Technol Univ Div Math Singapore 637371 Singapore Northeastern Univ Khoury Coll Comp Sci Boston MA 02115 USA Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA

This paper presents a systematic study of the space complexity of estimating the Schatten p-norms of an n x n matrix in the turnstile streaming model. Both kinds of space complexities, bit complexity and sketching dimension, are considered. Furthermore, two sketching models, general linear sketching and bilinear sketching, are considered. When p is not an even integer, we show that any one-pass algorithm with constant success probability requires near-linear space in terms of bits. This lower bound holds even for sparse matrices, i.e., matrices with O(1) nonzero entries per row and per column. However, when p is an even integer, we give for sparse matrices an upper bound which, up to logarithmic factors, is the same as estimating the pth moment of an n-dimensional vector. These results considerably strengthen lower bounds in previous work for arbitrary (not necessarily sparse) matrices. Similar near-linear lower bounds are obtained for Ky Fan norms, SVD entropy, eigenvalue shrinkers, and M-estimators, many of which could have been solvable in logarithmic space prior to this work. The results for general linear sketches give separations in the sketching complexity of Schatten p-norms with the corresponding vector p-norms, and rule out a table-lookup nearest-neighbor search for p = 1, making progress on a question of Andoni. The results for bilinear sketches are tight for the rank problem and nearly tight for p >= 2;the latter is the first general subquadratic upper bound for sketching the Schatten norms.

关键词： Schatten norm matrix norm streaming algorithm approximation algorithm sketching algorithm numerical linear algebra

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：