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

randomized data selection in detection with applications to distributed signal processing

PROCEEDINGS OF THE IEEE 2003年第8期91卷 1184-1198页

作者： Sestok, CK Said, MR Oppenheim, AV MIT Elect Res Lab Cambridge MA 02139 USA

Performing robust detection with resource limitations such as low-power requirements or limited communication bandwidth is becoming increasingly important in contexts involving distributed signal processing. One way to address these constraints consists of reducing the amount of data used by the detection algorithms. Intelligent data selection in detection can be highly dependent on a priori information about the signal and noise. In this paper we explore detection strategies based on randomized data selection and analyze the resulting algorithms' performance. randomized data selection is a viable approach in the absence of reliable and detailed a priori information, and it provides a reasonable lower bound on signal processing performance as more a priori information is incorporated. The randomized selection procedure has the added benefits of simple implementation in a distributed environment and limited communication overhead. As an example of detection algorithms based upon randomized selection, we analyze a binary hypothesis testing problem, and determine several useful properties of detectors derived from the likelihood ratio test. Additionally, we suggest an adaptive detector that accounts for fluctuations in the selected data subset. The advantages and disadvantages of this approach in distributed sensor networks applications are also discussed.

关键词： distributed signal processing likelihood ratio test nonparametric detection randomized algorithms randomized sampling sensor networks

来源：评论

学校读者我要写书评

暂无评论

An ellipsoid algorithm for probabilistic robust controller design

引用

SYSTEMS & CONTROL LETTERS 2003年第5期49卷 365-375页

作者： Kanev, S De Schutter, B Verhaegen, M Univ Twente Fac Appl Phys Syst & Control Engn Grp NL-7500 AE Enschede Netherlands Delft Univ Technol Fac Informat Technol & Syst Control Syst Engn Grp NL-2600 GA Delft Netherlands

In this paper, a new iterative approach to probabilistic robust controller design is presented, which is applicable to any robust controller/filter design problem that can be represented as an LMI feasibility problem. Recently, a probabilistic Subgradient Iteration algorithm was proposed for solving LMIs. It transforms the initial feasibility problem to an equivalent convex optimization problem, which is subsequently solved by means of an iterative algorithm. While this algorithm always converges to a feasible solution in a finite number of iterations, it requires that the radius of a non-empty ball contained into the solution set is known a priori. This rather restrictive assumption is released in this paper, while retaining the convergence property. Given an initial ellipsoid that contains the solution set, the approach proposed here iteratively generates a sequence of ellipsoids with decreasing volumes, all containing the solution set. At each iteration a random uncertainty sample is generated with a specified probability density, which parameterizes an LMI. For this LMI the next minimum-volume ellipsoid that contains the solution set is computed. An upper bound on the maximum number of possible correction steps, that can be performed by the algorithm before finding a feasible solution, is derived. A method for finding an initial ellipsoid containing the solution set, which is necessary for initialization of the optimization, is also given. The proposed approach is illustrated on a real-life diesel actuator benchmark model with real parametric uncertainty, for which a H-2 robust state-feedback controller is designed. (C) 2003 Elsevier B.V. All rights reserved.

关键词： probabilistic design randomized algorithms robust LMIs robust control ellipsoid algorithm

来源：评论

学校读者我要写书评

暂无评论

Testing basic boolean formulae

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2003年第1期16卷 20-46页

作者： Parnas, M Ron, D Samorodnitsky, A Acad Coll Tel Aviv Yaffo Tel Aviv Israel Tel Aviv Univ Dept EE Syst Ramat Aviv Israel Hebrew Univ Jerusalem Sch Engn & Comp Sci Jerusalem Israel Inst Adv Study Princeton NJ 08540 USA

We consider the problem of determining whether a given function f : {0, 1}(n) --> {0, 1} belongs to a certain class of Boolean functions F or whether it is far from the class. More precisely, given query access to the function f and given a distance parameter epsilon, we would like to decide whether f is an element of F or whether it differs from every g is an element of F on more than an c-fraction of the domain elements. The classes of functions we consider are singleton ("dictatorship") functions, monomials, and monotone disjunctive normal form functions with a bounded number of terms. In all cases we provide algorithms whose query complexity is independent of n (the number of function variables), and linear in 1/epsilon.

关键词： property testing Boolean functions randomized algorithms approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

The distribution of values in the quadratic assignment problem

引用

MATHEMATICS OF OPERATIONS RESEARCH 2003年第1期28卷 64-91页

作者： Barvinok, A Stephen, T Univ Michigan Dept Math Ann Arbor MI 48109 USA Univ Minnesota Inst Math & Its Applicat IMA Minneapolis MN 55455 USA

We obtain a number of results regarding the distribution of values of a quadratic function f on the set of n x n permutation matrices (identified with the symmetric group S) around its optimum,. (minimum or maximum). We estimate the fraction of permutations sigma such that f (sigma) lies within a given neighborhood of the optimal value of f and relate the optimal value with the average value of f over a neighborhood of the optimal permutation. We describe a natural class of functions (which includes, for example, the objective function in the Traveling Salesman Problem) with a relative abundance of near-optimal permutations. Also, we identify a large class of functions f with the property that permutations close to the optimal permutation in the Hamming metric of S-n tend to produce near optimal values of f (such is, for example, the objective function in the symmetric Traveling Salesman Problem). We show that for general f, just the opposite behavior may take place: an average permutation in the vicinity of the optimal permutation may be much worse than an average permutation in the whole group S-n.

关键词： Quadratic Assignment Problem distribution symmetric group randomized algorithms heuristics representation theory

来源：评论

学校读者我要写书评

暂无评论

Probabilistic design of LPV control systems

引用

AUTOMATICA 2003年第8期39卷 1323-1337页

作者： Fujisaki, Y Dabbene, F Tempo, R Kobe Univ Dept Syst & Comp Engn Kobe Hyogo 6578501 Japan Politecn Torino CNR IEIIT I-10129 Turin Italy

This paper presents an alternative approach to design of linear parameter-varying (LPV) control systems. In contrast to previous methods, which are focused on deterministic algorithms, this paper is based on a probabilistic setting. The proposed randomized algorithm provides a sequence of candidate solutions converging with probability one to a feasible solution in a finite number of steps. The main features of this approach are as follows: (i) The randomized algorithm gives a method for general LPV plants with state space matrices depending on scheduling parameters in a nonlinear manner. That is, the probabilistic setting does not need a gridding of the set of scheduling parameters or approximations such as a linear fractional transformation of the state space matrices. (ii) The proposed algorithm is sequential and, at each iteration, it does not require heavy computational effort such as solving simultaneously a large number of linear matrix inequalities. (C) 2003 Elsevier Ltd. All rights reserved.

关键词： randomized algorithms linear parameter-varying systems gain scheduling output feedback

来源：评论

学校读者我要写书评

暂无评论

One-pass wavelet decompositions of data streams

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2003年第3期15卷 541-554页

作者： Gilbert, AC Kotidis, Y Muthukrishnan, S Strauss, MJ AT&T Labs Res Florham Pk NJ 07932 USA

We present techniques for computing small space representations of massive data streams. These are inspired by traditional wavelet-based approximations that consist of specific linear projections of the underlying data. We present general "sketch"-based methods for capturing various linear projections and use them to provide pointwise and rangesum estimation of data streams. These methods use small amounts of space and per-item time while streaming through the data and provide accurate representation as our experiments with real data streams show.

关键词： data streams wavelets randomized algorithms approximate queries

来源：评论

学校读者我要写书评

暂无评论

Better algorithms for unfair metrical task systems and applications

引用

SIAM JOURNAL ON COMPUTING 2003年第6期32卷 1403-1422页

作者： Fiat, A Mendel, M Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel

Unfair metrical task systems are a generalization of online metrical task systems. In this paper we introduce new techniques to combine algorithms for unfair metrical task systems and apply these techniques to obtain ... 详细信息

关键词： online algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

On testing convexity and submodularity

引用

SIAM JOURNAL ON COMPUTING 2003年第5期32卷 1158-1184页

作者： Parnas, M Ron, D Rubinfeld, R Acad Coll Tel Aviv Yaffo Tel Aviv Israel Tel Aviv Univ Dept EE Syst Ramat Aviv Israel NEC Res Inst Princeton NJ 08540 USA

Convex and submodular functions play an important role in many applications, and in particular in combinatorial optimization. Here we study two special cases: convexity in one dimension and submodularity in two dimensions. The latter type off unctions are equivalent to the well-known Monge matrices. A matrix V = {v(i, j)} (i= n)(i,j,=0)(1, j= n2) is called a Monge matrix if for every 0 less than or equal to i < i' <= n(1) and 0 <= j < j' less than or equal to n(2) we have v(i, j) + v(i, j') less than or equal to v(i, j') + v(i', j). If inequality holds in the opposite direction, then V is an inverse Monge matrix ( supermodular function). Many problems, such as the traveling salesperson problem and various transportation problems, can be solved more efficiently if the input is a Monge matrix. In this work we present testing algorithms for the above properties. A testing algorithm for a predetermined property P is given query access to an unknown function f and a distance parameter epsilon. The algorithm should accept f with high probability if it has the property P and reject it with high probability if more than an epsilon-fraction of the function values should be modified so that f obtains the property. Our algorithm for testing whether a 1-dimensional function f : [n] --> R is convex (concave) has query complexity and running time of O ((log n)/epsilon). Our algorithm for testing whether an n(1) x n(2) matrix V is a Monge ( inverse Monge) matrix has query complexity and running time of O ((log n(1) . log n(2))/epsilon).

关键词： property testing convex functions Monge matrices approximation algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

The data broadcast problem with non-uniform transmission times

引用

ALGORITHMICA 2003年第2期35卷 146-175页

作者： Kenyon, C Schabanel, N Univ Paris 11 LRI F-91405 Orsay France ENS Lyon INRIA 5668 CNRS LIP F-69364 Lyon 07 France

The Data Broadcast Problem consists of finding an infinite schedule to broadcast a given set of messages so as to minimize a linear combination of the average service time to clients requesting messages, and of the cost of the broadcast. This problem also models the Maintenance Scheduling Problem and the Multi-Item Replenishment Problem. Previous work concentrated on a discrete-time restriction where all messages have transmission time equal to 1. Here, we study a generalization of the model to a setting of continuous time and messages of non-uniform transmission times. We prove that the Data Broadcast Problem is strongly NP-hard, even if the broadcast costs are all zero, and give 3-approximation algorithms.

关键词： approximation algorithms scheduling randomized algorithms NP-completeness data broadcasting

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithms for projective clustering

引用

JOURNAL OF algorithms-COGNITION INFORMATICS AND LOGIC 2003年第2期46卷 115-139页

作者： Agarwal, PK Procopiuc, CM Duke Univ Dept Comp Sci Ctr Geometr & Biol Comp Durham NC 27708 USA AT&T Labs Res Florham Pk NJ 07932 USA

We consider the following two instances of the projective clustering problem: Given a set S of n points in R-d and an integer k > 0, cover S by k slabs (respectively d-cylinders) so that the maximum width of a slab (respectively the maximum diameter of a d-cylinder) is minimized. Let w* be the smallest value so that S can be covered by k slabs (respectively d-cylinders), each of width (respectively diameter) at most w*. This paper contains three main results: (i) For d = 2, we present a randomized algorithm that computes O(k log k) strips of width at most w* that cover S. Its expected running time is O(nk(2) log(4) n) if k(2) log k less than or equal to n;for larger values of k, the expected running time is O(n(2/3) k(8/3) log(14/3) n). (ii) For d = 3, a cover of S by O(k log k) slabs of width at most w* can be computed in expected time O(n(3/2)k(9/4) polylog(n)). (iii) We compute a cover of S subset of R-d by O(d k log k) d-cylinders of diameter at most 8w* in expected time O(dnk(3) log(4) n). We also present a few extensions of this result. (C) 2003 Elsevier Science (USA). All rights reserved.

关键词： GEOMETRIC OPTIMIZATION LINES maximum width signal to noise ratios Approximation algorithms Diameter randomized algorithms logarithm (log) Plate slabs Sulfur Less than or equal to Cluster Analysis Runtime

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：