An official website of the United States government
The advancement of wireless networking has significantly enhanced beamforming capabilities in Autonomous Unmanned Aerial Systems (AUAS). This paper presents a simple and efficient classical algorithm to route a collection of AUAS or drone swarms extending our previous work on AUAS. The algorithm is based on the sparse factorization of frequency Vandermonde matrices that correspond to each drone, and its entries are determined through spatiotemporal data of drones in the AUAS. The algorithm relies on multibeam beamforming, making it suitable for large-scale AUAS networking in wireless communications. We show a reduction in the arithmetic and time complexities of the algorithm through theoretical and numerical results. Finally, we also present an ML-based AUAS routing algorithm using the classical AUAS algorithm and feed-forward neural networks. We compare the beamformed signals of the ML-based AUAS routing algorithm with the ground truth signals to minimize the error between them. The numerical error results show that the ML-based AUAS routing algorithm enhances the accuracy of the routing. This error, along with the numerical and theoretical results for over 100 drones, provides the basis for the scalability of the proposed ML-based AUAS algorithms for large-scale deployments.
more »
« less
Entropy-based convergence rates of greedy algorithms
We present convergence estimates of two types of greedy algorithms in terms of the entropy numbers of underlying compact sets. In the first part, we measure the error of a standard greedy reduced basis method for parametric PDEs by the entropy numbers of the solution manifold in Banach spaces. This contrasts with the classical analysis based on the Kolmogorov [Formula: see text]-widths and enables us to obtain direct comparisons between the algorithm error and the entropy numbers, where the multiplicative constants are explicit and simple. The entropy-based convergence estimate is sharp and improves upon the classical width-based analysis of reduced basis methods for elliptic model problems. In the second part, we derive a novel and simple convergence analysis of the classical orthogonal greedy algorithm for nonlinear dictionary approximation using the entropy numbers of the symmetric convex hull of the dictionary. This also improves upon existing results by giving a direct comparison between the algorithm error and the entropy numbers.
more »
« less
- Award ID(s):
- 2424305
- PAR ID:
- 10521543
- Publisher / Repository:
- World Scientific
- Date Published:
- Journal Name:
- Mathematical Models and Methods in Applied Sciences
- Volume:
- 34
- Issue:
- 05
- ISSN:
- 0218-2025
- Page Range / eLocation ID:
- 779 to 802
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
The paper introduces the first formulation of convex Q-learning for Markov decision processes with function approximation. The algorithms and theory rest on a relaxation of a dual of Manne's celebrated linear programming characterization of optimal control. The main contributions firstly concern properties of the relaxation, described as a deterministic convex program: we identify conditions for a bounded solution, a significant connection between the solution to the new convex program, and the solution to standard Q-learning with linear function approximation. The second set of contributions concern algorithm design and analysis: (i) A direct model-free method for approximating the convex program for Q-learning shares properties with its ideal. In particular, a bounded solution is ensured subject to a simple property of the basis functions; (ii) The proposed algorithms are convergent and new techniques are introduced to obtain the rate of convergence in a mean-square sense; (iii) The approach can be generalized to a range of performance criteria, and it is found that variance can be reduced by considering ``relative'' dynamic programming equations; (iv) The theory is illustrated with an application to a classical inventory control problem.more » « less
-
We introduce Neural Radiosity, an algorithm to solve the rendering equation by minimizing the norm of its residual, similar as in classical radiosity techniques. Traditional basis functions used in radiosity, such as piecewise polynomials or meshless basis functions are typically limited to representing isotropic scattering from diffuse surfaces. Instead, we propose to leverage neural networks to represent the full four-dimensional radiance distribution, directly optimizing network parameters to minimize the norm of the residual. Our approach decouples solving the rendering equation from rendering (perspective) images similar as in traditional radiosity techniques, and allows us to efficiently synthesize arbitrary views of a scene. In addition, we propose a network architecture using geometric learnable features that improves convergence of our solver compared to previous techniques. Our approach leads to an algorithm that is simple to implement, and we demonstrate its effectiveness on a variety of scenes with diffuse and non-diffuse surfaces.more » « less
-
Identifying governing equations for a dynamical system is a topic of critical interest across an array of disciplines, from mathematics to engineering to biology. Machine learning—specifically deep learning—techniques have shown their capabilities in approximating dynamics from data, but a shortcoming of traditional deep learning is that there is little insight into the underlying mapping beyond its numerical output for a given input. This limits their utility in analysis beyond simple prediction. Simultaneously, a number of strategies exist which identify models based on a fixed dictionary of basis functions, but most either require some intuition or insight about the system, or are susceptible to overfitting or a lack of parsimony. Here, we present a novel approach that combines the flexibility and accuracy of deep learning approaches with the utility of symbolic solutions: a deep neural network that generates a symbolic expression for the governing equations. We first describe the architecture for our model and then show the accuracy of our algorithm across a range of classical dynamical systems.more » « less
-
Discriminating between quantum states is a fundamental task in quantum information theory. Given two quantum states, ρ+ and ρ− , the Helstrom measurement distinguishes between them with minimal probability of error. However, finding and experimentally implementing the Helstrom measurement can be challenging for quantum states on many qubits. Due to this difficulty, there is a great interest in identifying local measurement schemes which are close to optimal. In the first part of this work, we generalize previous work by Acin et al. (Phys. Rev. A 71, 032338) and show that a locally greedy (LG) scheme using Bayesian updating can optimally distinguish between any two states that can be written as a tensor product of arbitrary pure states. We then show that the same algorithm cannot distinguish tensor products of mixed states with vanishing error probability (even in a large subsystem limit), and introduce a modified locally-greedy (MLG) scheme with strictly better performance. In the second part of this work, we compare these simple local schemes with a general dynamic programming (DP) approach. The DP approach finds the optimal series of local measurements and optimal order of subsystem measurement to distinguish between the two tensor-product states.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1142/S0218202524500143
