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

Sensor networks: From dependence analysis via matroid bases to online synthesis

THEORETICAL COMPUTER SCIENCE 2014年第0期553卷 2-17页

作者： Cohen, Asaf Dolev, Shlomi Leshem, Guy Ben Gurion Univ Negev Dept Commun Syst Engn IL-84105 Beer Sheva Israel Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel Ashkelon Acad Coll Dept Comp Sci Ashqelon Israel

Consider the two related problems of sensor selection and sensor fusion. In the first, given a set of sensors, one wishes to identify a subset of the sensors, which while small in size, captures the essence of the data gathered by the sensors. In the second, one wishes to construct a fused sensor, which utilizes the data from the sensors (possibly after discarding dependent ones) in order to create a single sensor which is more reliable than each of the individual ones. In this work, we rigorously define the dependence among sensors in terms of joint empirical measures and incremental parsing. We show that these measures adhere to a polymatroid structure, which in turn facilitates the application of efficient algorithms for sensor selection. We suggest both a random and a greedy algorithm for sensor selection. Given an independent set, we then turn to the fusion problem, and suggest a novel variant of the exponential weighting algorithm. In the suggested algorithm, one competes against an augmented set of sensors, which allows it to converge to the best fused sensor in a family of sensors, without having any prior data on the sensors' performance. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Sensor networks Dependence analysis Polymatroids Matroid optimization randomized algorithms Greedy selection Empirical measures Lempel-Ziv Incremental parsing Online fusion

来源：评论

学校读者我要写书评

暂无评论

A statistical learning theory approach for uncertain linear and bilinear matrix inequalities

引用

AUTOMATICA 2014年第6期50卷 1617-1625页

作者： Chamanbaz, Mohammadreza Dabbene, Fabrizio Tempo, Roberto Venkataramanan, Venkatakrishnan Wang, Qing-Guo Data Storage Inst Singapore Singapore Politecn Torino CNR IEIIT I-10129 Turin Italy Natl Univ Singapore Dept Elect & Comp Engn Singapore 117548 Singapore

In this paper, we consider the problem of minimizing a linear functional subject to uncertain linear and bilinear matrix inequalities, which depend in a possibly nonlinear way on a vector of uncertain parameters. Motivated by recent results in statistical learning theory, we show that probabilistic guaranteed solutions can be obtained by means of randomized algorithms. In particular, we show that the Vapnik-Chervonenkis dimension (VC-dimension) of the two problems is finite, and we compute upper bounds on it. In turn, these bounds allow us to derive explicitly the sample complexity of these problems. Using these bounds, in the second part of the paper, we derive a sequential scheme, based on a sequence of optimization and validation steps. The algorithm is on the same lines of recent schemes proposed for similar problems, but improves both in terms of complexity and generality. The effectiveness of this approach is shown using a linear model of a robot manipulator subject to uncertain parameters. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Statistical learning theory Vapnik-Chervonenkis dimension Uncertain linear/bilinear matrix inequality randomized algorithms Probabilistic design

来源：评论

学校读者我要写书评

暂无评论

A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2014年第2期57卷 307-337页

作者： Necoara, Ion Patrascu, Andrei Univ Politeh Bucharest Automat Control & Syst Engn Dept Bucharest 060042 Romania

In this paper we propose a variant of the random coordinate descent method for solving linearly constrained convex optimization problems with composite objective functions. If the smooth part of the objective function has Lipschitz continuous gradient, then we prove that our method obtains an I mu-optimal solution in iterations, where n is the number of blocks. For the class of problems with cheap coordinate derivatives we show that the new method is faster than methods based on full-gradient information. Analysis for the rate of convergence in probability is also provided. For strongly convex functions our method converges linearly. Extensive numerical tests confirm that on very large problems, our method is much more numerically efficient than methods based on full gradient information.

关键词： Coordinate descent Composite objective function Linearly coupled constraints randomized algorithms Convergence rate O(1/epsilon)

来源：评论

学校读者我要写书评

暂无评论

FAST-Fast Algorithm for the Scenario Technique

引用

OPERATIONS RESEARCH 2014年第3期62卷 662-671页

作者： Care, Algo Garatti, Simone Campi, Marco C. Univ Melbourne Dept Elect & Elect Engn Parkville Vic 3052 Australia Politecn Milan Dipartimento Elettron Informaz & Bioingn I-20133 Milan Italy Univ Brescia Dipartimento Ingn Informaz I-25123 Brescia Italy

The scenario approach is a recently introduced method to obtain feasible solutions to chance-constrained optimization problems based on random sampling. It has been noted that the sample complexity of the scenario approach rapidly increases with the number of optimization variables and this may pose a hurdle to its applicability to medium-and large-scale problems. We here introduce the Fast Algorithm for the Scenario Technique, a variant of the scenario optimization algorithm with reduced sample complexity.

关键词： stochastic programming chance-constrained optimization randomized algorithms sample-based methods scenario approach

来源：评论

学校读者我要写书评

暂无评论

On the advice complexity of the online L(2,1)-coloring problem on paths and cycles

引用

THEORETICAL COMPUTER SCIENCE 2014年第0期554卷 22-39页

作者： Bianchi, Maria Paola Boeckenhauer, Hans-Joachim Hromkovic, Juraj Krug, Sacha Steffen, Bjoern Univ Milan Dipartimento Informat I-20122 Milan Italy Swiss Fed Inst Technol Dept Comp Sci Zurich Switzerland

In an L(2, 1)-coloring of a graph, the vertices are colored with colors from an ordered set such that neighboring vertices get colors that have distance at least 2 and vertices at distance 2 in the graph get different colors. We consider the problem of finding an L(2, 1)-coloring using a minimum range of colors in an online setting where the vertices arrive in consecutive time steps together with information about their neighbors and vertices at distance 2 among the previously revealed vertices. For this, we restrict our attention to paths and cycles. Offline, paths can easily be colored within the range {0, ... , 4} of colors. We prove that, considering deterministic algorithms in an online setting, the range {0, ... , 6} is necessary and sufficient while a simple greedy strategy needs range (0, ... , 7}. Advice complexity is a recently developed framework to measure the complexity of online problems. The idea is to measure how many bits of advice about the yet unknown parts of the input an online algorithm needs to compute a solution of a certain quality. We show a sharp threshold on the advice complexity of the online L(2, 1)-coloring problem on paths and cycles. While achieving color range (0, ... , 6} does not need any advice, improving over this requires a number of advice bits that is linear in the size of the input. Thus, the L(2, 1)-coloring problem is the first known example of an online problem for which sublinear advice does not help. We further use our advice complexity results to prove that no randomized online algorithm can achieve a better expected competitive ratio than 5/4(1 - delta), for any delta > 0. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Online coloring Frequency assignment Advice complexity randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

The Bell Is Ringing in Speed-Scaled Multiprocessor Scheduling

引用

THEORY OF COMPUTING SYSTEMS 2014年第1期54卷 24-44页

作者： Greiner, Gero Nonner, Tim Souza, Alexander Tech Univ Munich D-80290 Munich Germany IBM Res Zurich Zurich Switzerland Humboldt Univ D-10099 Berlin Germany

This paper investigates the problem of scheduling jobs on multiple speed-scaled processors, i.e., we have constant alpha > 1 such that running a processor at speed s results in energy consumption s (alpha) per time unit. We consider the general case where each job has a monotonously increasing cost function that penalizes delay. This includes the so far considered cases of deadlines, flow time, and weighted flow time. For any type of delay cost functions, we obtain the following results: Any beta-approximation algorithm for a single processor yields a randomized beta B (alpha) -approximation algorithm for multiple processors, where B (alpha) is the alpha th Bell number, that is, the number of partitions of a set of size alpha. The generated schedule is without migration, but we compare it to an optimal schedule with migration. Hence, this result holds for migratory and non-migratory schedules. Analogously, we show that any beta-competitive online algorithm for a single processor yields a beta B (alpha) -competitive online algorithm for multiple processors. Finally, we show that any beta-approximation algorithm for multiple processors with migration yields a deterministic beta B (alpha) -approximation algorithm for multiple processors without migration. These facts improve several approximation ratios and lead to new results. For instance, we obtain the first constant factor online and offline approximation algorithm for multiple processors without migration for arbitrary release times, deadlines, and job sizes.

关键词： Approximation algorithms Online algorithms randomized algorithms Scheduling Speed-scaling Probabilistic analysis

来源：评论

学校读者我要写书评

暂无评论

High-Dimensional Screening Using Multiple Grouping of Variables

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2014年第3期62卷 694-702页

作者： Vats, Divyanshu Rice Univ Dept Elect & Comp Engn Houston TX 77098 USA

Screening is the problem of finding a superset of the set of non-zero entries in an unknown p-dimensional vector beta* given n noisy observations. Naturally, we want this superset to be as small as possible. We propose a novel framework for screening, which we refer to as Multiple Grouping (MuG), that groups variables, performs variable selection over the groups, and repeats this process multiple number of times to estimate a sequence of sets that contains the non-zero entries in beta*. Screening is done by taking an intersection of all these estimated sets. The MuG framework can be used in conjunction with any group based variable selection algorithm. In the high-dimensional setting, where p >> n, we show that when MuG is used with the group Lasso estimator, screening can be consistently performed without using any tuning parameter. Our numerical simulations clearly show the merits of using the MuG framework in practice.

关键词： Screening Lasso group Lasso variable selection multiple grouping randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Online Metric Tracking and Smoothing

引用

ALGORITHMICA 2014年第1期68卷 133-151页

作者： Chen, Sixia Russell, Alexander Univ Connecticut Dept Comp Sci & Engn Storrs CT 06269 USA

We consider the online smoothing problem, in which a tracker is required to maintain distance no more than Delta a parts per thousand yen0 from a time-varying signal f while minimizing its own movement. The problem is determined by a metric space (X,d) with an associated cost function c:a"ea dagger'a"e. Given a signal f (1),f (2),aEuro broken vertical bar aX the tracker is responsible for producing a sequence a (1),a (2),aEuro broken vertical bar of elements of X that meet the proximity constraint: d(f (i) ,a (i) )a parts per thousand currency sign Delta. To complicate matters, the tracker is on-line-the value a (i) may only depend on f (1),aEuro broken vertical bar,f (i) -and wishes to minimize the cost of his travels, ac(d(a (i) ,a (i+1))). We evaluate such tracking algorithms competitively, comparing this with the cost achieved by an optimal adversary apprised of the entire signal in advance. The problem was originally proposed by Yi and Zhang (In: Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms (SODA), pp. 1098-1107. ACM Press, New York, 2009), who considered the natural circumstance where the metric spaces are taken to be a"currency sign (k) with the a"" (2) metric and the cost function is equal to 1 unless the distance is zero (thus the tracker pays a fixed cost for any nonzero motion). - We begin by studying arbitrary metric spaces with the "pay if you move" metric of Yi and Zhang (In: Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms (SODA), pp. 1098-1107. ACM Press, New York, [2009]) described above and describe a natural randomized algorithm that achieves a O(logb (Delta))-competitive ratio, where b (Delta)=max (xaX) |B (Delta)(x)| is the maximum number of points appearing in any ball of radius Delta. We show that this bound is tight. We then focus on the metric space a"currency sign with natural families of monotone cost functions c(x)=x (p) for some pa parts per thousand yen0. We consider both the expansive

关键词： Online algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Probabilistic Optimal Estimation With Uniformly Distributed Noise

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2014年第8期59卷 2113-2127页

作者： Dabbene, Fabrizio Sznaier, Mario Tempo, Roberto Politecn Torino CNR IEIIT Turin Italy Northeastern Univ Boston MA 02115 USA

The classical approach to system identification is based on stochastic assumptions about the measurement error, and provides estimates that have random nature. Worst-case identification, on the other hand, only assumes the knowledge of deterministic error bounds, and establishes guaranteed estimates, thus being in principle better suited for the use in control design. However, a main limitation of such deterministic bounds lies in their potential conservatism, thus leading to estimates of restricted use. In this paper, we propose a rapprochement between the stochastic and worst-case system identification viewpoints, which is based on the probabilistic setting of information-based complexity. The main idea in this line of research is to "discard" sets of measure at most epsilon, where epsilon is a probabilistic accuracy, from the set of deterministic estimates. Therefore, we are decreasing the so-called worst-case radius of information at the expense of a given probabilistic "risk." In the case of uniformly distributed noise, we derive new computational results, and in particular we compute a trade-off curve, called violation function, which shows how the radius of information decreases as a function of the accuracy. To this end, we construct randomized and deterministic algorithms which provide approximations of this function. We report extensive simulations showing numerical comparisons between the stochastic, worst-case and probabilistic approaches, thus demonstrating the efficacy of the methods proposed in this paper.

关键词： Least-squares linear estimation optimal algorithms randomized algorithms system identification uncertain systems

来源：评论

学校读者我要写书评

暂无评论

Matrix Recipes for Hard Thresholding Methods

引用

JOURNAL OF MATHEMATICAL IMAGING AND VISION 2014年第2期48卷 235-265页

作者： Kyrillidis, Anastasios Cevher, Volkan Ecole Polytech Fed Lausanne Lab Informat & Inference Syst Lausanne Switzerland

In this paper, we present and analyze a new set of low-rank recovery algorithms for linear inverse problems within the class of hard thresholding methods. We provide strategies on how to set up these algorithms via basic ingredients for different configurations to achieve complexity vs. accuracy tradeoffs. Moreover, we study acceleration schemes via memory-based techniques and randomized, I mu-approximate matrix projections to decrease the computational costs in the recovery process. For most of the configurations, we present theoretical analysis that guarantees convergence under mild problem conditions. Simulation results demonstrate notable performance improvements as compared to state-of-the-art algorithms both in terms of reconstruction accuracy and computational complexity.

关键词： Affine rank minimization Hard thresholding epsilon-approximation schemes randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：