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

A SUBLINEAR-TIME randomized algorithm FOR COLUMN AND ROW SUBSET SELECTION BASED ON STRONG RANK-REVEALING QR FACTORIZATIONS\ast

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2025年第1期46卷 22-44页

作者： Cortinovis, Alice Ping, Lexing Stanford Univ Dept Math Stanford CA 94305 USA Stanford Univ Dept Math Stanford CA 94305 USA Stanford Univ ICME Stanford CA 94305 USA

In this work, we analyze a sublinear-time algorithm for selecting a few rows and columns of a matrix for low-rank approximation purposes. The algorithm is based on an initial uniformly random selection of rows and columns, followed by a refinement of this choice using a strong rank-revealing QR factorization. We prove bounds on the error of the corresponding low-rank approximation (more precisely, the CUR approximation error) when the matrix is a perturbation of a low-rank matrix that can be factorized into the product of matrices with suitable incoherence and/or sparsity assumptions.

关键词： low-rank approximation column subset selection strong rank-revealing QR randomized algorithm uniform sampling incoherence

来源：评论

学校读者我要写书评

暂无评论

randomized algorithm for the sum selection problem

引用

THEORETICAL COMPUTER SCIENCE 2007年第1-3期377卷 151-156页

作者： Lin, Tien-Ching Lee, D. T. Acad Sinica Inst Informat Sci Taipei 11529 Taiwan Natl Taiwan Univ Dept Comp Sci & Informat Engn Taipei 10764 Taiwan

Let A be a sequence of n real numbers a(1), a(2),., a(n). We consider the SUM SELECTION PROBLEM as that of finding the segment A(i*, j*) such that the rank of s(i*, j*) = Sigma(j*)(t=i) at over all possible feasible segments is k, where a feasible segment A (i, j) = a(i), a(i + 1),..., a(j) is a consecutive subsequence of A, and its width j - i + 1 satisfies l <= j - i + 1 <= u for some given integers t and it, and l <= u. It is a generalization of two well-known problems: the SELECTION PROBLEM in computer science for which e = it = 1, and the MAXIMUM SUM SEGMENT PROBLEM in bioinformatics for which the rank k is the total number of possible feasible segments. We will give a randomized algorithm for the Sum SELECTION PROBLEM that runs in expected O(n log(u - l)) time. It matches the optimal O(n) time randomized algorithm for the SELECTION PROBLEM. We can also solve the K MAXIMUM SUMS PROBLEM, to enumerate the k largest sums, in expected 0(n log(u - e) + k) time. The previously best known result was an algorithm that solves this problem for the case when f = 1, u = n and runs in O(n log(2) n + k) time in the worst case. (c) 2007 Elsevier B.V. All rights reserved.

关键词： bioinformatics randomized algorithm random sampling order-statistic tree k maximum sums problem sum selection problem selection problem maximum sum segment problem maximum sum problem

来源：评论

学校读者我要写书评

暂无评论

randomized algorithm for global optimization with bounded memory

引用

MATHEMATICS AND COMPUTERS IN SIMULATION 2010年第6期80卷 1068-1081页

作者： Calvin, James M. New Jersey Inst Technol Dept Comp Sci Newark NJ 07102 USA

We describe a class of adaptive algorithms tor approximating the global minimum of a function defined on a compact subset of R(d) The algorithms are adaptive versions of Monte Carlo search and use a memory of a fixed number of past observations By choosing a large enough memory. the convergence rate can be made to exceed any power of the convergence rate obtained with standard Monte Carlo search (C) 2008 IMACS Published by Elsevier B V All rights reserved

关键词： Global optimization Monte Carlo methods Parallel algorithm Point process randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

randomized algorithm Based Fault Detection System Design for Uncertain LTI Systems

引用

IFAC-PapersOnLine 2017年第1期50卷 3648-3653页

作者： Krueger M. Koenings T. Liu Y. Ding S.X. Saijai J. Li L. Institute for Automatic Control and Complex Systems University of Duisburg-Essen Bismarckstr. 81 BB Duisburg 47048 Germany Department of Electrical Engineering Burapha UniversityChonburi 20131 Thailand School of Automation and Electrical Engineering University of Science and Technology Beijing Beijing 100083 China

This paper studies the design of fault detection (FD) system for uncertain linear time-invariant (LTI) systems based on randomized algorithms. With the help of probabilistic robustness techniques, an iterative design approach is proposed to determine the post-filter of observer-based residual generators with direct incorporation of the probability distribution of the model parameter uncertainties into the design procedure. The effectiveness of the proposed approach is demonstrated with an illustrative example. © 2017

关键词： Fault detection randomized algorithm Uncertain systems

来源：评论

学校读者我要写书评

暂无评论

randomized algorithm for the partial set multicover problem 18

Randomized algorithm for the partial set multicover problem

引用

4th International Conference on Engineering and MIS (ICEMIS)

作者： Gorgi, A. El Ouali, M. Hachimi, M. Krit, S. Univ Ibn Zohr Agadir Agadir Morocco Fac Polydisciplinary Ouarzazate Ouarzazate Morocco

ISBN: (纸本)9781450363921

In this paper we analyze the minimum cardinality PARTIAL SET b-MULTICOVER problem in uniform and regular hypergraphs. The problem is defined as follows: Let k is an element of (>= 1), b >= 2 and a hypergraph H = (V, E) with maximum vertex degree Delta and maximum edge size l, a PARTIAL SET b-MULTICOVER in H is a set of edges C subset of E such that every vertex in a subset U subset of V with vertical bar U vertical bar >= k, belongs to at least b edges in C. PARTIAL SET b- MULTICOVER problem is the problem of finding a PARTIAL SET b-MULTICOVER of minimum cardinality. We present a randomized algorithm of hybrid type for this problem, combining LP-based randomized rounding with greedy repairing. We achieve an approximation ratio of alpha(n, k) n/k (Delta - b + 1) with alpha (n, k) < 2 a factor depends on n and k for hypergraphs with l is an element of O(n(1/5)). Furthermore we consider the SET b-MULTICOVER problem in hypergraphs i.e., the PARTIAL SET b-MULTICOVER problem for k = n. It remained an open problem whether an approximation ratio of alpha(Delta - b + 1) with a constant alpha < 1 can be proved unless P = NP. This was conjectured by Peleg, Schechtman and Wool (algorithmica 1997). We present a randomized algorithm for SET b-MULTICOVER, and achieve an approximation ratio of (1 - 1/2 root 2 root n) (Delta - b + 1) for hypergraphs with maximum edge size l is an element of O(n(1/2)). The results for both problems presented in this paper improve for large set of instances over the known results.

关键词： Combinatorial optimization approximation algorithms randomized algorithm hypergraphs multicover

来源：评论

学校读者我要写书评

暂无评论

randomized algorithm Based Fault Detection System Design for Uncertain LTI Systems

Randomized Algorithm Based Fault Detection System Design for...

引用

20th World Congress of the International-Federation-of-Automatic-Control (IFAC)

作者： Krueger, M. Koenings, T. Liu, Y. Ding, S. X. Saijai, J. Li, L. Univ Duisburg Essen Inst Automat Control & Complex Syst Bismarckstr 81 BB D-47048 Duisburg Germany Burapha Univ Dept Elect Engn Chon Buri 20131 Thailand Univ Sci & Technol Beijing Sch Automat & Elect Engn Beijing 100083 Peoples R China

关键词： Fault detection randomized algorithm Uncertain systems

来源：评论

学校读者我要写书评

暂无评论

A randomized algorithm for the efficient synthesis of heat exchanger networks

引用

COMPUTERS & CHEMICAL ENGINEERING 2010年第10期34卷 1632-1639页

作者： Gupta, Abhigyan Ghosh, Pallab Indian Inst Technol Guwahati Dept Chem Engn Gauhati 781039 Assam India

This article presents an algorithm for the synthesis of heat exchanger networks (HENs) using randomization as an effective tool. It optimizes the total cost of the network. The method proposed here is suitable for finding the optimal solution with stream-splitting and merging. The present approach provides significant advantage of randomization over other existing optimization techniques for obtaining the optimal solution. We have studied three benchmark problems already published in the literature to demonstrate how better solutions were undetected by the earlier approaches. The salient feature of the proposed algorithm is that it provides a variety of possible networks which are close to the optimal network. Another important aspect is that the algorithm is quite fast. For small-and medium-size problems, the technique proposed in this article will prove to be very effective for the design of heat exchanger networks. (C) 2009 Elsevier Ltd. All rights reserved.

关键词： Cost optimization CPU time Heat exchanger network synthesis Optimum network randomized algorithm Stream-splitting

来源：评论

学校读者我要写书评

暂无评论

Fast randomized algorithm for center-detection

引用

PATTERN RECOGNITION 2010年第8期43卷 2659-2665页

作者： Chung, Kuo-Liang Huang, Yong-Huai Wang, Jyun-Pin Chang, Ting-Chin Liao, Hong-Yuan Mark Jinwen Univ Sci & Technol Inst Comp & Commun Engn Taipei 23154 Taiwan Jinwen Univ Sci & Technol Dept Elect Engn Taipei 23154 Taiwan Natl Taiwan Univ Sci & Technol Dept Comp Sci & Informat Engn Taipei 10672 Taiwan Acad Sinica Inst Informat Sci Taipei 115 Taiwan

Recently, Cauchie et al. presented an adaptive Hough transform-based algorithm to successfully solve the center-detection problem which is an important issue in many real-world problems. This paper presents a fast randomized algorithm to solve the same problem. With similar memory requirement and accuracy, the computational complexity analysis and comparison show that our proposed algorithm performs much better in terms of efficiency. We have tested our algorithm on 13 real images. Experimental results indicated that our algorithm has 38% execution-time improvement over Cauchie et al.'s algorithm. The extension of the proposed algorithm to detect multiple centers is also addressed. (C) 2010 Elsevier Ltd. All rights reserved.

关键词： Center-detection Hough transform Gradient line Multiple centers randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Diagnosis of wiring networks: An optimal randomized algorithm for finding connected components of unknown graphs

引用

SIAM JOURNAL ON COMPUTING 1999年第5期28卷 1541-1551页

作者： Shi, WP West, DB Univ N Texas Dept Comp Sci Denton TX 76203 USA Univ Illinois Dept Math Urbana IL 61801 USA

We want to find the vertex sets of components of a graph G with a known vertex set V and unknown edge set E. We learn about G by sending an oracle a query set S subset of or equal to V, and the oracle tells us the vertices connected to S. The objective is to use the minimum number of queries to partition the vertex set into components. The problem is also known as interconnect diagnosis of wiring networks in VLSI. We present a deterministic algorithm using O(min{k;lg n }) queries and a randomized algorithm using expected O(min{k, lg k + lg lg n}) queries, where n is the number of vertices and k is the number of components. We also prove matching lower bounds.

关键词： randomized algorithm lower bound fault diagnosis graph component connection class

来源：评论

学校读者我要写书评

暂无评论

A randomized algorithm for joint power and channel allocation in 5G D2D communication

引用

COMPUTER COMMUNICATIONS 2021年 179卷 22-34页

作者： Ghosal, Subhankar Ghosh, Sasthi C. Indian Stat Inst Adv Comp & Microelect Unit Kolkata 700108 India

We formulate the joint power and channel allocation problem (JPCAP) for device to device (D2D) communication as a cost minimization problem, where cost is defined as a linear combination of the number of channels used and total power requirement. We first show that JPCAP is a NP-hard problem and providing n(1/epsilon) approximation for JPCAP for all epsilon > 0 is also NP-hard. Then we propose a mixed integer linear programming (MILP) to solve this problem. As solving MILP is a NP-hard problem we propose a greedy channel and power allocation (GCPA) algorithm to assign channels and powers to the links. We design GCPA in such a fashion that there exists an order of the links for which it produces optimum solution. We show that an order is equivalent to many orders and hence design an incremental algorithm (IA) to efficiently search good orders. Finally using IA we develop a randomized joint channel and power allocation (RJCPA) algorithm. We show that if a certain condition holds we can find the optimum in expected polynomial time else a slowly growing exponential time with very high probability. We then theoretically calculate the expected cost and energy efficiency (EE) produced by RJCPA. Through simulation, we show that RJCPA outperforms two existing approaches with respect to both cost and EE significantly. Finally we validate our theoretical findings through simulation.

关键词： 5G D2D communication Joint channel and power allocation Energy efficiency Greedy algorithm randomized algorithm Expected cost

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：