Data-Driven Reachability Analysis from Noisy Data

• URL: http://arxiv.org/abs/2105.07229v1
• Date: Sat, 15 May 2021 14:11:57 GMT
• Title: Data-Driven Reachability Analysis from Noisy Data
• Authors: Amr Alanwar, Anne Koch, Frank Allg\"ower, Karl Henrik Johansson
• Abstract summary: We consider the problem of computing reachable sets directly from noisy data without a given system model. Several reachability algorithms are presented, and their accuracy is shown to depend on the underlying system generating the data.
• Score: 5.949143454441281
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of computing reachable sets directly from noisy data without a given system model. Several reachability algorithms are presented, and their accuracy is shown to depend on the underlying system generating the data. First, an algorithm for computing over-approximated reachable sets based on matrix zonotopes is proposed for linear systems. Constrained matrix zonotopes are introduced to provide less conservative reachable sets at the cost of increased computational expenses and utilized to incorporate prior knowledge about the unknown system model. Then we extend the approach to polynomial systems and under the assumption of Lipschitz continuity to nonlinear systems. Theoretical guarantees are given for these algorithms in that they give a proper over-approximative reachable set containing the true reachable set. Multiple numerical examples show the applicability of the introduced algorithms, and accuracy comparisons are made between algorithms.

Related papers

• Large-Scale OD Matrix Estimation with A Deep Learning Method [70.78575952309023]
  The proposed method integrates deep learning and numerical optimization algorithms to infer matrix structure and guide numerical optimization. We conducted tests to demonstrate the good generalization performance of our method on a large-scale synthetic dataset.
  arXiv  Detail & Related papers  (2023-10-09T14:30:06Z)
• Learning to Relax: Setting Solver Parameters Across a Sequence of Linear System Instances [42.16343861129583]
  We show that a bandit online learning algorithm can select parameters for a sequence of instances such that the overall cost approaches that of the best fixed $omega$ as the sequence length increases. Our work provides the first learning-theoretic treatment of high-precision linear system solvers and the first end-to-end guarantees for data-driven scientific computing.
  arXiv  Detail & Related papers  (2023-10-03T17:51:42Z)
• Randomized Polar Codes for Anytime Distributed Machine Learning [66.46612460837147]
  We present a novel distributed computing framework that is robust to slow compute nodes, and is capable of both approximate and exact computation of linear operations. We propose a sequential decoding algorithm designed to handle real valued data while maintaining low computational complexity for recovery. We demonstrate the potential applications of this framework in various contexts, such as large-scale matrix multiplication and black-box optimization.
  arXiv  Detail & Related papers  (2023-09-01T18:02:04Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space. We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size. We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
  arXiv  Detail & Related papers  (2023-02-14T22:12:16Z)
• Bayesian Spline Learning for Equation Discovery of Nonlinear Dynamics with Quantified Uncertainty [8.815974147041048]
  We develop a novel framework to identify parsimonious governing equations of nonlinear (spatiotemporal) dynamics from sparse, noisy data with quantified uncertainty. The proposed algorithm is evaluated on multiple nonlinear dynamical systems governed by canonical ordinary and partial differential equations.
  arXiv  Detail & Related papers  (2022-10-14T20:37:36Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph. Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.
  arXiv  Detail & Related papers  (2021-09-10T07:01:15Z)
• Reachability Analysis of Neural Feedback Loops [34.94930611635459]
  This work focuses on estimating the forward reachable set of textitneural feedback loops (closed-loop systems with NN controllers) Recent work provides bounds on these reachable sets, but the computationally tractable approaches yield overly conservative bounds. This work bridges the gap by formulating a convex optimization problem for the reachability analysis of closed-loop systems with NN controllers.
  arXiv  Detail & Related papers  (2021-08-09T16:11:57Z)
• Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
  We study algorithms for estimating the statistical leverage scores of rectangular dense or sparse matrices of arbitrary rank. Our approach is based on combining rank revealing methods with compositions of dense and sparse randomized dimensionality reduction transforms.
  arXiv  Detail & Related papers  (2021-05-23T19:21:55Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  We propose a simple and efficient unsupervised feature selection method, by combining reconstruction error with $l_2,p$-norm regularization. We present an efficient optimization algorithm to solve the proposed unsupervised model, and analyse the convergence and computational complexity of the algorithm theoretically.
  arXiv  Detail & Related papers  (2020-12-29T04:08:38Z)
• Data-Driven Reachability Analysis Using Matrix Zonotopes [5.6184230760292175]
  We propose a data-driven reachability analysis approach from noisy data. We first provide an algorithm for over-approximating the reachable set of a linear time-invariant system. We then introduce an extension for Lipschitz nonlinear systems.
  arXiv  Detail & Related papers  (2020-11-17T06:48:23Z)
• Estimating Multiple Precision Matrices with Cluster Fusion Regularization [0.90238471756546]
  We propose a penalized likelihood estimating multiple precision matrices from different classes. Most existing methods either incorporate no information on relationships between the precision matrices, or require this information be a priori.
  arXiv  Detail & Related papers  (2020-03-01T01:03:22Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.