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

On computing approximate Lewis weights

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Apers, Simon Gribling, Sander Sidford, Aaron Université Paris Cité CNRS IRIF Paris France Tilburg University Netherlands Stanford University United States

In this note we provide and analyze a simple method that given an n × d matrix, outputs approximate p-Lewis weights, a natural measure of the importance of the rows with respect to the p norm, for p ≥ 2. More precisely, we provide a simple post-processing procedure that turns natural one-sided approximate p-Lewis weights into two-sided approximations. When combined with a simple one-sided approximation algorithm presented by Lee (PhD thesis, ‘16) this yields an algorithm for computing two-sided approximations of the p-Lewis weights of an n × d-matrix using poly(d, p) approximate leverage score computations. While efficient high-accuracy algorithms for approximating p-Lewis had been established previously by Fazel, Lee, Padmanabhan and Sidford (SODA ‘22), the simple structure and approximation tolerance of our algorithm may make it of use for different applications. © 2024, CC BY.

关键词： approximation algorithms

Fast Orthogonal Matching Pursuit through Successive Regression

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Yu, Huiyuan He, Jia Cheng, Maggie Illinois Institute of Technology ChicagoIL60616 United States

Orthogonal Matching Pursuit (OMP) has been a powerful method in sparse signal recovery and approximation. However, OMP suffers computational issues when the signal has a large number of non-zeros. This paper advances OMP and its extension called generalized OMP (gOMP) by offering fast algorithms for the orthogonal projection of the input signal at each iteration. The proposed modifications directly reduce the computational complexity of OMP and gOMP. Experiment results verified the improvement in computation time. This paper also provides sufficient conditions for exact signal recovery. For general signals with additive noise, the approximation error is at the same order as OMP (gOMP), but is obtained within much less time. © 2024, CC BY.

关键词： approximation algorithms

Bosehedral: Compiler Optimization for Bosonic Quantum Computing

学校读者我要写书评

暂无评论

Bosehedral: Compiler Optimization for Bosonic Quantum Comput...

Annual International Symposium on Computer Architecture, ISCA

作者： Junyu Zhou Yuhao Liu Yunong Shi Ali Javadi-Abhari Gushu Li Department of Computer and Information Science University of Pennsylvania Philadelphia USA AWS Quantum Technology New York USA IBM Quantum New York USA

ISBN: (数字)9798350326581

ISBN: (纸本)9798350326598

Bosonic quantum computing, based on the infinite-dimensional qumodes, has shown promise for various practical applications that are classically hard. However, the lack of compiler optimizations has hindered its full potential. This paper introduces Bosehedral, an efficient compiler optimization framework for (Gaussian) Boson sampling on Bosonic quantum hardware. Bosehedral overcomes the challenge of handling infinite-dimensional qumode gate matrices by performing all its program analysis and optimizations at a higher algorithmic level, using a compact unitary matrix representation. It optimizes qumode gate decomposition and logical-to-physical qumode mapping, and introduces a tunable probabilistic gate dropout method. Overall, Bosehedral significantly improves the performance by accurately approximating the original program with much fewer gates. Our evaluation shows that Bosehedral can largely reduce the program size but still maintain a high approximation fidelity, which can translate to significant end-to-end application performance improvement.

关键词： Quantum computing Computer architecture Logic gates Probabilistic logic approximation algorithms Hardware Matrix decomposition

Evolution and Recent Trends for the SGD Algorithm: Key Takeaways from an Educational Short Course

学校读者我要写书评

暂无评论

Evolution and Recent Trends for the SGD Algorithm: Key Takea...

European Signal Processing Conference (EUSIPCO)

作者： Paul Rodriguez Department of Electrical Engineering Pontificia Universidad Católica del Perú Lima Peru

ISBN: (数字)9789464593617

ISBN: (纸本)9798331519773

One of the key challenges when designing a ten (10) hours educational short course, entitled “A Hands-on Approach for Implementing Stochastic Optimization algorithms from Scratch”, which was accepted for inclusion at ICASSP'23, was related to addressing “how to introduce the Stochastic Gradient Descent (SGD) algorithm and variants in a consistent, accessible fashion”? From a simplistic perspective, the SGD algorithm is nothing else than the classical gradient descent (GD) algorithm along with a (very) noisy gradient. Nonetheless, arguably, SGD's most influential variants, e.g. AdaGrad, RMSprop and Adam, nor more recent ones (LookAhead, E-Adam, MadGrad, among several others) may not be explained in such superficial terms. Moreover, such variants are usually given as as black-boxes by most deep-learning (DL) libraries (e.g. TensorFlow, PyTorch, etc.). In this article, based on the experience of the aforementioned short-course, I propose to link the SGD algorithm and variants via an “evolutionary path”, in which each SGD variant may be understood as a set of add-on features over the vanilla SGD, resulting in a generalized algorithm along with a “family tree” graph which are both intuitive and useful when implementing a given SGD variant.

关键词： Geometry Signal processing algorithms Europe Closed box Signal processing Market research approximation algorithms Libraries Noise measurement Optimization

Performance Analysis of VLSI Architecture of Dadda Multiplier Using Divide and Conquer Strategy with Approximate Adders

学校读者我要写书评

暂无评论

Performance Analysis of VLSI Architecture of Dadda Multiplie...

Emerging Trends in Engineering and Medical Sciences (ICETEMS), International Conference on

作者： Bala Sindhuri Kandula Raghumandala Devi Muddala Kamakshi Devi Pilli Gamya Geethika Prodduturi Hitesh P Y N S Vara Prasad Department of E.C.E. S.R.K.R Engineering College (A) Bhimavaram India

ISBN: (数字)9798331529352

ISBN: (纸本)9798331529390

Multiplication plays a pivotal role in diverse fields, including digital signal processing, scientific computing, machine learning, cryptography, computer graphics, control systems, finance, and embedded systems. Optimizing multiplication operations can significantly enhance performance and efficiency across these domains. This paper presents a VLSI architecture for a hardware multiplier module that utilizes the Dadda algorithm in conjunction with the Divide and Conquer strategy, incorporating Approximate Adders. These adders strike a balance between accuracy and resource efficiency, leading to reductions in power consumption and silicon area. Approximate Adders are essential in optimizing power, area, speed, and heat dissipation in digital systems, particularly in applications where absolute precision is not important. This work underscores the potential of integrating approximate computing with efficient multiplication techniques to advance digital circuit design. The architecture is implemented in Verilog, and its functionality is validated using Vivado 2023.2 and Cadence tools.

关键词： Power demand Approximate computing Signal processing algorithms Computer architecture Very large scale integration approximation algorithms Hardware Performance analysis Delays Adders

Filtering and smoothing estimation algorithms from uncertain nonlinear observations with time-correlated additive noise and random deception attacks

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Caballero-Águila, R. Hu, J. Linares-Pérez, J. Departamento de Estadística Universidad de Jaén Paraje Las Lagunillas. Jaén23071 Spain Key Laboratory of Advanced Manufacturing and Intelligent Technology Ministry of Education Harbin University of Science and Technology Harbin150080 China Departamento de Estadística Universidad de Granada Avenida Fuentenueva. Granada18071 Spain

This paper discusses the problem of estimating a stochastic signal from nonlinear uncertain observations with time-correlated additive noise described by a first-order Markov process. Random deception attacks are assumed to be launched by an adversary, and both this phenomenon and the uncertainty in the observations are modelled by two sets of Bernoulli random variables. Under the assumption that the evolution model generating the signal to be estimated is unknown and only the mean and covariance functions of the processes involved in the observation equation are available, recursive algorithms based on linear approximations of the real observations are proposed for the least-squares filtering and fixed-point smoothing problems. Finally, the feasibility and effectiveness of the developed estimation algorithms are verified by a numerical simulation example, where the impact of uncertain observation and deception attack probabilities on estimation accuracy is evaluated. Copyright © 2024, The Authors. All rights reserved.

关键词： approximation algorithms

Coevolution with Bee Colony: Paradigm Shift in Many Objective Optimization

学校读者我要写书评

暂无评论

Coevolution with Bee Colony: Paradigm Shift in Many Objectiv...

Emerging Trends in Industry 4.0 (ETI 4.0)

作者： Selina Khoirom Shreya Pramanik Pratyusha Rakshit Archana Chowdhury Department of Electronics and Telecommunication Engineering Jadavpur University India Department of Computer Science and Engineering Christian College Of Engineering and Technology Bhilai

ISBN: (数字)9798350373783

ISBN: (纸本)9798350373790

The research offers a unique coevolution-based many-objective optimization (MaOO) approach to benefit from the underlying parallelism of the evolutionary process. The proposed MaOO handles individual objectives in parallel using artificial bee colony (ABC) algorithm. After achieving convergence, a group of good-quality solutions is carefully chosen from each ABC population, dealing with a specific objective. Next, the groups are combined to form a union set. Finally, a fuzzy membership-induced rank measure is developed to discover the top-ranked equally good members of the union set, showing the approximate Pareto optimal solutions to the given MaOO problem. The proposed MaOO algorithm, referred to as fuzzy-bee colony (FBC) is compared with three state-of-the-art techniques. Experiments undertaken reveal that FBC outperforms its contenders with respect to the performance metrics.

关键词： Measurement Technological innovation Decision making Focusing Pareto optimization Parallel processing approximation algorithms

Adaptive Meta-Learning-based KKL Observer Design for Nonlinear Dynamical Systems

学校读者我要写书评

暂无评论

Adaptive Meta-Learning-based KKL Observer Design for Nonline...

European Control Conference (ECC)

作者： Lukas Trommer Halil Yiğit Öksüz Control Systems Group Technical University of Berlin Germany Control Systems Group and Science of Intelligence Research Cluster of Excellence Technical University of Berlin Germany

ISBN: (数字)9783907144107

ISBN: (纸本)9798331540920

The theory of Kazantzis-Kravaris/Luenberger (KKL) observer design introduces a methodology that uses a nonlinear transformation map and its left inverse to estimate the state of a nonlinear system through the introduction of a linear observer state space. Data-driven approaches using artificial neural networks have demonstrated the ability to accurately approximate these transformation maps. This paper presents a novel approach to observer design for nonlinear dynamical systems through meta-learning, a concept in machine learning that aims to optimize learning models for fast adaptation to a distribution of tasks through an improved focus on the intrinsic properties of the underlying learning problem. We introduce a framework that leverages information from measurements of the system output to design a learning-based KKL observer capable of online adaptation to a variety of system conditions and attributes. To validate the effectiveness of our approach, we present comprehensive experimental results for the estimation of nonlinear system states with varying initial conditions and internal parameters, demonstrating high accuracy, generalization capability, and robustness against noise.

关键词： Metalearning Training Time-frequency analysis Accuracy Estimation Observers approximation algorithms

Balanced Truncation via Tangential Interpolation

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Zulfiqar, Umair Song, Qiu-Yan Xiao, Zhi-Hua Sreeram, Victor School of Electronic Information and Electrical Engineering Yangtze University Hubei Jingzhou434023 China School of Mechatronic Engineering and Automation Shanghai University Shanghai200444 China School of Statistics and Data Science Nanjing Audit University Jiangsu Nanjing211815 China Department of Electrical Electronic and Computer Engineering The University of Western Australia Perth6009 Australia

This paper examines the construction of rth-order truncated balanced realizations via tangential interpolation at r specified interpolation points. It is demonstrated that when the truncated Hankel singular values are negligible—that is, when the discarded states are nearly uncontrollable and unobservable—balanced truncation simplifies to a bi-tangential Hermite interpolation problem at r interpolation points. In such cases, the resulting truncated balanced realization is nearly H2-optimal and thus interpolates the original model at the mirror images of its poles along its residual directions. Additionally, it is shown that existing low-rank balanced truncation algorithms implicitly perform block interpolation to construct a surrogate for the original system, which is subsequently reduced to obtain an approximate truncated balanced realization. Like standard H2-optimal model reduction, where the interpolation points and tangential directions that yield a local optimum are not known, in balanced truncation as well, the interpolation points and tangential directions required to produce a truncated balanced realization remain unknown. To address this, we propose an iterative tangential interpolation-based algorithm for balanced truncation. This algorithm starts with an initial guess of an rth-order truncated balanced realization and iteratively refines the interpolation data by performing tangential interpolation at the mirror images of the poles of the current low-rank truncated balanced realization in the residual directions. In each iteration, the rank of the approximated Gramians is incremented by r, followed by low-rank balanced truncation to generate updated interpolation data for the subsequent step. As the Gramian rank increases and the approximation improves, the relative changes in both the interpolation data and approximate Hankel singular values stagnate. Upon convergence, the algorithm yields a low-rank truncated balanced realization that accurately preser

关键词： approximation algorithms