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

An HSS Matrix-Inspired Butterfly-Based Direct Solver for Analyzing Scattering From Two-Dimensional Objects

IEEE ANTENNAS AND WIRELESS PROPAGATION LETTERS 2017年 16卷 1179-1183页

作者： Liu, Yang Guo, Han Michielssen, Eric Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48109 USA

A butterfly-based fast direct integral equation solver for analyzing high-frequency scattering from two-dimensional objects is presented. The solver leverages a randomized butterfly scheme to compress blocks corresponding to near-and far-field interactions in the discretized forward and inverse electric field integral operators. The observed memory requirements and computational cost of the proposed solver scale as O(Nlog(2)N) and O(N-1.5 logN), respectively. The solver is applied to the analysis of scattering from electrically large objects spanning over 10 000 wavelengths and modeled in terms of five million unknowns.

关键词： Butterfly scheme electromagnetic scattering fast direct solver multilevel matrix decomposition algorithm (MLMDA) randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

A Statistical Perspective on algorithmic Leveraging

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2015年第1期16卷 861-911页

作者： Ma, Ping Mahoney, Michael W. Yu, Bin Univ Georgia Dept Stat Athens GA 30602 USA Univ Calif Berkeley Int Comp Sci Inst Berkeley CA 94720 USA Univ Calif Berkeley Dept Stat Berkeley CA 94720 USA

One popular method for dealing with large-scale data sets is sampling. For example, by using the empirical statistical leverage scores as an importance sampling distribution, the method of algorithmic leveraging samples and rescales rows/columns of data matrices to reduce the data size before performing computations on the subproblem. This method has been successful in improving computational efficiency of algorithms for matrix problems such as least-squares approximation, least absolute deviations approximation, and low-rank matrix approximation. Existing work has focused on algorithmic issues such as worst-case running times and numerical issues associated with providing high-quality implementations, but none of it addresses statistical aspects of this method. In this paper, we provide a simple yet effective framework to evaluate the statistical properties of algorithmic leveraging in the context of estimating parameters in a linear regression model with a fixed number of predictors. In particular, for several versions of leverage-based sampling, we derive results for the bias and variance, both conditional and unconditional on the observed data. We show that from the statistical perspective of bias and variance, neither leverage-based sampling nor uniform sampling dominates the other. This result is particularly striking, given the well-known result that, from the algorithmic perspective of worst-case analysis, leverage-based sampling provides uniformly superior worst-case algorithmic results, when compared with uniform sampling. Based on these theoretical results, we propose and analyze two new leveraging algorithms: one constructs a smaller least-squares problem with "shrinkage" leverage scores (SLEV), and the other solves a smaller and unweighted (or biased) least-squares problem (LEVUNW). A detailed empirical evaluation of existing leverage-based methods as well as these two new methods is carried out on both synthetic and real data sets. The empirical result

关键词： randomized algorithm leverage scores subsampling least squares linear regression

来源：评论

学校读者我要写书评

暂无评论

Scalable wake-up of multi-channel single-hop radio networks

引用

THEORETICAL COMPUTER SCIENCE 2016年 615卷 23-44页

作者： Chlebus, Bogdan S. De Marco, Gianluca Kowalski, Dariusz R. Univ Colorado Dept Comp Sci & Engn Denver CO 80217 USA Univ Salerno Dipartimento Informat I-84084 Salerno Italy Univ Liverpool Dept Comp Sci Liverpool L69 3BX Merseyside England

We consider single-hop radio networks with multiple channels as a model of wireless networks. There are n stations connected to b radio channels that do not provide collision detection. A station uses all the channels concurrently and independently. Some k stations may become active spontaneously at arbitrary times. The goal is to wake up the network, which occurs when all the stations hear a successful transmission on some channel. Duration of a waking-up execution is measured starting from the first spontaneous activation. We present a deterministic algorithm that wakes up a network in O(k log(1/b) k log n) time, where k is unknown. We give a deterministic scalable algorithm for the special case when b > d log log n, for some constant d > 1, which wakes up a network in O(k/b log n log(b log n)) time, with k unknown. This algorithm misses time optimality by at most a factor of O(log n(log b + log log n)), because any deterministic algorithm requires Omega(k/b log n/k) time. We give a randomized algorithm that wakes up a network within O(k(1/b) In 1/epsilon) rounds with a probability that is at least 1 - epsilon, for any 0 < epsilon < 1, where k is known. We also consider a model of jamming, in which each channel in any round may be jammed to prevent a successful transmission, which happens with some known parameter probability p, independently across all channels and rounds. For this model, we give two deterministic algorithms for unknown k: one wakes up a network in time O(log(-1) (1/p) log n log(1/b) k), and the other in time O(log(-1) (1/p) k/b log n log(b log n)) when the inequality b > log(128b log n) holds, both with probabilities that are at least 1 - 1/poly(n). (c) 2015 Elsevier B.V. All rights reserved.

关键词： Multiple access channel Radio network Multi-channel Wake-up Synchronization Deterministic algorithm randomized algorithm Distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

On derandomization and average-case complexity of monotone functions

引用

THEORETICAL COMPUTER SCIENCE 2012年 434卷 35-44页

作者： Karakostas, George Kinne, Jeff van Melkebeek, Dieter Indiana State Univ Terre Haute IN 47809 USA McMaster Univ Hamilton ON L8S 4L8 Canada Univ Wisconsin Madison WI 53706 USA

We investigate whether circuit lower bounds for monotone circuits can be used to derandomize randomized monotone circuits. We show that, in fact, any derandomization of randomized monotone computations would derandomize all randomized computations, whether monotone or not. We prove similar results in the settings of pseudorandom generators and average-case hard functions - that a pseudorandom generator secure against monotone circuits is also secure with somewhat weaker parameters against general circuits, and that an average-case hard function for monotone circuits is also hard with somewhat weaker parameters for general circuits. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Derandomization Monotone circuits Monotone functions randomized algorithm Pseudorandom generators Average-case complexity

来源：评论

学校读者我要写书评

暂无评论

IMPORTANCE SAMPLING FOR A MONTE CARLO MATRIX MULTIPLICATION algorithm, WITH APPLICATION TO INFORMATION RETRIEVAL

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2011年第4期33卷 1689-1706页

作者： Eriksson-Bique, Sylvester Solbrig, Mary Stefanelli, Michael Warkentin, Sarah Abbey, Ralph Ipsen, Ilse C. F. Univ Helsinki FI-00014 Helsinki Finland Reed Coll Portland OR 97202 USA Coll New Jersey Ewing NJ 08628 USA Harvey Mudd Coll Claremont CA 91711 USA N Carolina State Univ Dept Math Raleigh NC 27695 USA

We perform importance sampling for a randomized matrix multiplication algorithm by Drineas, Kannan, and Mahoney and derive probabilities that minimize the expected value (with regard to the distributions of the matrix elements) of the variance. We compare these optimized probabilities with uniform probabilities and derive conditions under which the actual variance of the optimized probabilities is lower. Numerical experiments with query matching in information retrieval applications illustrate that the optimized probabilities produce more accurate matchings than the uniform probabilities and that they can also be computed efficiently.

关键词： randomized algorithm expected value variance term-by-document matrix query matching

来源：评论

学校读者我要写书评

暂无评论

Fast concurrent access to parallel disks

引用

algorithmICA 2003年第1期35卷 21-55页

作者： Sanders, P Egner, S Korst, J Max Planck Inst Comp Sci D-66123 Saarbrucken Germany Philips Res Labs NL-5656 AA Eindhoven Netherlands

High performance applications involving large data sets require the efficient and flexible use of multiple disks. In an external memory machine with D parallel, independent disks, only one block can be accessed on each disk in one I/O step. This restriction leads to a load balancing problem that is perhaps the main inhibitor for the efficient adaptation of single-disk external memory algorithms to multiple disks. We solve this problem for arbitrary access patterns by randomly mapping blocks of a logical address space to the disks. We show that a shared buffer of O(D) blocks suffices to support efficient writing. The analysis uses the properties of negative association to handle dependencies between the random variables involved. This approach might be of independent interest for probabilistic analysis in general. If two randomly allocated copies of each block exist, N arbitrary blocks can be read within [N/D] + 1 I/O steps with high probability. The redundancy can be further reduced from 2 to 1 + 1/r for any integer r without a big impact on reading efficiency. From the point of view of external memory models, these results rehabilitate Aggarwal and Vitter's "single-disk multi-head" model [1] that allows access to D arbitrary blocks in each I/O step. This powerful model can be emulated on the physically more realistic independent disk model [2] with small constant overhead factors. Parallel disk external memory algorithms can therefore be developed in the multi-head model first. The emulation result can then be applied directly or further refinements can be added.

关键词： randomized algorithm scheduling load balancing external memory

来源：评论

学校读者我要写书评

暂无评论

Regularized Kaczmarz algorithms for Tensor Recovery

引用

SIAM JOURNAL ON IMAGING SCIENCES 2021年第4期14卷 1439-1471页

作者： Chen, Xuemei Qin, Jing Univ North Carolina Wilmington Dept Math & Stat Wilmington NC 28409 USA Univ Kentucky Dept Math Lexington KY 40506 USA

Tensor recovery has recently arisen in a lot of application fields, such as transportation, medical imaging, and remote sensing. Under the assumption that signals possess sparse and/or low-rank structures, many tensor recovery methods have been developed to apply various regularization techniques together with the operator-splitting type of algorithms. Due to the unprecedented growth of data, it becomes increasingly desirable to use streamlined algorithms to achieve real-time computation, such as stochastic optimization algorithms that have recently emerged as an efficient family of methods in machine learning. In this work, we propose a novel algorithmic framework based on the Kaczmarz algorithm for tensor recovery. We provide thorough convergence analysis and its applications from the vector case to the tensor one. Numerical results on a variety of tensor recovery applications, including sparse signal recovery, low-rank tensor recovery, image inpainting, and deconvolution, illustrate the enormous potential of the proposed methods.

关键词： Kaczmarz algorithm tensor recovery image inpainting image deblurring randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

On approximating the d-girth of a graph

引用

DISCRETE APPLIED MATHEMATICS 2013年第16-17期161卷 2587-2596页

作者： Peleg, David Sau, Ignasi Shalom, Mordechai Weizmann Inst Sci IL-76100 Rehovot Israel CNRS LIRMM Montpellier France TelHai Acad Coll IL-12210 Upper Galilee Israel

For a finite, simple, undirected graph G and an integer d >= 1, a mindeg-d subgraph is a subgraph of G of minimum degree at least d. The d-girth of G, denoted by g(d)(G), is the minimum size of a mindeg-d subgraph of G. It is a natural generalization of the usual girth, which coincides with the 2-girth. The notion of d-girth was proposed by Erdos et al. (1988, 1990) [14,15] and Bollobas and Brightwell (1989) [8] over 25 years ago, and studied from a purely combinatorial point of view. Since then, no new insights have appeared in the literature. Recently, first algorithmic studies of the problem have been carried out by Amini et al. (2012a,b) [2,4]. The current article further explores the complexity of finding a small mindeg-d subgraph of a given graph (that is, approximating its d-girth), by providing new hardness results and the first approximation algorithms in general graphs, as well as analyzing the case where G is planar. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Generalized girth Minimum degree Approximation algorithm Hardness of approximation randomized algorithm Planar graph

来源：评论

学校读者我要写书评

暂无评论

Service Home Identification of Multiple-Source IoT Applications in Edge Computing

引用

IEEE TRANSACTIONS ON SERVICES COMPUTING 2023年第2期16卷 1417-1430页

作者： Li, Jing Liang, Weifa Xu, Wenzheng Xu, Zichuan Li, Yuchen Jia, Xiaohua Australian Natl Univ Sch Comp Canberra ACT 2601 Australia City Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China Sichuan Univ Coll Comp Sci Chengdu 610017 Peoples R China Dalian Univ Technol Sch Software Dalian 116024 Peoples R China

The real-time communication requirement of the Internet of Things (IoT) applications promotes the convergence of IoT and Mobile Edge Computing (MEC). The MEC paradigm greatly shortens the IoT service delay by leveraging cloudlets (edge servers) of MEC in the proximity of IoT devices. Considering limited computing and storage resources in an MEC network, it is challenging to provide efficient IoT-enabled service provisioning in such a network. In this article, we study the service home identification problem of service provisioning for multi-source IoT applications in an MEC network, by identifying a service home (cloudlet) of each multi-source IoT application for its data processing, querying and storage. Each multi-source IoT application consists of multiple sources located at different geographical locations and each source uploads its data stream via a gateway (its nearby access point) to the MEC network and the uploaded data then is aggregated with the stream data of the other sources of the IoT application at the service home. We here focus on two novel service home identification problems: the service operational cost minimization problem with the aim to minimize the total service operational cost by admitting as many multi-source IoT applications as possible, and the online throughput maximization problem with the aim to maximize the number of multi-source IoT application requests admitted. We first show that both the problems are NP-hard. We then formulate an Integer Linear Programming (ILP) solution to the service operational cost minimization problem, and propose a randomized algorithm with high probability and a deterministic approximation algorithm respectively, at moderate resource capacity violations. We third develop an efficient heuristic algorithm for the problem without any resource violation. Furthermore, we deal with the online throughput maximization problem under an assumption that multi-source IoT application requests arrive one by one without

关键词： Internet of Things Heuristic algorithms Cloud computing Costs Approximation algorithms Minimization Delays Internet of Things (IoT) mobile edge computing (MEC) service provisioning for multi-source IoT applications service operational cost minimization randomized algorithm online algorithm resource allocation and optimization dynamic IoT application request admissions network slicing in edge computing

来源：评论

学校读者我要写书评

暂无评论

Optimizing static and adaptive probing schedules for rapid event detection

引用

THEORETICAL COMPUTER SCIENCE 2019年 774卷 14-30页

作者： Mahmoody, Ahmad Upfal, Eli Brown Univ Dept Comp Sci Providence RI 02912 USA

We formulate and study a fundamental search and detection problem, Schedule Optimization, motivated by a variety of real-world applications, ranging from monitoring content changes on the web, social networks, and user activities to detecting failure on large systems with many individual machines. We consider a large system consists of many nodes, where each node has its own rate of generating new events, or items. A monitoring application can probe a small number of nodes at each step, and our goal is to compute a probing schedule that minimizes the expected number of undiscovered items at the system, or equivalently, minimizes the expected time to discover a new item in the system. We study the Schedule Optimization problem both for deterministic and randomized memoryless algorithms. We provide lower bounds on the cost of an optimal schedule and construct close to optimal schedules with rigorous mathematical guarantees. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Event/novelty detection Sampling randomized algorithm Approximation algorithm Probabilistic method

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：