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

Multidimensional Gains for Stochastic approximation

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS 2020年第5期31卷 1602-1615页

作者： Saab, Samer S. Shen, Dong Lebanese Amer Univ Dept Elect & Comp Engn Byblos 2038 Lebanon Beijing Univ Chem Technol Coll Informat Sci & Technol Beijing Peoples R China

This paper deals with iterative Jacobian-based recursion technique for the root-finding problem of the vector-valued function, whose evaluations are contaminated by noise. Instead of a scalar step size, we use an iterate-dependent matrix gain to effectively weigh the different elements associated with the noisy observations. The analytical development of the matrix gain is built on an iterative-dependent linear function interfered by additive zero-mean white noise, where the dimension of the function is $ {M\ge 1}$ and the dimension of the unknown variable is $ {N\ge 1}$ . Necessary and sufficient conditions for $ {M\ge N}$ algorithms are presented pertaining to algorithm stability and convergence of the estimate error covariance matrix. Two algorithms are proposed: one for the case where $ {M\ge N}$ and the second one for the antithesis. The two algorithms assume full knowledge of the Jacobian. The recursive algorithms are proposed for generating the optimal iterative-dependent matrix gain. The proposed algorithms here aim for per-iteration minimization of the mean square estimate error. We show that the proposed algorithm satisfies the presented conditions for stability and convergence of the covariance. In addition, the convergence rate of the estimation error covariance is shown to be inversely proportional to the number of iterations. For the antithesis $ {M< N}$ , contraction of the error covariance is guaranteed. This underdetermined system of equations can be helpful in training neural networks. Numerical examples are presented to illustrate the performance capabilities of the proposed multidimensional gain while considering nonlinear functions.

关键词： Convergence Jacobian matrices Noise measurement Covariance matrices approximation algorithms Estimation Optimization Gradient descent Newton's method noisy function measurements root finding Rosenbrock function stochastic approximation (SA) stochastic optimization variance reduction

来源：评论

学校读者我要写书评

暂无评论

Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs

引用

DISCRETE & COMPUTATIONAL GEOMETRY 2021年第4期66卷 1401-1414页

作者： Abu-Affash, A. Karim Carmi, Paz Maheshwari, Anil Morin, Pat Smid, Michiel Smorodinsky, Shakhar Shamoon Coll Engn Software Engn Dept IL-84100 Beer Sheva Israel Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel Carleton Univ Sch Comp Sci Ottawa ON Canada Ben Gurion Univ Negev Dept Math IL-84105 Beer Sheva Israel

We consider a well-studied generalization of the maximum clique problem which is defined as follows. Given a graph G on n vertices and a fixed parameter d >= 1, in the maximum diameter-bounded subgraph problem (MaxDBS for short) the goal is to find a (vertex) maximum subgraph of G of diameter at most d. For d = 1, this problem is equivalent to the maximum clique problem and thus it is NP-hard to approximate it within a factor n(1-epsilon), for any epsilon > 0. Moreover, it is known that, for any d = 2, it is NP-hard to approximate MaxDBS within a factor n(1/2-epsilon), for any epsilon > 0. In this paper we focus on MaxDBS for the class of unit disk graphs. We provide a polynomial-time constant-factor approximation algorithm for the problem. The approximation ratio of our algorithm does not depend on the diameter d. Even though the algorithm itself is simple, its analysis is rather involved. We combine tools from the theory of hypergraphs with bounded VC-dimension, k-quasi planar graphs, fractional Helly theorems, and several geometric properties of unit disk graphs.

关键词： approximation algorithms Maximum diameter-bounded subgraph Unit disk graphs Fractional Helly theorem VC-dimension

来源：评论

学校读者我要写书评

暂无评论

Seismic Image Dip Estimation by Multiscale Principal Component Analysis

引用

IEEE TRANSACTIONS ON GEOSCIENCE AND REMOTE SENSING 2023年 61卷

作者： Wu, Shaojiang Wang, Yibo Chinese Acad Sci Inst Geol & Geophys Key Lab Petr Resource Res Beijing 100029 Peoples R China Chinese Acad Sci Innovat Acad Earth Sci Beijing 100029 Peoples R China

Dip estimation of geological structures plays an important role in geophysical applications. Principal component analysis (PCA) is a common approach to estimating local dips by decomposing the local gradients of a seismic migration image and obtaining its principal eigenvector. However, PCA is difficult to obtain robust and high-resolution dip estimations for low signal-to-noise ratio (SNR) migration images, while multiscale schemes in digital image processing can achieve a better compromise between noise robustness and dip resolution. Therefore, we propose to adopt a multiscale PCA (MPCA) method coupled with a propagation-weight-based fusion mechanism for seismic dip estimation of low SNR migration image. MPCA consists of three steps: 1) constructing an image pyramid by repeating the low-pass filter from fine to coarse scales;2) estimating the dip using the PCA method at each scale of the image pyramid;and 3) fusing the multiscale dip estimations using propagation weights from coarse to fine scales. We test the MPCA method on an omnidirectional dip pattern and three seismic migration images and compare with the conventional PCA and multiscale methods. The results demonstrate that MPCA yields robust and high-resolution dip estimations for low SNR seismic migration images.

关键词： Estimation Principal component analysis Signal to noise ratio Image resolution Tensors Low-pass filters Mathematical models approximation algorithms estimation inverse problems mathematical model reliability

来源：评论

学校读者我要写书评

暂无评论

Tight Localizations of Feedback Sets

引用

ACM Journal of Experimental Algorithmics 2021年第PP1–19期26卷 1–19页

作者： Hecht, Michael Gonciarz, Krzysztof Horvát, Szabolcs Max Planck Institute of Molecular Cell Biology and Genetics Center for Systems Biology Dresden Germany Max Planck Institute for the Physics of Complex Systems Dresden Germany

The classical NP-hard feedback arc set problem (FASP) and feedback vertex set problem (FVSP) ask for a minimum set of arcs ϵ ⊆ E or vertices ν ⊆ V whose removal G ∖ ϵ, G ∖ ν makes a given multi-digraph G=(V, E) acyclic, respectively. Though both problems are known to be APX-hard, constant ratio approximations or proofs of inapproximability are unknown. We propose a new universal O(|V||E|4)-heuristic for the directed FASP. While a ratio of r ≈ 1.3606 is known to be a lower bound for the APX-hardness, at least by empirical validation we achieve an approximation of r ≤ 2. Most of the relevant applications, such as circuit testing, ask for solving the FASP on large sparse graphs, which can be done efficiently within tight error bounds with our approach. © 2021 Owner/Author.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Minimum Cost Feedback Selection in Structured Systems: Hardness and approximation Algorithm

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2020年第12期65卷 5517-5524页

作者： Joshi, Aishwary Moothedath, Shana Chaporkar, Prasanna QE Secur LLP Gurugram 122002 India Univ Washington Seattle WA 98195 USA Indian Inst Technol Dept Elect Engn Mumbai 400076 Maharashtra India

This article deals with output feedback selection in linear time-invariant structured systems. We assume that the inputs and the outputs are dedicated, i.e., each input directly actuates a single state and each output directly senses a single state. Given a structured system with dedicated inputs and outputs and a cost matrix that denotes the cost of each feedback connection, our aim is to select a minimum cost set of feedback connections such that the closed-loop system satisfies arbitrary pole-placement. This problem is referred to as the optimal feedback selection problem for dedicated i/o. The optimal feedback selection problem for dedicated i/o is NP-hard and inapproximable to a constant factor of log n, where n denotes the system dimension. To this end, we propose an algorithm to find an approximate solution to the problem. The proposed algorithm consists of a potential function incorporated with a greedy scheme and attains a solution with a guaranteed approximation ratio. We consider two special network topologies of practical importance, referred to as back-edge feedback structure and hierarchical networks. For the first case, which is NP-hard and inapproximable to a multiplicative factor of log n, we provide a logn-approximate solution. For hierarchical networks, we give a dynamic programming based algorithm to obtain an optimal solution in polynomial time.

关键词： approximation algorithms Optimization Closed loop systems Dynamic programming Heuristic algorithms Dynamical systems Linear systems Arbitrary pole-placement hierarchical networks linear dynamical systems minimum cost feedback selection

来源：评论

学校读者我要写书评

暂无评论

A 16-Channel 60μW Neural Synchrony Processor for Multi-Mode Phase-Locked Neurostimulation 43

A 16-Channel 60μW Neural Synchrony Processor for Multi-Mode...

引用

43rd Annual IEEE Custom Integrated Circuits Conference, CICC 2022

作者： Shin, Uisub Ding, Cong Somappa, Laxmeesha Woods, Virginia Widge, Alik S. Shoaran, Mahsa EPFL Lausanne Switzerland Cornell University IthacaNY United States University of Minnesota MinneapolisMN United States

ISBN: (纸本)9781665407564

Measuring neural oscillatory synchrony facilitates our understanding of complex brain networks and the underlying pathological states. Altering the cross-regional synchrony-as a measure of brain network connectivity-via phase-locked deep brain stimulation (DBS) could provide a new therapeutic solution for various neurological [1] and psychiatric disorders [2]. This feature is missing in current neuromodulation devices and requires an accurate, energy-efficient computation of oscillatory phase and cross-regional synchrony on chip. The conventional iterative vector processing approach via CORDIC [3] can accurately extract the instantaneous phase and phase locking value (PLV) at the cost of high power consumption (400μW). As a result, it cannot be applied to large-scale (>100-CH) neuronal networks. Moreover, the latency in the pipelined CORDIC processor may hinder timely phase-locked stimulation in the absence of an excessively high clock speed. Alternatively, the PLV extractors in [4], [5] utilized simple approximation algorithms such as 1-bit quantization and local minima detection. These methods, albeit efficient, compromise PLV accuracy and cannot extract the instantaneous phase of neuronal signals. To provide an efficient, flexible, and accurate phase-locked DBS platform, this paper integrates a 16-channel low-noise AFE, an energy-efficient multi-mode phase synchrony processor, and a 4-channel neurostimulator that is locked to specific neuronal oscillatory phases (i.e., fixed or random phase, PLV or PAC). An amplitude-locked control can be further enabled through envelope and multi-band spectral energy extraction for common use cases such as epilepsy. © 2022 IEEE.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults 18

Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faul...

引用

18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022

作者： Adjiashvili, David Hommelsheim, Felix Mühlenthaler, Moritz Schaudt, Oliver Department of Mathematics ETH Zürich Switzerland Department of Mathematics and Computer Science Universität Bremen Germany Laboratoire G-SCOP Grenoble INP Univ. Grenoble-Alpes France Department of Mathematics RWTH Aachen University Germany

ISBN: (纸本)9783959772365

The Edge-disjoint s-t Paths Problem (s-t EDP) is a classical network design problem whose goal is to connect for some k ≥ 1 two given vertices of a graph under the condition that any k - 1 edges of the graph may fail. We extend the simple uniform failure model of the s-t EDP as follows: the edge set of the graph is partitioned into vulnerable, and safe edges, and a set of at most k vulnerable edges may fail, while safe edges do not fail. In particular we study the Fault-Tolerant Path (FTP) problem, the counterpart of the Shortest s-t Path problem in this non-uniform failure model as well as the Fault-Tolerant Flow (FTF) problem, the counterpart of s-t EDP. We present complexity results alongside exact and approximation algorithms for both problems. We emphasize the vast increase in complexity of the problems compared to s-t EDP. © 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

A tight bound for stochastic submodular cover

引用

Journal of Artificial Intelligence Research 2021年 71卷 347-370页

作者： Hellerstein, Lisa Kletenik, Devorah Parthasarathy, Srinivasan Dept. of Computer Science and Engineering NYU Tandon School of Engineering BrooklynNY11201 United States Dept. of Computer and Information Science Brooklyn College City University of New York BrooklynNY11210 United States IBM T. J. Watson Research Center Yorktown HeightsNY10598 United States

We show that the Adaptive Greedy algorithm of Golovin and Krause achieves an approximation bound of (ln(Q/η)+1) for Stochastic Submodular Cover: here Q is the "goal value" and η is the minimum gap between Q and any attainable utility value Q02. A bound of 56(ln(Q/η)+1) is implied by work of Im et al. Other bounds for the problem depend on quantities other than Q and η. Our bound restores the original bound claimed by Golovin and Krause, generalizing the well-known (ln m+1) approximation bound on the greedy algorithm for the classical Set Cover problem, where m is the size of the ground set. © 2021 AI Access Foundation. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

On the geometric priority set cover problem

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2023年 112卷

作者： Banik, Aritra Raman, Rajiv Ray, Saurabh HBNI Natl Inst Sci Educ & Res Bhubaneswar India Univ Clermont Auvergne Clermont Auvergne INP CNRS Mines St EtienneLIMOS F-63000 Clermont Ferrand France NYU Abu Dhabi Abu Dhabi U Arab Emirates

We study the priority set cover problem for simple geometric set systems in the plane. For pseudo-halfspaces in the plane we obtain a PTAS via local search by showing that the corresponding set system admits a planar support. We show that the problem is APX-hard even for unit disks in the plane and argue that in this case the standard local search algorithm can output a solution that is arbitrarily bad compared to the optimal solution. We then present an LP-relative constant factor approximation algorithm (which also works in the weighted setting) for unit disks via quasi-uniform sampling. As a consequence we obtain a constant factor approximation for the capacitated set cover problem with unit disks. For arbitrary size disks, we show that the problem is at least as hard as the vertex cover problem in general graphs even when the disks have nearly equal sizes. We also present a few simple results for unit squares and orthants in the plane. (c) 2023 Elsevier B.V. All rights reserved.

关键词： approximation algorithms Geometric set cover Local search Quasi-uniform sampling

来源：评论

学校读者我要写书评

暂无评论

Locating Service and Charging Stations 1

引用

20th International Workshop on approximation and Online algorithms, WAOA 2022

作者： Dabas, Rajni Garg, Naveen Gupta, Neelima Kaur, Dilpreet Department of Computer Science University of Delhi New Delhi India Indian Institute of Technology Delhi New Delhi India

ISBN: (数字)9783031183676

ISBN: (纸本)9783031183669

In this paper, we consider the problem of locating service and charging stations to serve commuters. In the service station location problem we are given the paths followed by m clients and wish to locate k service stations, from a set of feasible locations, such that the maximum detour that a client has to take is minimized. We give a solution that has a maximum detour 3 OPT+ L where L is the length of the longest client-path. Electric vehicles have a limited range and charging stations need to be located so that a client can drive from the source to destination without running out of charge. We consider two variants of the problem. In the first, we are given only the source and destination of each client and have to locate facilities at some subset of locations such that every client has a feasible path. In the second variant, we are also given the path that a client wishes to take and have to locate the facilities such that each client can follow its path without any detours. For both problems, our objective is to minimize the number of charging stations. For all three problems, when the underlying graph is a tree and the facility can be located at any vertex on the tree, we show that the problem can be solved in polynomial time. On general graphs, the problem with source-destination pairs is at least as hard as the node-weighted group-Steiner tree but if we allow vehicles in our solution to have a range of 4 times that of the optimum then we obtain an 8-approximation. For the problem with specified paths, we show that finding an o(log m) approximation is hard even when vehicles of our solution have a range that is a constant times larger than that of the optimum solution. © 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：