New submissions for Mon, 8 Jan 24

[zoq]

Keyword: sgd

On the numerical reliability of nonsmooth autodiff: a MaxPool case study

• Authors: Authors: Ryan Boustany (TSE-R)
• Subjects: Machine Learning (cs.LG); Numerical Analysis (math.NA); Optimization and Control (math.OC); Machine Learning (stat.ML)
• Arxiv link: https://arxiv.org/abs/2401.02736
• Pdf link: https://arxiv.org/pdf/2401.02736
• Abstract This paper considers the reliability of automatic differentiation (AD) for neural networks involving the nonsmooth MaxPool operation. We investigate the behavior of AD across different precision levels (16, 32, 64 bits) and convolutional architectures (LeNet, VGG, and ResNet) on various datasets (MNIST, CIFAR10, SVHN, and ImageNet). Although AD can be incorrect, recent research has shown that it coincides with the derivative almost everywhere, even in the presence of nonsmooth operations (such as MaxPool and ReLU). On the other hand, in practice, AD operates with floating-point numbers (not real numbers), and there is, therefore, a need to explore subsets on which AD can be numerically incorrect. These subsets include a bifurcation zone (where AD is incorrect over reals) and a compensation zone (where AD is incorrect over floating-point numbers but correct over reals). Using SGD for the training process, we study the impact of different choices of the nonsmooth Jacobian for the MaxPool function on the precision of 16 and 32 bits. These findings suggest that nonsmooth MaxPool Jacobians with lower norms help maintain stable and efficient test accuracy, whereas those with higher norms can result in instability and decreased performance. We also observe that the influence of MaxPool's nonsmooth Jacobians on learning can be reduced by using batch normalization, Adam-like optimizers, or increasing the precision level.

Keyword: optimization

UAV Trajectory Planning for AoI-Minimal Data Collection in UAV-Aided IoT Networks by Transformer

• Authors: Authors: Botao Zhu, Ebrahim Bedeer, Ha H. Nguyen, Robert Barton, Zhen Gao
• Subjects: Networking and Internet Architecture (cs.NI); Artificial Intelligence (cs.AI)
• Arxiv link: https://arxiv.org/abs/2401.02425
• Pdf link: https://arxiv.org/pdf/2401.02425
• Abstract Maintaining freshness of data collection in Internet-of-Things (IoT) networks has attracted increasing attention. By taking into account age-of-information (AoI), we investigate the trajectory planning problem of an unmanned aerial vehicle (UAV) that is used to aid a cluster-based IoT network. An optimization problem is formulated to minimize the total AoI of the collected data by the UAV from the ground IoT network. Since the total AoI of the IoT network depends on the flight time of the UAV and the data collection time at hovering points, we jointly optimize the selection of hovering points and the visiting order to these points. We exploit the state-of-the-art transformer and the weighted A*, which is a path search algorithm, to design a machine learning algorithm to solve the formulated problem. The whole UAV-IoT system is fed into the encoder network of the proposed algorithm, and the algorithm's decoder network outputs the visiting order to ground clusters. Then, the weighted A* is used to find the hovering point for each cluster in the ground IoT network. Simulation results show that the trained model by the proposed algorithm has a good generalization ability to generate solutions for IoT networks with different numbers of ground clusters, without the need to retrain the model. Furthermore, results show that our proposed algorithm can find better UAV trajectories with the minimum total AoI when compared to other algorithms.

Image Collage on Arbitrary Shape via Shape-Aware Slicing and Optimization

• Authors: Authors: Dong-Yi Wu, Thi-Ngoc-Hanh Le, Sheng-Yi Yao, Yun-Chen Lin, Tong-Yee Lee
• Subjects: Computer Vision and Pattern Recognition (cs.CV); Graphics (cs.GR)
• Arxiv link: https://arxiv.org/abs/2401.02435
• Pdf link: https://arxiv.org/pdf/2401.02435
• Abstract Image collage is a very useful tool for visualizing an image collection. Most of the existing methods and commercial applications for generating image collages are designed on simple shapes, such as rectangular and circular layouts. This greatly limits the use of image collages in some artistic and creative settings. Although there are some methods that can generate irregularly-shaped image collages, they often suffer from severe image overlapping and excessive blank space. This prevents such methods from being effective information communication tools. In this paper, we present a shape slicing algorithm and an optimization scheme that can create image collages of arbitrary shapes in an informative and visually pleasing manner given an input shape and an image collection. To overcome the challenge of irregular shapes, we propose a novel algorithm, called Shape-Aware Slicing, which partitions the input shape into cells based on medial axis and binary slicing tree. Shape-Aware Slicing, which is designed specifically for irregular shapes, takes human perception and shape structure into account to generate visually pleasing partitions. Then, the layout is optimized by analyzing input images with the goal of maximizing the total salient regions of the images. To evaluate our method, we conduct extensive experiments and compare our results against previous work. The evaluations show that our proposed algorithm can efficiently arrange image collections on irregular shapes and create visually superior results than prior work and existing commercial tools.

On the Prospects of Incorporating Large Language Models (LLMs) in Automated Planning and Scheduling (APS)

• Authors: Authors: Vishal Pallagani, Kaushik Roy, Bharath Muppasani, Francesco Fabiano, Andrea Loreggia, Keerthiram Murugesan, Biplav Srivastava, Francesca Rossi, Lior Horesh, Amit Sheth
• Subjects: Artificial Intelligence (cs.AI)
• Arxiv link: https://arxiv.org/abs/2401.02500
• Pdf link: https://arxiv.org/pdf/2401.02500
• Abstract Automated Planning and Scheduling is among the growing areas in Artificial Intelligence (AI) where mention of LLMs has gained popularity. Based on a comprehensive review of 126 papers, this paper investigates eight categories based on the unique applications of LLMs in addressing various aspects of planning problems: language translation, plan generation, model construction, multi-agent planning, interactive planning, heuristics optimization, tool integration, and brain-inspired planning. For each category, we articulate the issues considered and existing gaps. A critical insight resulting from our review is that the true potential of LLMs unfolds when they are integrated with traditional symbolic planners, pointing towards a promising neuro-symbolic approach. This approach effectively combines the generative aspects of LLMs with the precision of classical planning methods. By synthesizing insights from existing literature, we underline the potential of this integration to address complex planning challenges. Our goal is to encourage the ICAPS community to recognize the complementary strengths of LLMs and symbolic planners, advocating for a direction in automated planning that leverages these synergistic capabilities to develop more advanced and intelligent planning systems.

Image-based Deep Learning for Smart Digital Twins: a Review

• Authors: Authors: Md Ruman Islam, Mahadevan Subramaniam, Pei-Chi Huang (Department of Computer Science, University of Nebraska at Omaha, Omaha, NE, USA)
• Subjects: Computer Vision and Pattern Recognition (cs.CV); Artificial Intelligence (cs.AI); Machine Learning (cs.LG); Systems and Control (eess.SY)
• Arxiv link: https://arxiv.org/abs/2401.02523
• Pdf link: https://arxiv.org/pdf/2401.02523
• Abstract Smart Digital twins (SDTs) are being increasingly used to virtually replicate and predict the behaviors of complex physical systems through continual data assimilation enabling the optimization of the performance of these systems by controlling the actions of systems. Recently, deep learning (DL) models have significantly enhanced the capabilities of SDTs, particularly for tasks such as predictive maintenance, anomaly detection, and optimization. In many domains, including medicine, engineering, and education, SDTs use image data (image-based SDTs) to observe and learn system behaviors and control their behaviors. This paper focuses on various approaches and associated challenges in developing image-based SDTs by continually assimilating image data from physical systems. The paper also discusses the challenges involved in designing and implementing DL models for SDTs, including data acquisition, processing, and interpretation. In addition, insights into the future directions and opportunities for developing new image-based DL approaches to develop robust SDTs are provided. This includes the potential for using generative models for data augmentation, developing multi-modal DL models, and exploring the integration of DL with other technologies, including 5G, edge computing, and IoT. In this paper, we describe the image-based SDTs, which enable broader adoption of the digital twin DT paradigms across a broad spectrum of areas and the development of new methods to improve the abilities of SDTs in replicating, predicting, and optimizing the behavior of complex systems.

Autonomous Multi-Rotor UAVs: A Holistic Approach to Design, Optimization, and Fabrication

• Authors: Authors: Aniruth A, Chirag Satpathy, Jothika K, Nitteesh M, Gokulraj M, Venkatram K, Harshith G, Shristi S, Anushka Vani, Jonathan Spurgeon
• Subjects: Robotics (cs.RO); Materials Science (cond-mat.mtrl-sci)
• Arxiv link: https://arxiv.org/abs/2401.02541
• Pdf link: https://arxiv.org/pdf/2401.02541
• Abstract Unmanned Aerial Vehicles (UAVs) have become pivotal in domains spanning military, agriculture, surveillance, and logistics, revolutionizing data collection and environmental interaction. With the advancement in drone technology, there is a compelling need to develop a holistic methodology for designing UAVs. This research focuses on establishing a procedure encompassing conceptual design, use of composite materials, weight optimization, stability analysis, avionics integration, advanced manufacturing, and incorporation of autonomous payload delivery through object detection models tailored to satisfy specific applications while maintaining cost efficiency. The study conducts a comparative assessment of potential composite materials and various quadcopter frame configurations. The novel features include a payload-dropping mechanism, a unibody arm fixture, and the utilization of carbon-fibre-balsa composites. A quadcopter is designed and analyzed using the proposed methodology, followed by its fabrication using additive manufacturing and vacuum bagging techniques. A computer vision-based deep learning model enables precise delivery of payloads by autonomously detecting targets.

OptFlow: Fast Optimization-based Scene Flow Estimation without Supervision

• Authors: Authors: Rahul Ahuja, Chris Baker, Wilko Schwarting
• Subjects: Computer Vision and Pattern Recognition (cs.CV)
• Arxiv link: https://arxiv.org/abs/2401.02550
• Pdf link: https://arxiv.org/pdf/2401.02550
• Abstract Scene flow estimation is a crucial component in the development of autonomous driving and 3D robotics, providing valuable information for environment perception and navigation. Despite the advantages of learning-based scene flow estimation techniques, their domain specificity and limited generalizability across varied scenarios pose challenges. In contrast, non-learning optimization-based methods, incorporating robust priors or regularization, offer competitive scene flow estimation performance, require no training, and show extensive applicability across datasets, but suffer from lengthy inference times. In this paper, we present OptFlow, a fast optimization-based scene flow estimation method. Without relying on learning or any labeled datasets, OptFlow achieves state-of-the-art performance for scene flow estimation on popular autonomous driving benchmarks. It integrates a local correlation weight matrix for correspondence matching, an adaptive correspondence threshold limit for nearest-neighbor search, and graph prior rigidity constraints, resulting in expedited convergence and improved point correspondence identification. Moreover, we demonstrate how integrating a point cloud registration function within our objective function bolsters accuracy and differentiates between static and dynamic points without relying on external odometry data. Consequently, OptFlow outperforms the baseline graph-prior method by approximately 20% and the Neural Scene Flow Prior method by 5%-7% in accuracy, all while offering the fastest inference time among all non-learning scene flow estimation methods.

Long-term Fairness For Real-time Decision Making: A Constrained Online Optimization Approach

• Authors: Authors: Ruijie Du, Deepan Muthirayan, Pramod P. Khargonekar, Yanning Shen
• Subjects: Machine Learning (cs.LG); Computers and Society (cs.CY)
• Arxiv link: https://arxiv.org/abs/2401.02552
• Pdf link: https://arxiv.org/pdf/2401.02552
• Abstract Machine learning (ML) has demonstrated remarkable capabilities across many real-world systems, from predictive modeling to intelligent automation. However, the widespread integration of machine learning also makes it necessary to ensure machine learning-driven decision-making systems do not violate ethical principles and values of society in which they operate. As ML-driven decisions proliferate, particularly in cases involving sensitive attributes such as gender, race, and age, to name a few, the need for equity and impartiality has emerged as a fundamental concern. In situations demanding real-time decision-making, fairness objectives become more nuanced and complex: instantaneous fairness to ensure equity in every time slot, and long-term fairness to ensure fairness over a period of time. There is a growing awareness that real-world systems that operate over long periods and require fairness over different timelines. However, existing approaches mainly address dynamic costs with time-invariant fairness constraints, often disregarding the challenges posed by time-varying fairness constraints. To bridge this gap, this work introduces a framework for ensuring long-term fairness within dynamic decision-making systems characterized by time-varying fairness constraints. We formulate the decision problem with fairness constraints over a period as a constrained online optimization problem. A novel online algorithm, named LoTFair, is presented that solves the problem 'on the fly'. We prove that LoTFair can make overall fairness violations negligible while maintaining the performance over the long run.

Gradient weighting for speaker verification in extremely low Signal-to-Noise Ratio

• Authors: Authors: Yi Ma, Kong Aik Lee, Ville Hautamäki, Meng Ge, Haizhou Li
• Subjects: Sound (cs.SD); Audio and Speech Processing (eess.AS)
• Arxiv link: https://arxiv.org/abs/2401.02626
• Pdf link: https://arxiv.org/pdf/2401.02626
• Abstract Speaker verification is hampered by background noise, particularly at extremely low Signal-to-Noise Ratio (SNR) under 0 dB. It is difficult to suppress noise without introducing unwanted artifacts, which adversely affects speaker verification. We proposed the mechanism called Gradient Weighting (Grad-W), which dynamically identifies and reduces artifact noise during prediction. The mechanism is based on the property that the gradient indicates which parts of the input the model is paying attention to. Specifically, when the speaker network focuses on a region in the denoised utterance but not on the clean counterpart, we consider it artifact noise and assign higher weights for this region during optimization of enhancement. We validate it by training an enhancement model and testing the enhanced utterance on speaker verification. The experimental results show that our approach effectively reduces artifact noise, improving speaker verification across various SNR levels.

Improving sample efficiency of high dimensional Bayesian optimization with MCMC

• Authors: Authors: Zeji Yi, Yunyue Wei, Chu Xin Cheng, Kaibo He, Yanan Sui
• Subjects: Machine Learning (cs.LG); Machine Learning (stat.ML)
• Arxiv link: https://arxiv.org/abs/2401.02650
• Pdf link: https://arxiv.org/pdf/2401.02650
• Abstract Sequential optimization methods are often confronted with the curse of dimensionality in high-dimensional spaces. Current approaches under the Gaussian process framework are still burdened by the computational complexity of tracking Gaussian process posteriors and need to partition the optimization problem into small regions to ensure exploration or assume an underlying low-dimensional structure. With the idea of transiting the candidate points towards more promising positions, we propose a new method based on Markov Chain Monte Carlo to efficiently sample from an approximated posterior. We provide theoretical guarantees of its convergence in the Gaussian process Thompson sampling setting. We also show experimentally that both the Metropolis-Hastings and the Langevin Dynamics version of our algorithm outperform state-of-the-art methods in high-dimensional sequential optimization and reinforcement learning benchmarks.

Nurse-in-the-Loop Artificial Intelligence for Precision Management of Type 2 Diabetes in a Clinical Trial Utilizing Transfer-Learned Predictive Digital Twin

• Authors: Authors: Syed Hasib Akhter Faruqui, Adel Alaeddini, Yan Du, Shiyu Li, Kumar Sharma, Jing Wang
• Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI)
• Arxiv link: https://arxiv.org/abs/2401.02661
• Pdf link: https://arxiv.org/pdf/2401.02661
• Abstract Background: Type 2 diabetes (T2D) is a prevalent chronic disease with a significant risk of serious health complications and negative impacts on the quality of life. Given the impact of individual characteristics and lifestyle on the treatment plan and patient outcomes, it is crucial to develop precise and personalized management strategies. Artificial intelligence (AI) provides great promise in combining patterns from various data sources with nurses' expertise to achieve optimal care. Methods: This is a 6-month ancillary study among T2D patients (n = 20, age = 57 +- 10). Participants were randomly assigned to an intervention (AI, n=10) group to receive daily AI-generated individualized feedback or a control group without receiving the daily feedback (non-AI, n=10) in the last three months. The study developed an online nurse-in-the-loop predictive control (ONLC) model that utilizes a predictive digital twin (PDT). The PDT was developed using a transfer-learning-based Artificial Neural Network. The PDT was trained on participants self-monitoring data (weight, food logs, physical activity, glucose) from the first three months, and the online control algorithm applied particle swarm optimization to identify impactful behavioral changes for maintaining the patient's glucose and weight levels for the next three months. The ONLC provided the intervention group with individualized feedback and recommendations via text messages. The PDT was re-trained weekly to improve its performance. Findings: The trained ONLC model achieved >=80% prediction accuracy across all patients while the model was tuned online. Participants in the intervention group exhibited a trend of improved daily steps and stable or improved total caloric and total carb intake as recommended.

GainNet: Coordinates the Odd Couple of Generative AI and 6G Networks

• Authors: Authors: Ning Chen, Jie Yang, Zhipeng Cheng, Xuwei Fan, Zhang Liu, Bangzhen Huang, Yifeng Zhao, Lianfen Huang, Xiaojiang Du, Mohsen Guizani
• Subjects: Networking and Internet Architecture (cs.NI); Signal Processing (eess.SP)
• Arxiv link: https://arxiv.org/abs/2401.02662
• Pdf link: https://arxiv.org/pdf/2401.02662
• Abstract The rapid expansion of AI-generated content (AIGC) reflects the iteration from assistive AI towards generative AI (GAI) with creativity. Meanwhile, the 6G networks will also evolve from the Internet-of-everything to the Internet-of-intelligence with hybrid heterogeneous network architectures. In the future, the interplay between GAI and the 6G will lead to new opportunities, where GAI can learn the knowledge of personalized data from the massive connected 6G end devices, while GAI's powerful generation ability can provide advanced network solutions for 6G network and provide 6G end devices with various AIGC services. However, they seem to be an odd couple, due to the contradiction of data and resources. To achieve a better-coordinated interplay between GAI and 6G, the GAI-native networks (GainNet), a GAI-oriented collaborative cloud-edge-end intelligence framework, is proposed in this paper. By deeply integrating GAI with 6G network design, GainNet realizes the positive closed-loop knowledge flow and sustainable-evolution GAI model optimization. On this basis, the GAI-oriented generic resource orchestration mechanism with integrated sensing, communication, and computing (GaiRom-ISCC) is proposed to guarantee the efficient operation of GainNet. Two simple case studies demonstrate the effectiveness and robustness of the proposed schemes. Finally, we envision the key challenges and future directions concerning the interplay between GAI models and 6G networks.

Modelling Open-Source Software Reliability Incorporating Swarm Intelligence-Based Techniques

• Authors: Authors: Omar Shatnawi
• Subjects: Software Engineering (cs.SE); Neural and Evolutionary Computing (cs.NE)
• Arxiv link: https://arxiv.org/abs/2401.02664
• Pdf link: https://arxiv.org/pdf/2401.02664
• Abstract In the software industry, two software engineering development best practices coexist: open-source and closed-source software. The former has a shared code that anyone can contribute, whereas the latter has a proprietary code that only the owner can access. Software reliability is crucial in the industry when a new product or update is released. Applying meta-heuristic optimization algorithms for closed-source software reliability prediction has produced significant and accurate results. Now, open-source software dominates the landscape of cloud-based systems. Therefore, providing results on open-source software reliability - as a quality indicator - would greatly help solve the open-source software reliability growth-modelling problem. The reliability is predicted by estimating the parameters of the software reliability models. As software reliability models are inherently nonlinear, traditional approaches make estimating the appropriate parameters difficult and ineffective. Consequently, software reliability models necessitate a high-quality parameter estimation technique. These objectives dictate the exploration of potential applications of meta-heuristic swarm intelligence optimization algorithms for optimizing the parameter estimation of nonhomogeneous Poisson process-based open-source software reliability modelling. The optimization algorithms are firefly, social spider, artificial bee colony, grey wolf, particle swarm, moth flame, and whale. The applicability and performance evaluation of the optimization modelling approach is demonstrated through two real open-source software reliability datasets. The results are promising.

LMaaS: Exploring Pricing Strategy of Large Model as a Service for Communication

• Authors: Authors: Panlong Wu, Qi Liu, Yanjie Dong, Fangxin Wang
• Subjects: Networking and Internet Architecture (cs.NI); Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG)
• Arxiv link: https://arxiv.org/abs/2401.02675
• Pdf link: https://arxiv.org/pdf/2401.02675
• Abstract The next generation of communication is envisioned to be intelligent communication, that can replace traditional symbolic communication, where highly condensed semantic information considering both source and channel will be extracted and transmitted with high efficiency. The recent popular large models such as GPT4 and the boosting learning techniques lay a solid foundation for the intelligent communication, and prompt the practical deployment of it in the near future. Given the characteristics of "training once and widely use" of those multimodal large language models, we argue that a pay-as-you-go service mode will be suitable in this context, referred to as Large Model as a Service (LMaaS). However, the trading and pricing problem is quite complex with heterogeneous and dynamic customer environments, making the pricing optimization problem challenging in seeking on-hand solutions. In this paper, we aim to fill this gap and formulate the LMaaS market trading as a Stackelberg game with two steps. In the first step, we optimize the seller's pricing decision and propose an Iterative Model Pricing (IMP) algorithm that optimizes the prices of large models iteratively by reasoning customers' future rental decisions, which is able to achieve a near-optimal pricing solution. In the second step, we optimize customers' selection decisions by designing a robust selecting and renting (RSR) algorithm, which is guaranteed to be optimal with rigorous theoretical proof. Extensive experiments confirm the effectiveness and robustness of our algorithms.

A multi-objective optimization framework for terrain modification based on a combined hydrological and earthwork cost-benefit

• Authors: Authors: Hanwen Xu, Mark Randall, Lei Li, Yuyi Tan, Thomas Balstrøm
• Subjects: Computational Engineering, Finance, and Science (cs.CE)
• Arxiv link: https://arxiv.org/abs/2401.02698
• Pdf link: https://arxiv.org/pdf/2401.02698
• Abstract The escalating risk of urban inundation has drawn increased attention to urban stormwater management. This study proposes a multi-objective optimization for terrain modification, combining the Non-dominated Sorting Genetic Algorithm II (NSGA-II) with digital elevation model (DEM)-based hydrological cost factor analysis. To reduce the precipitation erosive forces and runoff kinetic energy, the resulting framework offers the possibility of efficiently searching numerous solutions for trade-off sets that meet three conflicting objectives: minimizing maximum flow velocity, maximizing runoff path length and minimizing earthwork costs. Our application case study in H{\o}je Taastrup, Denmark, demonstrates the ability of the optimization framework to iteratively generate diversified modification scenarios, which form the reference for topography planning. The three individual objective preferred solutions, a balanced solution, and twenty solutions under regular ordering are selected and visualized to determine the limits of the optimization and the cost-effectiveness tendency. Integrating genetic algorithms with DEM-based hydrological analysis demonstrates the potential to consider more complicated hydrological benefit objectives with open-ended characteristics. It provides a novel and efficient way to optimize topographic characteristics for improving holistic stormwater management strategies.

Joint User Association and Power Control for Cell-Free Massive MIMO

• Authors: Authors: Chongzheng Hao, Tung Thanh Vu, Hien Quoc Ngo, Minh N.Dao, Xiaoyu Dang, Chenghua Wang, Michail Matthaiou
• Subjects: Information Theory (cs.IT); Signal Processing (eess.SP)
• Arxiv link: https://arxiv.org/abs/2401.02701
• Pdf link: https://arxiv.org/pdf/2401.02701
• Abstract This work proposes novel approaches that jointly design user equipment (UE) association and power control (PC) in a downlink user-centric cell-free massive multiple-input multiple-output (CFmMIMO) network, where each UE is only served by a set of access points (APs) for reducing the fronthaul signalling and computational complexity. In order to maximize the sum spectral efficiency (SE) of the UEs, we formulate a mixed-integer nonconvex optimization problem under constraints on the per-AP transmit power, quality-of-service rate requirements, maximum fronthaul signalling load, and maximum number of UEs served by each AP. In order to solve the formulated problem efficiently, we propose two different schemes according to the different sizes of the CFmMIMO systems. For small-scale CFmMIMO systems, we present a successive convex approximation (SCA) method to obtain a stationary solution and also develop a learning-based method (JointCFNet) to reduce the computational complexity. For large-scale CFmMIMO systems, we propose a low-complexity suboptimal algorithm using accelerated projected gradient (APG) techniques. Numerical results show that our JointCFNet can yield similar performance and significantly decrease the run time compared with the SCA algorithm in small-scale systems. The presented APG approach is confirmed to run much faster than the SCA algorithm in the large-scale system while obtaining an SE performance close to that of the SCA approach. Moreover, the median sum SE of the APG method is up to about 2.8 fold higher than that of the heuristic baseline scheme.

Predicting Traffic Flow with Federated Learning and Graph Neural with Asynchronous Computations Network

• Authors: Authors: Muhammad Yaqub, Shahzad Ahmad, Malik Abdul Manan, Imran Shabir Chuhan
• Subjects: Machine Learning (cs.LG); Computer Vision and Pattern Recognition (cs.CV)
• Arxiv link: https://arxiv.org/abs/2401.02723
• Pdf link: https://arxiv.org/pdf/2401.02723
• Abstract Real-time traffic flow prediction holds significant importance within the domain of Intelligent Transportation Systems (ITS). The task of achieving a balance between prediction precision and computational efficiency presents a significant challenge. In this article, we present a novel deep-learning method called Federated Learning and Asynchronous Graph Convolutional Network (FLAGCN). Our framework incorporates the principles of asynchronous graph convolutional networks with federated learning to enhance the accuracy and efficiency of real-time traffic flow prediction. The FLAGCN model employs a spatial-temporal graph convolution technique to asynchronously address spatio-temporal dependencies within traffic data effectively. To efficiently handle the computational requirements associated with this deep learning model, this study used a graph federated learning technique known as GraphFL. This approach is designed to facilitate the training process. The experimental results obtained from conducting tests on two distinct traffic datasets demonstrate that the utilization of FLAGCN leads to the optimization of both training and inference durations while maintaining a high level of prediction accuracy. FLAGCN outperforms existing models with significant improvements by achieving up to approximately 6.85% reduction in RMSE, 20.45% reduction in MAPE, compared to the best-performing existing models.

Design Optimization of Wire Arrangement with Variable Relay Points in Numerical Simulation for Tendon-driven Robots

• Authors: Authors: Kento Kawaharazuka, Shunnosuke Yoshimura, Temma Suzuki, Kei Okada, Masayuki Inaba
• Subjects: Robotics (cs.RO)
• Arxiv link: https://arxiv.org/abs/2401.02730
• Pdf link: https://arxiv.org/pdf/2401.02730
• Abstract One of the most important features of tendon-driven robots is the ease of wire arrangement and the degree of freedom it affords, enabling the construction of a body that satisfies the desired characteristics by modifying the wire arrangement. Various wire arrangement optimization methods have been proposed, but they have simplified the configuration by assuming that the moment arm of wires to joints are constant, or by disregarding wire arrangements that span multiple joints and include relay points. In this study, we formulate a more flexible wire arrangement optimization problem in which each wire is represented by a start point, multiple relay points, and an end point, and achieve the desired physical performance based on black-box optimization. We consider a multi-objective optimization which simultaneously takes into account both the feasible operational force space and velocity space, and discuss the optimization results obtained from various configurations.

Fairness-Aware Job Scheduling for Multi-Job Federated Learning

• Authors: Authors: Yuxin Shi, Han Yu
• Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Distributed, Parallel, and Cluster Computing (cs.DC)
• Arxiv link: https://arxiv.org/abs/2401.02740
• Pdf link: https://arxiv.org/pdf/2401.02740
• Abstract Federated learning (FL) enables multiple data owners (a.k.a. FL clients) to collaboratively train machine learning models without disclosing sensitive private data. Existing FL research mostly focuses on the monopoly scenario in which a single FL server selects a subset of FL clients to update their local models in each round of training. In practice, there can be multiple FL servers simultaneously trying to select clients from the same pool. In this paper, we propose a first-of-its-kind Fairness-aware Federated Job Scheduling (FairFedJS) approach to bridge this gap. Based on Lyapunov optimization, it ensures fair allocation of high-demand FL client datasets to FL jobs in need of them, by jointly considering the current demand and the job payment bids, in order to prevent prolonged waiting. Extensive experiments comparing FairFedJS against four state-of-the-art approaches on two datasets demonstrate its significant advantages. It outperforms the best baseline by 31.9% and 1.0% on average in terms of scheduling fairness and convergence time, respectively, while achieving comparable test accuracy.

Omnidirectional Multi-Rotor Aerial Vehicle Pose Optimization: A Novel Approach to Physical Layer Security

• Authors: Authors: Daniel Bonilla Licea, Giuseppe Silano, Mounir Ghogho, Martin Saska
• Subjects: Robotics (cs.RO)
• Arxiv link: https://arxiv.org/abs/2401.02848
• Pdf link: https://arxiv.org/pdf/2401.02848
• Abstract The integration of Multi-Rotor Aerial Vehicles (MRAVs) into 5G and 6G networks enhances coverage, connectivity, and congestion management. This fosters communication-aware robotics, exploring the interplay between robotics and communications, but also makes the MRAVs susceptible to malicious attacks, such as jamming. One traditional approach to counter these attacks is the use of beamforming on the MRAVs to apply physical layer security techniques. In this paper, we explore pose optimization as an alternative approach to countering jamming attacks on MRAVs. This technique is intended for omnidirectional MRAVs, which are drones capable of independently controlling both their position and orientation, as opposed to the more common underactuated MRAVs whose orientation cannot be controlled independently of their position. In this paper, we consider an omnidirectional MRAV serving as a Base Station (BS) for legitimate ground nodes, under attack by a malicious jammer. We optimize the MRAV pose (i.e., position and orientation) to maximize the minimum Signal-to-Interference-plus-Noise Ratio (SINR) over all legitimate nodes.

On the Selection of Intermediate Length Representative Periods for Capacity Expansion

• Authors: Authors: Osten Anderson, Nanpeng Yu, Konstantinos Oikonomou, Di Wu
• Subjects: Systems and Control (eess.SY)
• Arxiv link: https://arxiv.org/abs/2401.02888
• Pdf link: https://arxiv.org/pdf/2401.02888
• Abstract As the decarbonization of power systems accelerates, there has been increasing interest in capacity expansion models for their role in guiding this transition. Representative period selection is an important component of capacity expansion modeling, enabling computational tractability of optimization while ensuring fidelity between the representative periods and the full year. However, little attention has been devoted to selecting representative periods longer than a single day. This prevents the capacity expansion model from directly simulating interday energy sharing, which is of key importance as energy generation becomes more variable and storage more important. To this end, we propose a novel method for selecting representative periods of any length. The method is validated using a capacity expansion model and production cost model based on California's decarbonization goals. We demonstrate that the representative period length has a substantial impact in the results of the capacity expansion investment plan.

Energy-Preserving Reduced Operator Inference for Efficient Design and Control

• Authors: Authors: Tomoki Koike, Elizabeth Qian
• Subjects: Numerical Analysis (math.NA); Machine Learning (cs.LG); Dynamical Systems (math.DS)
• Arxiv link: https://arxiv.org/abs/2401.02889
• Pdf link: https://arxiv.org/pdf/2401.02889
• Abstract Many-query computations, in which a computational model for an engineering system must be evaluated many times, are crucial in design and control. For systems governed by partial differential equations (PDEs), typical high-fidelity numerical models are high-dimensional and too computationally expensive for the many-query setting. Thus, efficient surrogate models are required to enable low-cost computations in design and control. This work presents a physics-preserving reduced model learning approach that targets PDEs whose quadratic operators preserve energy, such as those arising in governing equations in many fluids problems. The approach is based on the Operator Inference method, which fits reduced model operators to state snapshot and time derivative data in a least-squares sense. However, Operator Inference does not generally learn a reduced quadratic operator with the energy-preserving property of the original PDE. Thus, we propose a new energy-preserving Operator Inference (EP-OpInf) approach, which imposes this structure on the learned reduced model via constrained optimization. Numerical results using the viscous Burgers' and Kuramoto-Sivashinksy equation (KSE) demonstrate that EP-OpInf learns efficient and accurate reduced models that retain this energy-preserving structure.

Model predictive altitude and velocity control in ergodic potential field directed multi-UAV search

• Authors: Authors: Luka Lanča, Karlo Jakac, Stefan Ivić
• Subjects: Robotics (cs.RO)
• Arxiv link: https://arxiv.org/abs/2401.02899
• Pdf link: https://arxiv.org/pdf/2401.02899
• Abstract This research addresses the challenge of executing multi-UAV survey missions over diverse terrains characterized by varying elevations. The approach integrates advanced two-dimensional ergodic search technique with model predictive control of UAV altitude and velocity. Optimization of altitude and velocity is performed along anticipated UAV ground routes, considering multiple objectives and constraints. This yields a flight regimen tailored to the terrain, as well as the motion and sensing characteristics of the UAVs. The proposed UAV motion control strategy is assessed through simulations of realistic search missions and actual terrain models. Results demonstrate the successful integration of model predictive altitude and velocity control with a two-dimensional potential field-guided ergodic search. Adjusting UAV altitudes to near-ideal levels facilitates the utilization of sensing ranges, thereby enhancing the effectiveness of the search. Furthermore, the control algorithm is capable of real-time computation, encouraging its practical application in real-world scenarios.

State Derivative Normalization for Continuous-Time Deep Neural Networks

• Authors: Authors: Jonas Weigand, Gerben I. Beintema, Jonas Ulmen, Daniel Görges, Roland Tóth, Maarten Schoukens, Martin Ruskowski
• Subjects: Systems and Control (eess.SY); Machine Learning (cs.LG)
• Arxiv link: https://arxiv.org/abs/2401.02902
• Pdf link: https://arxiv.org/pdf/2401.02902
• Abstract The importance of proper data normalization for deep neural networks is well known. However, in continuous-time state-space model estimation, it has been observed that improper normalization of either the hidden state or hidden state derivative of the model estimate, or even of the time interval can lead to numerical and optimization challenges with deep learning based methods. This results in a reduced model quality. In this contribution, we show that these three normalization tasks are inherently coupled. Due to the existence of this coupling, we propose a solution to all three normalization challenges by introducing a normalization constant at the state derivative level. We show that the appropriate choice of the normalization constant is related to the dynamics of the to-be-identified system and we derive multiple methods of obtaining an effective normalization constant. We compare and discuss all the normalization strategies on a benchmark problem based on experimental data from a cascaded tanks system and compare our results with other methods of the identification literature.

Plug-in Diffusion Model for Sequential Recommendation

• Authors: Authors: Haokai Ma, Ruobing Xie, Lei Meng, Xin Chen, Xu Zhang, Leyu Lin, Zhanhui Kang
• Subjects: Information Retrieval (cs.IR)
• Arxiv link: https://arxiv.org/abs/2401.02913
• Pdf link: https://arxiv.org/pdf/2401.02913
• Abstract Pioneering efforts have verified the effectiveness of the diffusion models in exploring the informative uncertainty for recommendation. Considering the difference between recommendation and image synthesis tasks, existing methods have undertaken tailored refinements to the diffusion and reverse process. However, these approaches typically use the highest-score item in corpus for user interest prediction, leading to the ignorance of the user's generalized preference contained within other items, thereby remaining constrained by the data sparsity issue. To address this issue, this paper presents a novel Plug-in Diffusion Model for Recommendation (PDRec) framework, which employs the diffusion model as a flexible plugin to jointly take full advantage of the diffusion-generating user preferences on all items. Specifically, PDRec first infers the users' dynamic preferences on all items via a time-interval diffusion model and proposes a Historical Behavior Reweighting (HBR) mechanism to identify the high-quality behaviors and suppress noisy behaviors. In addition to the observed items, PDRec proposes a Diffusion-based Positive Augmentation (DPA) strategy to leverage the top-ranked unobserved items as the potential positive samples, bringing in informative and diverse soft signals to alleviate data sparsity. To alleviate the false negative sampling issue, PDRec employs Noise-free Negative Sampling (NNS) to select stable negative samples for ensuring effective model optimization. Extensive experiments and analyses on four datasets have verified the superiority of the proposed PDRec over the state-of-the-art baselines and showcased the universality of PDRec as a flexible plugin for commonly-used sequential encoders in different recommendation scenarios. The code is available in https://github.com/hulkima/PDRec.

Optimizing Dataflow Systems for Scalable Interactive Visualization

• Authors: Authors: Junran Yang, Hyekang Kevin Joo, Sai Yerramreddy, Dominik Moritz, Leilani Battle
• Subjects: Databases (cs.DB)
• Arxiv link: https://arxiv.org/abs/2401.02952
• Pdf link: https://arxiv.org/pdf/2401.02952
• Abstract Supporting the interactive exploration of large datasets is a popular and challenging use case for data management systems. Traditionally, the interface and the back-end system are built and optimized separately, and interface design and system optimization require different skill sets that are difficult for one person to master. To enable analysts to focus on visualization design, we contribute VegaPlus, a system that automatically optimizes interactive dashboards to support large datasets. To achieve this, VegaPlus leverages two core ideas. First, we introduce an optimizer that can reason about execution plans in Vega, a back-end DBMS, or a mix of both environments. The optimizer also considers how user interactions may alter execution plan performance, and can partially or fully rewrite the plans when needed. Through a series of benchmark experiments on seven different dashboard designs, our results show that VegaPlus provides superior performance and versatility compared to standard dashboard optimization techniques.

DeepSeek LLM: Scaling Open-Source Language Models with Longtermism

• Authors: Authors: DeepSeek-AI: Xiao Bi, Deli Chen, Guanting Chen, Shanhuang Chen, Damai Dai, Chengqi Deng, Honghui Ding, Kai Dong, Qiushi Du, Zhe Fu, Huazuo Gao, Kaige Gao, Wenjun Gao, Ruiqi Ge, Kang Guan, Daya Guo, Jianzhong Guo, Guangbo Hao, Zhewen Hao, Ying He, Wenjie Hu, Panpan Huang, Erhang Li, Guowei Li, Jiashi Li, Yao Li, Y.K. Li, Wenfeng Liang, Fangyun Lin, A.X. Liu, Bo Liu, Wen Liu, Xiaodong Liu, Xin Liu, Yiyuan Liu, Haoyu Lu, Shanghao Lu, Fuli Luo, Shirong Ma, Xiaotao Nie, Tian Pei, Yishi Piao, Junjie Qiu, Hui Qu, Tongzheng Ren, Zehui Ren, Chong Ruan, Zhangli Sha, Zhihong Shao, Junxiao Song, Xuecheng Su, Jingxiang Sun, Yaofeng Sun, Minghui Tang, Bingxuan Wang, Peiyi Wang, Shiyu Wang, Yaohui Wang, Yongji Wang, Tong Wu, Y. Wu, Xin Xie, Zhenda Xie, Ziwei Xie, Yiliang Xiong, Hanwei Xu, R.X. Xu, Yanhong Xu, et al. (18 additional authors not shown)
• Subjects: Computation and Language (cs.CL); Artificial Intelligence (cs.AI); Machine Learning (cs.LG)
• Arxiv link: https://arxiv.org/abs/2401.02954
• Pdf link: https://arxiv.org/pdf/2401.02954
• Abstract The rapid development of open-source large language models (LLMs) has been truly remarkable. However, the scaling law described in previous literature presents varying conclusions, which casts a dark cloud over scaling LLMs. We delve into the study of scaling laws and present our distinctive findings that facilitate scaling of large scale models in two commonly used open-source configurations, 7B and 67B. Guided by the scaling laws, we introduce DeepSeek LLM, a project dedicated to advancing open-source language models with a long-term perspective. To support the pre-training phase, we have developed a dataset that currently consists of 2 trillion tokens and is continuously expanding. We further conduct supervised fine-tuning (SFT) and Direct Preference Optimization (DPO) on DeepSeek LLM Base models, resulting in the creation of DeepSeek Chat models. Our evaluation results demonstrate that DeepSeek LLM 67B surpasses LLaMA-2 70B on various benchmarks, particularly in the domains of code, mathematics, and reasoning. Furthermore, open-ended evaluations reveal that DeepSeek LLM 67B Chat exhibits superior performance compared to GPT-3.5.

Denoising Vision Transformers

• Authors: Authors: Jiawei Yang, Katie Z Luo, Jiefeng Li, Kilian Q Weinberger, Yonglong Tian, Yue Wang
• Subjects: Computer Vision and Pattern Recognition (cs.CV)
• Arxiv link: https://arxiv.org/abs/2401.02957
• Pdf link: https://arxiv.org/pdf/2401.02957
• Abstract We delve into a nuanced but significant challenge inherent to Vision Transformers (ViTs): feature maps of these models exhibit grid-like artifacts, which detrimentally hurt the performance of ViTs in downstream tasks. Our investigations trace this fundamental issue down to the positional embeddings at the input stage. To address this, we propose a novel noise model, which is universally applicable to all ViTs. Specifically, the noise model dissects ViT outputs into three components: a semantics term free from noise artifacts and two artifact-related terms that are conditioned on pixel locations. Such a decomposition is achieved by enforcing cross-view feature consistency with neural fields in a per-image basis. This per-image optimization process extracts artifact-free features from raw ViT outputs, providing clean features for offline applications. Expanding the scope of our solution to support online functionality, we introduce a learnable denoiser to predict artifact-free features directly from unprocessed ViT outputs, which shows remarkable generalization capabilities to novel data without the need for per-image optimization. Our two-stage approach, termed Denoising Vision Transformers (DVT), does not require re-training existing pre-trained ViTs and is immediately applicable to any Transformer-based architecture. We evaluate our method on a variety of representative ViTs (DINO, MAE, DeiT-III, EVA02, CLIP, DINOv2, DINOv2-reg). Extensive evaluations demonstrate that our DVT consistently and significantly improves existing state-of-the-art general-purpose models in semantic and geometric tasks across multiple datasets (e.g., +3.84 mIoU). We hope our study will encourage a re-evaluation of ViT design, especially regarding the naive use of positional embeddings.

Keyword: adam

On the numerical reliability of nonsmooth autodiff: a MaxPool case study

• Authors: Authors: Ryan Boustany (TSE-R)
• Subjects: Machine Learning (cs.LG); Numerical Analysis (math.NA); Optimization and Control (math.OC); Machine Learning (stat.ML)
• Arxiv link: https://arxiv.org/abs/2401.02736
• Pdf link: https://arxiv.org/pdf/2401.02736
• Abstract This paper considers the reliability of automatic differentiation (AD) for neural networks involving the nonsmooth MaxPool operation. We investigate the behavior of AD across different precision levels (16, 32, 64 bits) and convolutional architectures (LeNet, VGG, and ResNet) on various datasets (MNIST, CIFAR10, SVHN, and ImageNet). Although AD can be incorrect, recent research has shown that it coincides with the derivative almost everywhere, even in the presence of nonsmooth operations (such as MaxPool and ReLU). On the other hand, in practice, AD operates with floating-point numbers (not real numbers), and there is, therefore, a need to explore subsets on which AD can be numerically incorrect. These subsets include a bifurcation zone (where AD is incorrect over reals) and a compensation zone (where AD is incorrect over floating-point numbers but correct over reals). Using SGD for the training process, we study the impact of different choices of the nonsmooth Jacobian for the MaxPool function on the precision of 16 and 32 bits. These findings suggest that nonsmooth MaxPool Jacobians with lower norms help maintain stable and efficient test accuracy, whereas those with higher norms can result in instability and decreased performance. We also observe that the influence of MaxPool's nonsmooth Jacobians on learning can be reduced by using batch normalization, Adam-like optimizers, or increasing the precision level.

Keyword: gradient

Adaptive Differential Privacy in Federated Learning: A Priority-Based Approach

• Authors: Authors: Mahtab Talaei, Iman Izadi
• Subjects: Cryptography and Security (cs.CR); Distributed, Parallel, and Cluster Computing (cs.DC); Machine Learning (cs.LG)
• Arxiv link: https://arxiv.org/abs/2401.02453
• Pdf link: https://arxiv.org/pdf/2401.02453
• Abstract Federated learning (FL) as one of the novel branches of distributed machine learning (ML), develops global models through a private procedure without direct access to local datasets. However, access to model updates (e.g. gradient updates in deep neural networks) transferred between clients and servers can reveal sensitive information to adversaries. Differential privacy (DP) offers a framework that gives a privacy guarantee by adding certain amounts of noise to parameters. This approach, although being effective in terms of privacy, adversely affects model performance due to noise involvement. Hence, it is always needed to find a balance between noise injection and the sacrificed accuracy. To address this challenge, we propose adaptive noise addition in FL which decides the value of injected noise based on features' relative importance. Here, we first propose two effective methods for prioritizing features in deep neural network models and then perturb models' weights based on this information. Specifically, we try to figure out whether the idea of adding more noise to less important parameters and less noise to more important parameters can effectively save the model accuracy while preserving privacy. Our experiments confirm this statement under some conditions. The amount of noise injected, the proportion of parameters involved, and the number of global iterations can significantly change the output. While a careful choice of parameters by considering the properties of datasets can improve privacy without intense loss of accuracy, a bad choice can make the model performance worse.

GPBiLQ and GPQMR: Two iterative methods for unsymmetric partitioned linear systems

• Authors: Authors: Kui Du, Jia-Jun Fan, Fang Wang
• Subjects: Numerical Analysis (math.NA)
• Arxiv link: https://arxiv.org/abs/2401.02608
• Pdf link: https://arxiv.org/pdf/2401.02608
• Abstract We introduce two iterative methods, GPBiLQ and GPQMR, for solving unsymmetric partitioned linear systems. The basic mechanism underlying GPBiLQ and GPQMR is a novel simultaneous tridiagonalization via biorthogonality that allows for short-recurrence iterative schemes. Similar to the biconjugate gradient method, it is possible to develop another method, GPBiCG, whose iterate (if it exists) can be obtained inexpensively from the GPBiLQ iterate. Whereas the iterate of GPBiCG may not exist, the iterates of GPBiLQ and GPQMR are always well defined as long as the biorthogonal tridiagonal reduction process does not break down. We discuss connections between the proposed methods and some existing methods, and give numerical experiments to illustrate the performance of the proposed methods.

Gradient weighting for speaker verification in extremely low Signal-to-Noise Ratio

• Authors: Authors: Yi Ma, Kong Aik Lee, Ville Hautamäki, Meng Ge, Haizhou Li
• Subjects: Sound (cs.SD); Audio and Speech Processing (eess.AS)
• Arxiv link: https://arxiv.org/abs/2401.02626
• Pdf link: https://arxiv.org/pdf/2401.02626
• Abstract Speaker verification is hampered by background noise, particularly at extremely low Signal-to-Noise Ratio (SNR) under 0 dB. It is difficult to suppress noise without introducing unwanted artifacts, which adversely affects speaker verification. We proposed the mechanism called Gradient Weighting (Grad-W), which dynamically identifies and reduces artifact noise during prediction. The mechanism is based on the property that the gradient indicates which parts of the input the model is paying attention to. Specifically, when the speaker network focuses on a region in the denoised utterance but not on the clean counterpart, we consider it artifact noise and assign higher weights for this region during optimization of enhancement. We validate it by training an enhancement model and testing the enhanced utterance on speaker verification. The experimental results show that our approach effectively reduces artifact noise, improving speaker verification across various SNR levels.

Joint User Association and Power Control for Cell-Free Massive MIMO

• Authors: Authors: Chongzheng Hao, Tung Thanh Vu, Hien Quoc Ngo, Minh N.Dao, Xiaoyu Dang, Chenghua Wang, Michail Matthaiou
• Subjects: Information Theory (cs.IT); Signal Processing (eess.SP)
• Arxiv link: https://arxiv.org/abs/2401.02701
• Pdf link: https://arxiv.org/pdf/2401.02701
• Abstract This work proposes novel approaches that jointly design user equipment (UE) association and power control (PC) in a downlink user-centric cell-free massive multiple-input multiple-output (CFmMIMO) network, where each UE is only served by a set of access points (APs) for reducing the fronthaul signalling and computational complexity. In order to maximize the sum spectral efficiency (SE) of the UEs, we formulate a mixed-integer nonconvex optimization problem under constraints on the per-AP transmit power, quality-of-service rate requirements, maximum fronthaul signalling load, and maximum number of UEs served by each AP. In order to solve the formulated problem efficiently, we propose two different schemes according to the different sizes of the CFmMIMO systems. For small-scale CFmMIMO systems, we present a successive convex approximation (SCA) method to obtain a stationary solution and also develop a learning-based method (JointCFNet) to reduce the computational complexity. For large-scale CFmMIMO systems, we propose a low-complexity suboptimal algorithm using accelerated projected gradient (APG) techniques. Numerical results show that our JointCFNet can yield similar performance and significantly decrease the run time compared with the SCA algorithm in small-scale systems. The presented APG approach is confirmed to run much faster than the SCA algorithm in the large-scale system while obtaining an SE performance close to that of the SCA approach. Moreover, the median sum SE of the APG method is up to about 2.8 fold higher than that of the heuristic baseline scheme.

Survey of a Class of Iterative Row-Action Methods: The Kaczmarz Method

• Authors: Authors: Inês A. Ferreira, Juan A. Acebrón, José Monteiro
• Subjects: Numerical Analysis (math.NA)
• Arxiv link: https://arxiv.org/abs/2401.02842
• Pdf link: https://arxiv.org/pdf/2401.02842
• Abstract The Kaczmarz algorithm is an iterative method that solves linear systems of equations. It stands out among iterative algorithms when dealing with large systems for two reasons. First, at each iteration, the Kaczmarz algorithm uses a single equation, resulting in minimal computational work per iteration. Second, solving the entire system may only require the use of a small subset of the equations. These characteristics have attracted significant attention to the Kaczmarz algorithm. Researchers have observed that randomly choosing equations can improve the convergence rate of the algorithm. This insight led to the development of the Randomized Kaczmarz algorithm and, subsequently, several other variations emerged. In this paper, we extensively analyze the native Kaczmarz algorithm and many of its variations using large-scale dense random systems as benchmarks. Through our investigation, we have verified that, for consistent systems, various row sampling schemes can outperform both the original and Randomized Kaczmarz method. Specifically, sampling without replacement and using quasirandom numbers are the fastest techniques. However, for inconsistent systems, the Conjugate Gradient method for Least-Squares problems overcomes all variations of the Kaczmarz method for these types of systems.

Keyword: super-resolution

There is no result