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

Beyond symmetry: best submatrix selection for the sparse truncated SVD

MATHEMATICAL PROGRAMMING 2024年第1-2期208卷 1-50页

作者： Li, Yongchun Xie, Weijun Georgia Inst Technol Atlanta GA 30332 USA

The truncated singular value decomposition (SVD), also known as the best low-rank matrix approximation with minimum error measured by a unitarily invariant norm, has been applied to many domains such as biology, healthcare, among others, where high-dimensional datasets are prevalent. To extract interpretable information from the high-dimensional data, sparse truncated SVD (SSVD) has been used to select a handful of rows and columns of the original matrix along with the best low-rank approximation. Different from the literature on SSVD focusing on the top singular value or compromising the sparsity for the seek of computational efficiency, this paper presents a novel SSVD formulation that can select the best submatrix precisely up to a given size to maximize its truncated Ky Fan norm. The fact that the proposed SSVD problem is NP-hard motivates us to study effective algorithms with provable performance guarantees. To do so, we first reformulate SSVD as a mixed-integer semidefinite program, which can be solved exactly for small- or medium-sized instances within a branch-and-cut algorithm framework with closed-form cuts and is extremely useful for evaluating the solution quality of approximation algorithms. We next develop three selection algorithms based on different selection criteria and two searching algorithms, greedy and local search. We prove the approximation ratios for all the approximation algorithms and show that all the ratios are tight when the number of rows or columns of the selected submatrix is no larger than half of the data matrix, i.e., our derived approximation ratios are unimprovable. Our numerical study demonstrates the high solution quality and computational efficiency of the proposed algorithms. Finally, all our analysis can be extended to row-sparse PCA.

关键词： Sparse truncated SVD Mixed-integer semidefinite program Branch-and-cut algorithm approximation algorithms Row-sparse PCA

来源：评论

学校读者我要写书评

暂无评论

Low Complexity Turbo SIC-MMSE Detection for Orthogonal Time Frequency Space Modulation

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2024年第6期72卷 3169-3183页

作者： Li, Qi Yuan, Jinhong Qiu, Min Li, Shuangyang Xie, Yixuan Univ New South Wales Sch Elect Engn & Telecommun Sydney NSW 2052 Australia Tech Univ Berlin D-10623 Berlin Germany

Recently, orthogonal time frequency space (OTFS) modulation has garnered considerable attention due to its robustness against doubly-selective wireless channels. In this paper, we propose a low-complexity iterative successive interference cancellation based minimum mean squared error (SIC-MMSE) detection algorithm for zero-padded OTFS (ZP-OTFS) modulation. In the proposed algorithm, signals are detected based on layers processed by multiple SIC-MMSE linear filters for each sub-channel, with interference on the targeted signal layer being successively canceled either by hard or soft information. To reduce the complexity of computing individual layer filter coefficients, we also propose a novel filter coefficients recycling approach in place of generating the exact form of MMSE filter weights. Moreover, we design a joint detection and decoding algorithm for ZP-OTFS to enhance error performance. Compared to the conventional SIC-MMSE detection, our proposed algorithms outperform other linear detectors, e.g., maximal ratio combining (MRC), for ZP-OTFS with up to 3 dB gain while maintaining comparable computation complexity.

关键词： Detectors Modulation Receivers approximation algorithms Time-frequency analysis Symbols Wireless communication OTFS detection SIC-MMSE SISO turbo equalization

来源：评论

学校读者我要写书评

暂无评论

An approximation Algorithm for Covering Vertices by 4+ -Paths 16th

An Approximation Algorithm for Covering Vertices by 4+ -Pat...

引用

16th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2023

作者： Gong, Mingyang Chen, Zhi-Zhong Lin, Guohui Wang, Lusheng University of Alberta Edmonton Canada Tokyo Denki University Saitama Japan City University of Hong Kong Hong Kong

ISBN: (纸本)9783031496103

This paper deals with the problem of finding a collection of vertex-disjoint paths in a given graph G= (V, E) such that each path has at least four vertices and the total number of vertices in these paths is maximized. The problem is NP-hard and admits an approximation algorithm which achieves a ratio of 2 and runs in O(| V|8) time. The known algorithm is based on time-consuming local search, and its authors ask whether one can design a better approximation algorithm by a completely different approach. In this paper, we answer their question in the affirmative by presenting a new approximation algorithm for the problem. Our algorithm achieves a ratio of 1.874 and runs in O(min { | E|2| V|2, | V|5} ) time. Unlike the previously best algorithm, ours starts with a maximum matching M of G and then tries to transform M into a solution by utilizing a maximum-weight path-cycle cover in a suitably constructed graph. © 2024, The Author(s), under exclusive license to Springer Nature Switzerland AG.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Fault-Tolerant Optimal Consensus for Multiagent Systems: A Fuzzy-Based Game Approach

引用

IEEE TRANSACTIONS ON AEROSPACE AND ELECTRONIC SYSTEMS 2024年第5期60卷 6839-6852页

作者： Yang, Haoyue Zhang, Hao Wang, Zhuping Huang, Chao Yan, Huaicheng Tongji Univ Coll Elect & Informat Engn Shanghai 200092 Peoples R China Tongji Univ Shanghai Inst Intelligent Sci & Technol Shanghai 200092 Peoples R China East China Univ Sci & Technol Sch Informat Sci & Engn Shanghai 200237 Peoples R China

This article investigates the fault-tolerant optimal consensus problem of nonlinear discrete-time leader-following multiagent systems via nonzero-sum graphical games. First, a stochastic actuator fault model considering actuator effectiveness loss is established on account of semi-Markov processes under discrete-time settings, which can cover the existing multiplicative actuator fault models and is more general. Considering the multimodality of stochastic actuator faults, the cost function of each agent is reconstructed by combining semi-Markov kernel and weighted sum approach. By the optimality principle as well as the discrete-time Bellman equation, the hybrid policy-value iteration algorithm is developed to seek the Nash equilibrium of multiagent nonzero-sum games, which integrates the advantages of policy iteration and value iteration algorithms and can improve the convergence performance of both. Then, we propose the fault-tolerant optimal controller based on the projection estimation approach. The convergence of the iterative algorithm, as well as the uniformly ultimately boundedness for the tracking error and the estimation error of fault parameters are proved, respectively. Moreover, the generalized fuzzy hyperbolic model is adopted to implement approximately the proposed hybrid policy-value iteration algorithm, which can reduce the number of updated weights and the computational burden. Finally, two simulation examples are provided to justify the effectiveness of the presented approach.

关键词： Actuators Multi-agent systems Circuit faults Games Fault tolerant systems Fault tolerance approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

UAV Path Planning Based on the Average TD3 Algorithm With Prioritized Experience Replay

引用

IEEE ACCESS 2024年 12卷 38017-38029页

作者： Luo, Xuqiong Wang, Qiyuan Gong, Hongfang Tang, Chao Changsha Univ Sci & Technol Sch Math & Stat Changsha 410114 Peoples R China Changsha Univ Sci & Technol Sch Comp & Commun Engn Changsha Peoples R China

Path planning is one of the important components of the Unmanned Aerial Vehicle (UAV)mission, and it is also the key guarantee for the successful completion of the UAV's mission. The traditionalpath planning algorithm has certain limitations and deficiencies in the complex dynamic *** at the dynamic complex obstacle environment, this paper proposes an improved TD3 algorithm,which enables the UAV to complete the autonomous path planning through online learning and continuoustrial and error. The algorithm changes the experience pool of TD3 algorithm to priority experience replay,so that the agent can distinguish the importance of empirical samples, improve the sampling efficiency ofthe algorithm, and reduce the training time. The average TD3 is proposed, and the average value ofQ1Q2is taken when the target value is updated to solve the problem of overestimating theQvalue while avoidingunderestimating theQvalue, so that the improved algorithm has better stability and can adapt to variouscomplex obstacle environments. A new reward function is set up, so that each step of the UAV action canreceive reward feedback, which solves the problem of sparse reward in deep reinforcement learning. Theexperimental results show that this method can train the UAV to reach the target safely and quickly in amulti-obstacle environment. Compared with DDPG, SAC and traditional TD3, the path planning successrate of this algorithm is higher than that of the other three algorithms, and the collision rate is lower than thatof the comparison algorithm, which has better path planning performance

关键词： Autonomous aerial vehicles Path planning Heuristic algorithms Training approximation algorithms Machine learning algorithms Stability analysis Deep reinforcement learning Vehicle dynamics Performance evaluation UAV path planning deep reinforcement learning prioritized experience replay average TD3 algorithm

来源：评论

学校读者我要写书评

暂无评论

Moving Average-Based Variable Projection for Separable Nonlinear Problems

引用

IEEE SIGNAL PROCESSING LETTERS 2025年 32卷 1900-1904页

作者： Xue, Peng Gan, Min Yuan, Fang Chen, Guang-Yong Chen, C. L. Philip Fuzhou Univ Coll Comp Sci & Big Data Fuzhou 350116 Peoples R China Qingdao Univ Coll Comp Sci & Technol Qingdao 266071 Peoples R China South China Univ Technol Sch Comp Sci & Engn Guangzhou 510006 Peoples R China

The identification of separable nonlinear models, prevalent in tasks such as signal analysis, image processing, time series analysis, and machine learning, presents a non-convex optimization challenge that necessitates the development of efficient identification algorithms. The Variable Projection (VP) algorithm has been proven to be quite effective for addressing these problems;however, traditional VP relying on the Hessian matrix and its inverse are highly time-consuming and unsuitable for complex, large-scale applications. This letter introduces a novel approach that employs the exponential moving average of gradient and gradient estimation bias to indirectly estimate the curvature of the objective landscape, proposing a Moving Average-based Variable Projection method (MAVP). The proposed algorithm utilizes only gradient information and can properly tackle the coupling relationships between different parameters during the optimization process, thereby achieving faster convergence. Numerical results on nonlinear time series analysis and image reconstruction demonstrate that the MAVP algorithm exhibits significant efficiency and effectiveness.

关键词： Optimization Signal processing algorithms Couplings approximation algorithms Jacobian matrices Convergence Estimation Vectors Machine learning algorithms Linear programming Separable nonlinear optimization problem variable projection system identification

来源：评论

学校读者我要写书评

暂无评论

Gradient Coding With Iterative Block Leverage Score Sampling

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2024年第9期70卷 6639-6664页

作者： Charalambides, Neophytos Pilanci, Mert Hero, Alfred O. Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48109 USA Univ Calif San Diego Dept Comp Sci & Engn San Diego CA 92093 USA Univ Calif San Diego Halicioglu Data Sci Inst San Diego CA 92093 USA Stanford Univ Dept Elect Engn Stanford CA 94305 USA Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48109 USA

Gradient coding is a method for mitigating straggling servers in a centralized computing network that uses erasure-coding techniques to distributively carry out first-order optimization methods. Randomized numerical linear algebra uses randomization to develop improved algorithms for large-scale linear algebra computations. In this paper, we propose a method for distributed optimization that combines gradient coding and randomized numerical linear algebra. The proposed method uses a randomized $\ell _{2}$ -subspace embedding and a gradient coding technique to distribute blocks of data to the computational nodes of a centralized network, and at each iteration the central server only requires a small number of computations to obtain the steepest descent update. The novelty of our approach is that the data is replicated according to importance scores, called block leverage scores, in contrast to most gradient coding approaches that uniformly replicate the data blocks. Furthermore, we do not require a decoding step at each iteration, avoiding a bottleneck in previous gradient coding schemes. We show that our approach results in a valid $\ell _{2}$ -subspace embedding, and that our resulting approximation converges to the optimal solution.

关键词： Servers approximation algorithms Task analysis Encoding Linear algebra Accuracy Monte Carlo methods Low-rank approximations least-squares regression randomized algorithms randomized numerical linear algebra coded computing stragglers erasure-coding replication-coding

来源：评论

学校读者我要写书评

暂无评论

On Chernoff Lower-Bound of Outage Threshold for Non-Central χ²-Distributed Beamforming Gain in URLLC Systems

引用

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2024年第8期23卷 8330-8344页

作者： Wang, Jinfei Ma, Yi Tafazolli, Rahim Pang, Zhibo Univ Surrey Inst Commun Syst 5GIC&6GIC Guildford GU2 7XH England ABB Corp Res Sweden Dept Automat Technol S-72226 Vasteras Sweden Royal Inst Technol KTH Dept Intelligent Syst S-14428 Stockholm Sweden

The cumulative distribution function (CDF) of a non-central chi(2) -distributed random variable (RV) is often used when measuring the outage probability of communication systems. For ultra-reliable low-latency communication (URLLC), it is important but mathematically challenging to determine the outage threshold for an extremely small outage target. This motivates us to investigate lower bounds of the outage threshold, and it is found that the one derived from the Chernoff inequality (named Cher-LB) is the most effective lower bound. This finding is associated with three rigorously established properties of the Cher-LB with respect to the mean, variance, reliability requirement, and degrees of freedom of the non-central chi(2) -distributed RV. The Cher-LB is then employed to predict the beamforming gain in URLLC for both conventional multi-antenna systems (i.e., MIMO) under first-order Markov time-varying channel and reconfigurable intellgent surface (RIS) systems. It is exhibited that, with the proposed Cher-LB, the pessimistic prediction of the beamforming gain is made sufficiently accurate for guaranteed reliability as well as the transmit-energy efficiency.

关键词： Ultra reliable low latency communication Array signal processing Wireless communication Transmitters approximation algorithms Power system reliability MIMO communication Chernoff bound beamforming gain non-central chi(2)-distribution reliability ultra-reliable low-latency communication (URLLC)

来源：评论

学校读者我要写书评

暂无评论

Privacy-Preserving Distributed ADMM With Event-Triggered Communication

引用

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS 2024年第2期35卷 2835-2847页

作者： Zhang, Zhen Yang, Shaofu Xu, Wenying Di, Kai Southeast Univ Sch Comp Sci & Engn Nanjing 211189 Peoples R China Southeast Univ Sch Math Nanjing 211189 Peoples R China

This article addresses distributed optimization problems, in which a group of agents cooperatively minimize the sum of their private objective functions via information exchanging. Building on alternating direction method of multipliers (ADMM), we propose a privacy-preserving and communication-efficient decentralized quadratically approximated ADMM algorithm, termed PC-DQM, for solving such type of problems under the scenario of limited communication. In PC-DQM, an event-triggered mechanism is designed to schedule the communication instants for reducing communication cost. Simultaneously, for privacy preservation, a Hessian matrix with perturbed noise is introduced to quadratically approximate the objective function, which results in a closed form of primal vector update and then avoids solving a subproblem at each iteration with possible high computation cost. In addition, the triggered scheme is also utilized to schedule the update of Hessian, which can also reduce computation cost. We theoretically show that PC-DQM can protect privacy but without losing accuracy. In addition, we rigorously prove that PC-DQM converges linearly to the exact optimal solution for strongly convex and smooth objective functions. Finally, numerical simulation is presented to illustrate the effectiveness and efficiency of our algorithm.

关键词： Optimization Costs Privacy approximation algorithms Linear programming Convex functions Convergence Alternating direction method of multipliers (ADMM) distributed optimization event-triggered communication privacy preserving

来源：评论

学校读者我要写书评

暂无评论

Sparsity-Preserved Pareto Optimization for Subset Selection

引用

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION 2024年第3期28卷 825-836页

作者： Zhang, Lei Sun, Xiang Yang, Haipeng Cheng, Fan Anhui Univ Sch Comp Sci & Technol Informat Mat & Intelligent Sensing Lab Anhui Prov Hefei 230039 Peoples R China Anhui Univ Minist Educ Sch Comp Sci & Technol Key Lab Intelligent Comp & Signal Proc Hefei 230039 Peoples R China

Subset selection that selects a limited number of variables optimizing many given criteria is a fundamental problem with various applications, such as sparse regression (SR) and unsupervised feature selection (UFS). Among the existing algorithms for subset selection, evolutionary algorithms (EAs) have achieved great performance in obtaining the subsets with high quality. However, as the selected subsets are sparse, i.e., most variables of these solutions are zero, most existing EAs for subset selection problems pose great challenges to find the optimal solutions effectively and efficiently, especially when the size of the original set is large. To this end, we propose the SPESS approach which is a sparsity-preserved EA for subset selection. To be specific, we design two sparsity-preserved operators (i.e., sparsity-preserved crossover operator and sparsity-preserved mutation operator), which can be used in SPESS to ensure the sparsity of the generated solutions in the process of Pareto optimization. The main advantages of the proposed sparsity-preserved operators are that they can obtain high-quality solutions and improve the search efficiency of the algorithm. According to the experimental results on 12 SR problems and 12 UFS problems, the proposed SPESS is superior over the state-of-the-arts in solving subset selection tasks, and the effectiveness of the proposed two sparsity-preserved operators is also verified.

关键词： Pareto optimization Feature extraction approximation algorithms Greedy algorithms Task analysis Linear programming Relaxation methods Multiobjective evolutionary algorithms (EAs) sparse regression (SR) sparsity-preserved Pareto optimization subset selection unsupervised feature selection (UFS)

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：