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

Image Enhancement Based on Histogram-Guided Multiple Transformation Function Estimation

IEEE TRANSACTIONS ON CONSUMER ELECTRONICS 2024年第4期70卷 6664-6678页

作者： Park, Jaemin Vien, An Gia Pham, Thuy Thi Kim, Hanul Lee, Chul Dongguk Univ Dept Multimedia Engn Seoul 04620 South Korea LIG Co Ltd NEX1 EO IR Syst Res & Dev Team Yongin 16911 Gyeonggi South Korea Huawei Technol Ltd Tampere 33100 Finland MoMo Co Ho Chi Minh City 700000 Vietnam Seoul Natl Univ Sci & Technol Dept Appl Artificial Intelligence Seoul 01811 South Korea

Although recent deep learning-based algorithms have achieved significant performance improvements in various image enhancement tasks, most approaches have been developed using image-to-image translation, which is challenging to interpret and analyze the enhancement processes. Several attempts have been made to use the image-to-transformation function approach for better interpretability;however, they often fail to generate complex color mappings, degrading image quality. In this work, we develop a novel transformation function-based algorithm that estimates multiple transformation functions with different properties by exploiting both the spatial and statistical characteristics of the input image to describe complex color mapping. First, we extract the image features that capture spatial information, considering their channel correlations. Next, we estimate multiple transformation functions utilizing a cross-attention block to capture the relevance between spatial and statistical information in the input image and its histogram, respectively. We then estimate the weight maps indicating the pixel-wise contribution of each transformation function by exploiting the spatial correlation between the input and transformed images obtained by each transformation function. Finally, we obtain an enhanced image by taking the weighted sum of the transformed images and the corresponding weight maps. Experimental results demonstrate that the proposed algorithm outperforms state-of-the-art algorithms on various image enhancement tasks.

关键词： Image color analysis Image enhancement Feature extraction Histograms Correlation Lighting approximation algorithms Reflectivity Consumer electronics Brightness multiple transformation functions cross-attention histogram color representation

来源：评论

学校读者我要写书评

暂无评论

αi -Metric Graphs: Radius, Diameter and all Eccentricities

引用

ALGORITHMICA 2024年第7期86卷 2092-2129页

作者： Dragan, Feodor F. Ducoffe, Guillaume Kent State Univ Comp Sci Dept Kent OH 44240 USA Natl Inst Res & Dev Informat Bucharest Romania Univ Bucharest Bucharest Romania

We extend known results on chordal graphs and distance-hereditary graphs to much larger graph classes by using only a common metric property of these graphs. Specifically, a graph is called alpha(i)-metric (i is an element of N) if it satisfies the following alpha(i)-metric property for every vertices u, w, v and x: if a shortest path between u and w and a shortest path between x and v share a terminal edge vw, then d(u,x) >= d(u,v)+d(v,x)-i. Roughly, gluing together any two shortest paths along a common terminal edge may not necessarily result in a shortest path but yields a "near-shortest" path with defect at most i. It is known that alpha 0-metric graphs are exactly ptolemaic graphs, and that chordal graphs and distance-hereditary graphs are alpha i-metric for i=1 and i=2,respectively. We show that an additive O(i)-approximation of the radius, of the diameter, and in fact of all vertex eccentricities of an alpha(i)-metric graph can be computed in total linear time. Our strongest results are obtained for alpha(1)-metric graphs, for which we prove that a central vertex can be computed in subquadratic time, and even better in linear time for so-called (alpha(1),Delta)-metric graphs (a superclass of chordal graphs and of plane triangulations with inner vertices of degree at least 7). The latter answers a question raised in Dragan (Inf Probl Lett 154:105873, 2020), 2020). Our algorithms follow from new results on centers and metric intervals of alpha i-metric graphs. In particular, we prove that the diameter of the center is at most 3i+2 (at most 3, if i=1).The latter partly answers a question raised in Yushmanov and Chepoi (Math ProblCybernet 3:217-232, 1991)

关键词： Metric graph classes Chordal graphs alpha(i) -metric Radius Diameter Vertex eccentricity Eccentricity approximating trees approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Budgeted Sequence Submodular Maximization With Uniform and Non-Uniform Costs

引用

IEEE TRANSACTIONS ON EMERGING TOPICS IN COMPUTATIONAL INTELLIGENCE 2024年第1期8卷 503-518页

作者： Chen, Xuefeng Feng, Liang Cao, Xin Zeng, Yifeng Hou, Yaqing Zhang, Zhi Chongqing Univ Coll Comp Sci Chongqing 400044 Peoples R China Univ New South Wales Sch Comp Sci & Engn Sydney NSW 2052 Australia Northumbria Univ Dept Comp & Informat Sci Newcastle Upon Tyne NE1 8ST England Dalian Univ Technol Sch Comp Sci & Technol Dalian 116024 Peoples R China

The problem of picking a sequence of items that maximizes a given submodular function over the item sequence exists in many practical applications. Existing studies on this problem only consider uniform costs on items. However, it is more general that items have non-uniform costs. Taking this cue, in this article, we study the problem of budgeted sequence submodular maximization (BSSM), which considers both uniform and non-uniform item costs in the sequence selection. This problem widely appears in many applications such as movie recommendation and course learning. For BSSM with uniform costs, we first prove a new approximation ratio for an existing algorithm OMEGA, and then propose an anytime randomized iterative algorithm POBM which converges faster than a state-of-the-art method POSEQSEL in obtaining approximate solutions. We also develop some optimization techniques for improving the efficiency of POBM. For BSSM with non-uniform costs, we design a greedy algorithm GBM with a guaranteed error bound, and prove that POBM can find approximate solutions in a reasonable time. The results of the experimental study on both synthetic and real datasets demonstrate the excellent performance of our algorithms.

关键词： Costs Optimization Motion pictures Greedy algorithms Iterative methods Computational intelligence approximation algorithms Sequence submodular maximization submodular optimization evolutionary optimization theoretical analysis experimental study

来源：评论

学校读者我要写书评

暂无评论

Yet Another Self-Stabilizing Minimum Vertex Cover of a Network With Stochastic Stability

引用

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS 2024年第4期11卷 2226-2238页

作者： Chen, Jie Zhou, Rongpei Natl Univ Def Technol Coll Elect Engn Hefei 230037 Peoples R China Nanchang Univ Sch Informat Engn Nanchang 330036 Peoples R China

The vertex covering of a network is one of the well-known combinatorial optimization problems, and the focal point in the perspective of autonomous intelligent systems is to achieve the optimal covering solutions with distributed local information by the nodes (individual systems) themselves. In this article, we utilize a potential game for the vertex cover problem, whose solutions to the minimum value of its global objective function are the minimum vertex covering states of a network, and newly propose a self-stabilizing-parallel-game-based (SPG) distributed algorithm for each vertex (player) to learn (update) its strategy parallelly with the local information. Under the proposed SPG algorithm, we prove that only the solutions to the minimum value of the potential game's global objective function are stochastically stable, and the covering strategies of all the players will converge with probability one to a stochastically stable state, which is beyond the general Nash equilibrium of vertex covering games in the literature. Furthermore, we estimate the convergence rate of the proposed SPG algorithm, and extensive samples with numerical examples verify the effectiveness and superiority of the proposed SPG algorithm on a variety of representative complex networks with different scales and standard benchmarks.

关键词： Optimization approximation algorithms Heuristic algorithms Games Linear programming Nash equilibrium Convergence Convergence rate minimum vertex cover parallel game based potential game self-stabilizing stochastically stable

来源：评论

学校读者我要写书评

暂无评论

Redundancy-Free and Load-Balanced TGNN Training With Hierarchical Pipeline Parallelism

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2024年第11期35卷 1904-1919页

作者： Xia, Yaqi Zhang, Zheng Yang, Donglin Hu, Chuang Zhou, Xiaobo Chen, Hongyang Sang, Qianlong Cheng, Dazhao Wuhan Univ Sch Comp Sci Wuhan 430072 Hubei Peoples R China Nvidia Corp Santa Clara CA 95051 USA Univ Macau IOTSC Macau 999078 Peoples R China Univ Macau Dept Comp & Informat Sci Macau 999078 Peoples R China Zhejiang Lab Res Ctr Graph Comp Hangzhou 311100 Peoples R China

Recently, Temporal Graph Neural Networks (TGNNs), as an extension of Graph Neural Networks, have demonstrated remarkable effectiveness in handling dynamic graph data. Distributed TGNN training requires efficiently tackling temporal dependency, which often leads to excessive cross-device communication that generates significant redundant data. However, existing systems are unable to remove the redundancy in data reuse and transfer, and suffer from severe communication overhead in a distributed setting. This work introduces Sven, a co-designed algorithm-system library aimed at accelerating TGNN training on a multi-GPU platform. Exploiting dependency patterns of TGNN models, we develop a redundancy-free graph organization to mitigate redundant data transfer. Additionally, we investigate communication imbalance issues among devices and formulate the graph partitioning problem as minimizing the maximum communication balance cost, which is proved to be an NP-hard problem. We propose an approximation algorithm called Re-FlexBiCut to tackle this problem. Furthermore, we incorporate prefetching, adaptive micro-batch pipelining, and asynchronous pipelining to present a hierarchical pipelining mechanism that mitigates the communication overhead. Sven represents the first comprehensive optimization solution for scaling memory-based TGNN training. Through extensive experiments conducted on a 64-GPU cluster, Sven demonstrates impressive speedup, ranging from 1.9x to 3.5x, compared to State-of-the-Art approaches. Additionally, Sven achieves up to 5.26x higher communication efficiency and reduces communication imbalance by up to 59.2%.

关键词： Training Graph neural networks Pipeline processing Partitioning algorithms Heuristic algorithms approximation algorithms Task analysis Communication balance distributed training dynamic GNN pipeline parallelism redundancy-free

来源：评论

学校读者我要写书评

暂无评论

Finer-Grained Reductions in Fine-Grained Hardness of approximation 51

Finer-Grained Reductions in Fine-Grained Hardness of Approxi...

引用

51st International Colloquium on Automata, Languages, and Programming, ICALP 2024

作者： Abboud, Elie Ron-Zewi, Noga Department of Computer Science University of Haifa Israel

ISBN: (纸本)9783959773225

We investigate the relation between δ and ϵ required for obtaining a (1 + δ)-approximation in time N2−ϵ for closest pair problems under various distance metrics, and for other related problems in fine-grained complexity. Specifically, our main result shows that if it is impossible to (exactly) solve the (bichromatic) inner product (IP) problem for vectors of dimension c log N in time N2−ϵ, then there is no (1 + δ)approximation algorithm for (bichromatic) Euclidean Closest Pair running in time N2−2ϵ, where δ ≈ (ϵ/c)2 (where ≈ hides polylog factors). This improves on the prior result due to Chen and Williams (SODA 2019) which gave a smaller polynomial dependence of δ on ϵ, on the order of δ ≈ (ϵ/c)6. Our result implies in turn that no (1 + δ)-approximation algorithm exists for Euclidean closest pair for δ ≈ ϵ4, unless an algorithmic improvement for IP is obtained. This in turn is very close to the approximation guarantee of δ ≈ ϵ3 for Euclidean closest pair, given by the best known algorithm of Almam, Chan, and Williams (FOCS 2016). By known reductions, a similar result follows for a host of other related problems in fine-grained hardness of approximation. Our reduction combines the hardness of approximation framework of Chen and Williams, together with an MA communication protocol for IP over a small alphabet, that is inspired by the MA protocol of Chen (Theory of Computing, 2020). © Elie Abboud and Noga Ron-Zewi.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for Rank-Regret Minimization

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2024年第8期36卷 3801-3816页

作者： Xiao, Xingxing Li, Jianzhong Harbin Inst Technol Dept Comp Sci & Technol Harbin 150001 Peoples R China Chinese Acad Sci Shenzhen Inst Adv Technol Fac Comp Sci & Control Engn Shenzhen 518000 Peoples R China

Multi-criteria decision-making usually requires finding a small representative set from the database. A popular method, the regret minimization set (RMS) query, returns a size r subset S of the full dataset $D$D that minimizes the regret-ratio (the difference between the scores of top-1 in S and top-1 in D, for any utility function). RMS is not shift invariant, causing inconsistency in results. Further, the regret-ratio is often a "made up" number and users may mistake its absolute value. Instead, users do understand the notion of rank. Therefore, in this paper, we consider finding a fixed-size set S to minimize the maximum rank-regret (the rank of top-1 of S in the sorted list of D) over all possible utility functions, called the rank-regret minimization (RRM) problem, which is shift invariant. In 2D space, we design an exact algorithm 2DRRM for RRM. In HD space, we propose an approximate algorithm HDRRM with theoretical guarantees on rank-regret. It combines the ideas of space discretization and clustering. Extensive experiments verify the efficiency and effectiveness of our algorithms. In particular, HDRRM always has the best output quality in experiments.

关键词： Automobiles Databases approximation algorithms Minimization Clustering algorithms Logistics Decision making Multi-criteria decision-making rank-regret regret-ratio skyline top-k query

来源：评论

学校读者我要写书评

暂无评论

Transmission Design for Intelligent Reflecting Surface-Aided MIMO SWIPT Systems With Finite-Alphabet Inputs

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2024年第5期72卷 3095-3109页

作者： Zhu, Xiaodong Liu, Zhen Shi, Yuzhong Di, Haoyang Meng, Zhonglou Tu, Xiaodong Univ Elect Sci & Technol China Sch Informat & Commun Engn Chengdu 611731 Peoples R China

This paper investigates the transmission design for an intelligent reflecting surface (IRS)-aided simultaneous wireless information and power transfer (SWIPT) system, where the base station (BS), information decoding receiver (IDR), and energy harvesting receiver (EHR) are equipped with multiple antennas. The IRS can facilitate the transmission of information and the acquisition of energy by regulating its reflection phase shifts. By jointly optimizing the transmit precoder at the BS and the phase shifts of the IRS, our goal is to maximize the mutual information (MI) between the BS and the IDR subject to the constraints of the transmit power at the BS and the harvested energy at the EHR. Unlike existing works, where ideal Gaussian signals are assumed to be the inputs, this paper considers the actual scenario of finite-alphabet signals, such as phase shift keying (PSK) and quadrature amplitude modulation (QAM), as the input signals. To facilitate the solution of this optimization problem, we use the channel cutoff rate (CR) as a surrogate for MI. By doing this, the original problem of MI maximization is transformed into an approximate equivalent problem of CR maximization. Two cases, where perfect or imperfect channel state information (CSI) is available at the BS, are both considered. The formulated problems in the two cases are intractable due to the non-convexity and variable coupling. However, by analyzing the structure of the problems, for each CSI case, we develop a corresponding solution algorithm based on alternating optimization. For the perfect CSI case, the algorithm combines successive convex approximation (SCA) with penalty-based manifold optimization, while, for the imperfect CSI case, the algorithm is involved with SCA, S-Procedure, and semidefinite relaxation (SDR). Both the solution algorithms can be utilized to effectively optimize the precoder and the phase shifts, whose superiority is well verified by simulation results.

关键词： MIMO communication Optimization Wireless communication Receivers Quadrature amplitude modulation Phase shift keying approximation algorithms Intelligent reflecting surface (IRS) simultaneous wireless information and power transfer (SWIPT) multiple-input multiple-output (MIMO) finite-alphabet inputs transmission design

来源：评论

学校读者我要写书评

暂无评论

Deep Neural Network approximations for the Stable Manifolds of the Hamilton-Jacobi-Bellman Equations

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2024年第10期69卷 7239-7246页

作者： Chen, Guoyuan Zhejiang Univ Finance & Econ Sch Data Sci Hangzhou 310018 Peoples R China

For an infinite-horizon control problem, the optimal control can be represented by the stable manifold of the characteristic Hamiltonian system of Hamilton-Jacobi-Bellman (HJB) equation in a semiglobal domain. In this article, we first theoretically prove that if an approximation is sufficiently close to the exact stable manifold of the HJB equation in a certain sense, then the control derived from this approximation stabilizes the system and is nearly optimal. Then, based on the theoretical result, we propose a deep learning algorithm to approximate the stable manifold and compute optimal feedback control numerically. The algorithm relies on adaptive data generation through finding trajectories randomly within the stable manifold. Such kind of algorithm is grid-free basically, making it potentially applicable to a wide range of high-dimensional nonlinear systems. We demonstrate the effectiveness of our method through two examples: Stabilizing the Reaction Wheel Pendulums and controlling the parabolic Allen-Cahn equation.

关键词： Manifolds approximation algorithms Trajectory Optimal control Artificial neural networks Deep learning Mathematical models Deep neural network Hamilton-Jacobi-Bellman (HJB) equation optimal control stable manifold

来源：评论

学校读者我要写书评

暂无评论

SubLinearForce: Fully Sublinear-Time Force Computation for Large Complex Graph Drawing

引用

IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS 2024年第7期30卷 3386-3399页

作者： Meidiana, Amyra Hong, Seok-Hee Cai, Shijun Torkel, Marnijati Eades, Peter Univ Sydney Sydney NSW 2006 Australia

Recent works in graph visualization attempt to reduce the runtime of repulsion force computation of force-directed algorithms using sampling. However, they fail to reduce the runtime for attraction force computation to sublinear in the number of edges. We present the SubLinearForce framework for a fully sublinear-time force computation algorithm for drawing large complex graphs. More precisely, we present new sublinear-time algorithms for the attraction force computation of force-directed algorithms. We then integrate them with sublinear-time repulsion force computation to give a fully sublinear-time force computation. Extensive experiments show that our algorithms compute layouts on average 80% faster than the existing linear-time force computation algorithm, while obtaining significantly better quality metrics such as edge crossing and shape-based metrics.

关键词： Force Runtime Measurement Resistance approximation algorithms Springs Scalability Graph drawing force-directed algorithms sublinear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：