-
Low-rank Tensor Autoregressive Predictor for Third-Order Time-Series Forecasting
Authors:
Haoning Wang,
Liping Zhang,
Shengbo Eben Li
Abstract:
Recently, tensor time-series forecasting has gained increasing attention, whose core requirement is how to perform dimensionality reduction. Among all multidimensional data, third-order tensor is the most prevalent structure in real-world scenarios, such as RGB images and network traffic data. Previous studies in this field are mainly based on tensor Tucker decomposition and such methods have limi…
▽ More
Recently, tensor time-series forecasting has gained increasing attention, whose core requirement is how to perform dimensionality reduction. Among all multidimensional data, third-order tensor is the most prevalent structure in real-world scenarios, such as RGB images and network traffic data. Previous studies in this field are mainly based on tensor Tucker decomposition and such methods have limitations in terms of computational cost, with iteration complexity of approximately $O(2n^3r)$, where $n$ and $r$ are the dimension and rank of original tensor data. Moreover, many real-world data does not exhibit the low-rank property under Tucker decomposition, which may fail the dimensionality reduction. In this paper, we pioneer the application of tensor singular value decomposition (t-SVD) to third-order time-series, which builds an efficient forecasting algorithm, called Low-rank Tensor Autoregressive Predictor (LOTAP). We observe that tensor tubal rank in t-SVD is always less than Tucker rank, which leads to great benefit in computational complexity. By combining it with the autoregressive (AR) model, the forecasting problem is formulated as a least squares optimization. We divide such an optimization problem by fast Fourier transformation into four decoupled subproblems, whose variables include regressive coefficient, f-diagonal tensor, left and right orthogonal tensors. The alternating minimization algorithm is proposed with iteration complexity of about $O(n^3 + n^2r^2)$, in which each subproblem has a closed-form solution. Numerical experiments show that, compared to Tucker-decomposition-based algorithms, LOTAP achieves a speed improvement ranging from 2 to 6 times while maintaining accurate forecasting performance in all four baseline tasks. In addition, LOTAP is applicable to a wider range of tensor forecasting tasks due to its more effective dimensionality reduction ability.
△ Less
Submitted 5 March, 2024;
originally announced March 2024.
-
On the atomicity of power monoids of Puiseux monoids
Authors:
Victor Gonzalez,
Eddy Li,
Henrick Rabinovitz,
Pedro Rodriguez,
Marcos Tirador
Abstract:
A submonoid of the additive group $\mathbb{Q}$ is called a Puiseux monoid if it consists of nonnegative rationals. Given a monoid $M$, the set consisting of all nonempty finite subsets of $M$ is also a monoid under the Minkowski sum, and it is called the (finitary) power monoid of $M$. In this paper we study atomicity and factorization properties in power monoids of Puiseux monoids. We specially f…
▽ More
A submonoid of the additive group $\mathbb{Q}$ is called a Puiseux monoid if it consists of nonnegative rationals. Given a monoid $M$, the set consisting of all nonempty finite subsets of $M$ is also a monoid under the Minkowski sum, and it is called the (finitary) power monoid of $M$. In this paper we study atomicity and factorization properties in power monoids of Puiseux monoids. We specially focus on the ascent of the property of being atomic and both the bounded and the finite factorization properties (the ascending chain on principal ideals and the length-finite factorization properties are also considered here). We prove that both the bounded and the finite factorization properties ascend from any Puiseux monoid to its power monoid. On the other hand, we construct an atomic Puiseux monoid whose power monoid is not atomic. We also prove that the existence of maximal common divisors for nonempty finite subsets is a sufficient condition for the property of being atomic to ascend from a Puiseux monoid to its power monoid.
△ Less
Submitted 22 January, 2024;
originally announced January 2024.
-
Optimization Landscape of Policy Gradient Methods for Discrete-time Static Output Feedback
Authors:
Jingliang Duan,
Jie Li,
Xuyang Chen,
Kai Zhao,
Shengbo Eben Li,
Lin Zhao
Abstract:
In recent times, significant advancements have been made in delving into the optimization landscape of policy gradient methods for achieving optimal control in linear time-invariant (LTI) systems. Compared with state-feedback control, output-feedback control is more prevalent since the underlying state of the system may not be fully observed in many practical settings. This paper analyzes the opti…
▽ More
In recent times, significant advancements have been made in delving into the optimization landscape of policy gradient methods for achieving optimal control in linear time-invariant (LTI) systems. Compared with state-feedback control, output-feedback control is more prevalent since the underlying state of the system may not be fully observed in many practical settings. This paper analyzes the optimization landscape inherent to policy gradient methods when applied to static output feedback (SOF) control in discrete-time LTI systems subject to quadratic cost. We begin by establishing crucial properties of the SOF cost, encompassing coercivity, L-smoothness, and M-Lipschitz continuous Hessian. Despite the absence of convexity, we leverage these properties to derive novel findings regarding convergence (and nearly dimension-free rate) to stationary points for three policy gradient methods, including the vanilla policy gradient method, the natural policy gradient method, and the Gauss-Newton method. Moreover, we provide proof that the vanilla policy gradient method exhibits linear convergence towards local minima when initialized near such minima. The paper concludes by presenting numerical examples that validate our theoretical findings. These results not only characterize the performance of gradient descent for optimizing the SOF problem but also provide insights into the effectiveness of general policy gradient methods within the realm of reinforcement learning.
△ Less
Submitted 29 October, 2023;
originally announced October 2023.
-
Transversals in a collections of trees
Authors:
Ethan Y. H. Li,
Luyi Li,
Ping Li
Abstract:
Let $\mathcal{S}$ be a fixed family of graphs on vertex set $V$ and $\mathcal{G}$ be a collection of elements in $\mathcal{S}$. We investigated the transversal problem of finding the maximum value of $|\mathcal{G}|$ when $\mathcal{G}$ contains no rainbow elements in $\mathcal{S}$. Specifically, we determine the exact values when $\mathcal{S}$ is a family of stars or a family of trees of the same o…
▽ More
Let $\mathcal{S}$ be a fixed family of graphs on vertex set $V$ and $\mathcal{G}$ be a collection of elements in $\mathcal{S}$. We investigated the transversal problem of finding the maximum value of $|\mathcal{G}|$ when $\mathcal{G}$ contains no rainbow elements in $\mathcal{S}$. Specifically, we determine the exact values when $\mathcal{S}$ is a family of stars or a family of trees of the same order $n$ with $n$ dividing $|V|$. Further, all the extremal cases for $\mathcal{G}$ are characterized.
△ Less
Submitted 10 October, 2023;
originally announced October 2023.
-
Induced log-concavity of equivariant matroid invariants
Authors:
Alice L. L. Gao,
Ethan Y. H. Li,
Matthew H. Y. Xie,
Arthur L. B. Yang,
Zhong-Xue Zhang
Abstract:
Inspired by the notion of equivariant log-concavity, we introduce the concept of induced log-concavity for a sequence of representations of a finite group. For an equivariant matroid equipped with a symmetric group action or a finite general linear group action, we transform the problem of proving the induced log-concavity of matroid invariants to that of proving the Schur positivity of symmetric…
▽ More
Inspired by the notion of equivariant log-concavity, we introduce the concept of induced log-concavity for a sequence of representations of a finite group. For an equivariant matroid equipped with a symmetric group action or a finite general linear group action, we transform the problem of proving the induced log-concavity of matroid invariants to that of proving the Schur positivity of symmetric functions. We prove the induced log-concavity of the equivariant Kazhdan-Lusztig polynomials of $q$-niform matroids equipped with the action of a finite general linear group, as well as that of the equivariant Kazhdan-Lusztig polynomials of uniform matroids equipped with the action of a symmetric group.
As a consequence of the former, we obtain the log-concavity of Kazhdan-Lusztig polynomials of $q$-niform matroids, thus providing further positive evidence for Elias, Proudfoot and Wakefield's log-concavity conjecture on the matroid Kazhdan-Lusztig polynomials. From the latter we obtain the log-concavity of Kazhdan-Lusztig polynomials of uniform matroids, which was recently proved by Xie and Zhang by using a computer algebra approach. We also establish the induced log-concavity of the equivariant characteristic polynomials and the equivariant inverse Kazhdan-Lusztig polynomials for $q$-niform matroids and uniform matroids.
△ Less
Submitted 19 July, 2023;
originally announced July 2023.
-
SOS
Authors:
Jasper Caravan,
Michael Han,
Andrew Kalashnikov,
Tanya Khovanova,
Ella Li,
Alexander Meng,
Vaibhav Rastogi,
Gordon Redwine,
Lev Strougov,
Angela Zhao
Abstract:
SOS is a game similar to tic-tac-toe. We study a variety of variations of it played on a 1-by-$n$ rectangle. On our journey we change the target string to SOO, then study all target strings containing SSS, then go back to finite strings and study SOSO. Then we create a variation with two target strings SSSS-OOOO. We continue with misère games. After that we look at different changes of the board:…
▽ More
SOS is a game similar to tic-tac-toe. We study a variety of variations of it played on a 1-by-$n$ rectangle. On our journey we change the target string to SOO, then study all target strings containing SSS, then go back to finite strings and study SOSO. Then we create a variation with two target strings SSSS-OOOO. We continue with misère games. After that we look at different changes of the board: we wrap the board around, add dimension, and allow it to expand. We end with a variation that came from the ultimate tic-tac-toe.
△ Less
Submitted 9 June, 2023;
originally announced June 2023.
-
Quantifying the Individual Differences of Driver' Risk Perception with Just Four Interpretable Parameters
Authors:
Chen Chen,
Zhiqian Lan,
Guojian Zhan,
Yao Lyu,
Bingbing Nie,
Shengbo Eben Li
Abstract:
There will be a long time when automated vehicles are mixed with human-driven vehicles. Understanding how drivers assess driving risks and modelling their individual differences are significant for automated vehicles to develop human-like and customized behaviors, so as to gain people's trust and acceptance. However, the reality is that existing driving risk models are developed at a statistical l…
▽ More
There will be a long time when automated vehicles are mixed with human-driven vehicles. Understanding how drivers assess driving risks and modelling their individual differences are significant for automated vehicles to develop human-like and customized behaviors, so as to gain people's trust and acceptance. However, the reality is that existing driving risk models are developed at a statistical level, and no one scenario-universal driving risk measure can correctly describe risk perception differences among drivers. We proposed a concise yet effective model, called Potential Damage Risk (PODAR) model, which provides a universal and physically meaningful structure for driving risk estimation and is suitable for general non-collision and collision scenes. In this paper, based on an open-accessed dataset collected from an obstacle avoidance experiment, four physical-interpretable parameters in PODAR, including prediction horizon, damage scale, temporal attenuation, and spatial attention, are calibrated and consequently individual risk perception models are established for each driver. The results prove the capacity and potential of PODAR to model individual differences in perceived driving risk, laying the foundation for autonomous driving to develop human-like behaviors.
△ Less
Submitted 20 November, 2022;
originally announced November 2022.
-
An E-PINN assisted practical uncertainty quantification for inverse problems
Authors:
Xinchao Jiang,
Xin Wanga,
Ziming Wena,
Enying Li,
Hu Wang
Abstract:
How to solve inverse problems is the challenge of many engineering and industrial applications. Recently, physics-informed neural networks (PINNs) have emerged as a powerful approach to solve inverse problems efficiently. However, it is difficult for PINNs to quantify the uncertainty of results. Therefore, this study proposed ensemble PINNs (E-PINNs) to handle this issue. The E-PINN uses ensemble…
▽ More
How to solve inverse problems is the challenge of many engineering and industrial applications. Recently, physics-informed neural networks (PINNs) have emerged as a powerful approach to solve inverse problems efficiently. However, it is difficult for PINNs to quantify the uncertainty of results. Therefore, this study proposed ensemble PINNs (E-PINNs) to handle this issue. The E-PINN uses ensemble statistics of several basic models to provide uncertainty quantifications for the inverse solution based on the PINN framework, and it is employed to solve the inverse problems in which the unknown quantity is propagated through partial differential equations (PDEs), especially the identification of the unknown field (e.g., space function) of a given physical system. Compared with other data-driven approaches, the suggested method is more than straightforward to implement, and also obtains high-quality uncertainty estimates of the quantity of interest (QoI) without significantly increasing the complexity of the algorithm. This work discusses the good properties of ensemble learning in field inversion and uncertainty quantification. The effectiveness of the proposed method is demonstrated through several numerical experiments. To enhance the robustness of models, adversarial training (AT) is applied. Furthermore, an adaptive active sampling (AS) strategy based on the uncertainty estimates from E-PINNs is also proposed to improve the accuracy of material field inversion problems.
△ Less
Submitted 21 September, 2022;
originally announced September 2022.
-
Stack operation of tensor networks
Authors:
Tianning Zhang,
Tianqi Chen,
Erping Li,
Bo Yang,
L. K. Ang
Abstract:
The tensor network, as a facterization of tensors, aims at performing the operations that are common for normal tensors, such as addition, contraction and stacking. However, due to its non-unique network structure, only the tensor network contraction is so far well defined. In this paper, we propose a mathematically rigorous definition for the tensor network stack approach, that compress a large a…
▽ More
The tensor network, as a facterization of tensors, aims at performing the operations that are common for normal tensors, such as addition, contraction and stacking. However, due to its non-unique network structure, only the tensor network contraction is so far well defined. In this paper, we propose a mathematically rigorous definition for the tensor network stack approach, that compress a large amount of tensor networks into a single one without changing their structures and configurations. We illustrate the main ideas with the matrix product states based machine learning as an example. Our results are compared with the for loop and the efficient coding method on both CPU and GPU.
△ Less
Submitted 24 May, 2022; v1 submitted 28 March, 2022;
originally announced March 2022.
-
Optimization Landscape of Gradient Descent for Discrete-time Static Output Feedback
Authors:
Jingliang Duan,
Jie Li,
Shengbo Eben Li,
Lin Zhao
Abstract:
In this paper, we analyze the optimization landscape of gradient descent methods for static output feedback (SOF) control of discrete-time linear time-invariant systems with quadratic cost. The SOF setting can be quite common, for example, when there are unmodeled hidden states in the underlying process. We first establish several important properties of the SOF cost function, including coercivity…
▽ More
In this paper, we analyze the optimization landscape of gradient descent methods for static output feedback (SOF) control of discrete-time linear time-invariant systems with quadratic cost. The SOF setting can be quite common, for example, when there are unmodeled hidden states in the underlying process. We first establish several important properties of the SOF cost function, including coercivity, L-smoothness, and M-Lipschitz continuous Hessian. We then utilize these properties to show that the gradient descent is able to converge to a stationary point at a dimension-free rate. Furthermore, we prove that under some mild conditions, gradient descent converges linearly to a local minimum if the starting point is close to one. These results not only characterize the performance of gradient descent in optimizing the SOF problem, but also shed light on the efficiency of general policy gradient methods in reinforcement learning.
△ Less
Submitted 10 March, 2022; v1 submitted 27 September, 2021;
originally announced September 2021.
-
A planar network proof for Hankel total positivity of type $B$ Narayana polynomials
Authors:
Ethan Y. H. Li,
Grace M. X. Li,
Arthur L. B. Yang,
Candice X. T. Zhang
Abstract:
The Hankel matrix of type B Narayana polynomials was proved to be totally positive by Wang and Zhu, and independently by Sokal. Pan and Zeng raised the problem of giving a planar network proof of this result. In this paper, we present such a proof by constructing a planar network allowing negative weights, applying the Lindström-Gessel-Viennot lemma and establishing an involution on the set of non…
▽ More
The Hankel matrix of type B Narayana polynomials was proved to be totally positive by Wang and Zhu, and independently by Sokal. Pan and Zeng raised the problem of giving a planar network proof of this result. In this paper, we present such a proof by constructing a planar network allowing negative weights, applying the Lindström-Gessel-Viennot lemma and establishing an involution on the set of nonintersecting families of directed paths.
△ Less
Submitted 22 July, 2021;
originally announced July 2021.
-
Immanant Positivity for Catalan-Stieltjes Matrices
Authors:
Ethan Y. H. Li,
Grace M. X. Li,
Arthur L. B. Yang,
Candice X. T. Zhang
Abstract:
In this paper we give some sufficient conditions for the nonnegativity of immanants of square submatrices of Catalan-Stieltjes matrices and their corresponding Hankel matrices. To obtain these sufficient conditions, we construct new planar networks with a recursive nature for Catalan-Stieltjes matrices. As applications, we provide a unified way to produce inequalities for many combinatorial polyno…
▽ More
In this paper we give some sufficient conditions for the nonnegativity of immanants of square submatrices of Catalan-Stieltjes matrices and their corresponding Hankel matrices. To obtain these sufficient conditions, we construct new planar networks with a recursive nature for Catalan-Stieltjes matrices. As applications, we provide a unified way to produce inequalities for many combinatorial polynomials, such as the Eulerian polynomials, Schröder polynomials and Narayana polynomials.
△ Less
Submitted 24 June, 2021;
originally announced June 2021.
-
The twinning operation on graphs does not always preserve $e$-positivity
Authors:
Ethan Y. H. Li,
Grace M. X. Li,
David G. L. Wang,
Arthur L. B. Yang
Abstract:
Motivated by Stanley's $\mathbf{(3+1)}$-free conjecture on chromatic symmetric functions, Foley, Hoàng and Merkel introduced the concept of strong $e$-positivity and conjectured that a graph is strongly $e$-positive if and only if it is (claw, net)-free. In order to study strongly $e$-positive graphs, they further introduced the twinning operation on a graph $G$ with respect to a vertex $v$, which…
▽ More
Motivated by Stanley's $\mathbf{(3+1)}$-free conjecture on chromatic symmetric functions, Foley, Hoàng and Merkel introduced the concept of strong $e$-positivity and conjectured that a graph is strongly $e$-positive if and only if it is (claw, net)-free. In order to study strongly $e$-positive graphs, they further introduced the twinning operation on a graph $G$ with respect to a vertex $v$, which adds a vertex $v'$ to $G$ such that $v$ and $v'$ are adjacent and any other vertex is adjacent to both of them or neither of them. Foley, Hoàng and Merkel conjectured that if $G$ is $e$-positive, then so is the resulting twin graph $G_v$ for any vertex $v$. Based on the theory of chromatic symmetric functions in non-commuting variables developed by Gebhard and Sagan, we establish the $e$-positivity of a class of graphs called tadpole graphs. By considering the twinning operation on a subclass of these graphs with respect to certain vertices we disprove the latter conjecture of Foley, Hoàng and Merkel. We further show that if $G$ is $e$-positive, the twin graph $G_v$ and more generally the clan graphs $G^{(k)}_v$ ($k \ge 1$) may not even be $s$-positive, where $G^{(k)}_v$ is obtained from $G$ by applying $k$ twinning operations to $v$.
△ Less
Submitted 27 October, 2020;
originally announced October 2020.
-
Reinforcement Solver for H-infinity Filter with Bounded Noise
Authors:
Jie Li,
Shengbo Eben Li,
Kaiming Tang,
Yao Lv,
Wenhan Cao
Abstract:
H-infinity filter has been widely applied in engineering field, but copping with bounded noise is still an open problem and difficult to solve. This paper considers the H-infinity filtering problem for linear system with bounded process and measurement noise. The problem is first formulated as a zero-sum game where the dynamic of estimation error is non-affine with respect to filter gain and measu…
▽ More
H-infinity filter has been widely applied in engineering field, but copping with bounded noise is still an open problem and difficult to solve. This paper considers the H-infinity filtering problem for linear system with bounded process and measurement noise. The problem is first formulated as a zero-sum game where the dynamic of estimation error is non-affine with respect to filter gain and measurement noise. A nonquadratic Hamilton-Jacobi-Isaacs (HJI) equation is then derived by employing a nonquadratic cost to characterize bounded noise, which is extremely difficult to solve due to its non-affine and nonlinear properties. Next, a reinforcement learning algorithm based on gradient descent method which can handle nonlinearity is proposed to update the gain of reinforcement filter, where measurement noise is fixed to tackle non-affine property and increase the convexity of Hamiltonian. Two examples demonstrate the convergence and effectiveness of the proposed algorithm.
△ Less
Submitted 3 August, 2020;
originally announced August 2020.
-
Adaptive dynamic programming for nonaffine nonlinear optimal control problem with state constraints
Authors:
Jingliang Duan,
Zhengyu Liu,
Shengbo Eben Li,
Qi Sun,
Zhenzhong Jia,
Bo Cheng
Abstract:
This paper presents a constrained adaptive dynamic programming (CADP) algorithm to solve general nonlinear nonaffine optimal control problems with known dynamics. Unlike previous ADP algorithms, it can directly deal with problems with state constraints. Firstly, a constrained generalized policy iteration (CGPI) framework is developed to handle state constraints by transforming the traditional poli…
▽ More
This paper presents a constrained adaptive dynamic programming (CADP) algorithm to solve general nonlinear nonaffine optimal control problems with known dynamics. Unlike previous ADP algorithms, it can directly deal with problems with state constraints. Firstly, a constrained generalized policy iteration (CGPI) framework is developed to handle state constraints by transforming the traditional policy improvement process into a constrained policy optimization problem. Next, we propose an actor-critic variant of CGPI, called CADP, in which both policy and value functions are approximated by multi-layer neural networks to directly map the system states to control inputs and value function, respectively. CADP linearizes the constrained optimization problem locally into a quadratically constrained linear programming problem, and then obtains the optimal update of the policy network by solving its dual problem. A trust region constraint is added to prevent excessive policy update, thus ensuring linearization accuracy. We determine the feasibility of the policy optimization problem by calculating the minimum trust region boundary and update the policy using two recovery rules when infeasible. The vehicle control problem in the path-tracking task is used to demonstrate the effectiveness of this proposed method.
△ Less
Submitted 8 April, 2022; v1 submitted 26 November, 2019;
originally announced November 2019.
-
Robust concurrent topology optimization of structure and its composite material considering uncertainty with imprecise probability
Authors:
Y. Wu,
Eric Li,
Z. C. He,
X. Y. Lin,
H. X. Jiang
Abstract:
This paper studied a robust concurrent topology optimization (RCTO) approach to design the structure and its composite materials simultaneously. For the first time, the material uncertainty with imprecise probability is integrated into the multi-scale concurrent topology optimization (CTO) framework. To describe the imprecise probabilistic uncertainty efficiently, the type I hybrid interval random…
▽ More
This paper studied a robust concurrent topology optimization (RCTO) approach to design the structure and its composite materials simultaneously. For the first time, the material uncertainty with imprecise probability is integrated into the multi-scale concurrent topology optimization (CTO) framework. To describe the imprecise probabilistic uncertainty efficiently, the type I hybrid interval random model is adopted. An improved hybrid perturbation analysis (IHPA) method is formulated to estimate the expectation and stand variance of the objective function in the worst case. Combined with the bi-directional evolutionary structural optimization (BESO) framework, the robust designs of the structure and its composite material are carried out. Several 2D and 3D numerical examples are presented to illustrate the effectiveness of the proposed method. The results show that the proposed method has high efficiency and low precision loss. In addition, the proposed RCTO approach remains efficient in both of linear static and dynamic structures, which shows its extensive adaptability.
△ Less
Submitted 21 October, 2019;
originally announced October 2019.
-
Frustrated Random Walks: A Faster Algorithm to Evaluate Node Distances on Connected and Undirected Graphs
Authors:
Enzhi Li,
Zhengyi Le
Abstract:
Researchers have designed many algorithms to measure the distances between graph nodes, such as average hitting times of random walks, cosine distances from DeepWalk, personalized PageRank, etc. Successful although these algorithms are, still they are either underperforming or too time-consuming to be applicable to huge graphs that we encounter daily in this big data era. To address these issues,…
▽ More
Researchers have designed many algorithms to measure the distances between graph nodes, such as average hitting times of random walks, cosine distances from DeepWalk, personalized PageRank, etc. Successful although these algorithms are, still they are either underperforming or too time-consuming to be applicable to huge graphs that we encounter daily in this big data era. To address these issues, here we propose a faster algorithm based on an improved version of random walks that can beat DeepWalk results with more than ten times acceleration. The reason for this significant acceleration is that we can derive an analytical formula to calculate the expected hitting times of this random walk quickly. There is only one parameter (the power expansion order) in our algorithm, and the results are robust with respect to its changes. Therefore, we can directly find the optimal solution without fine-tuning of model parameters. Our method can be widely used for fraud detection, targeted ads, recommendation systems, topic-sensitive search, etc.
△ Less
Submitted 1 December, 2020; v1 submitted 20 August, 2019;
originally announced August 2019.
-
A Hoeffding's inequality for uniformly ergodic diffusion process
Authors:
Michael C. H. Choi,
Evelyn Li
Abstract:
In this note, we present a version of Hoeffding's inequality in a continuous-time setting, where the data stream comes from a uniformly ergodic diffusion process. Similar to the well-studied case of Hoeffding's inequality for discrete-time uniformly ergodic Markov chain, the proof relies on techniques ranging from martingale theory to classical Hoeffding's lemma as well as the notion of deviation…
▽ More
In this note, we present a version of Hoeffding's inequality in a continuous-time setting, where the data stream comes from a uniformly ergodic diffusion process. Similar to the well-studied case of Hoeffding's inequality for discrete-time uniformly ergodic Markov chain, the proof relies on techniques ranging from martingale theory to classical Hoeffding's lemma as well as the notion of deviation kernel of diffusion process. We present two examples to illustrate our results. In the first example we consider large deviation probability on the occupation time of the Jacobi diffusion, a popular process used in modelling of exchange rates in mathematical finance, while in the second example we look at the exponential functional of a finite interval analogue of the Ornstein-Uhlenbeck process introduced by Kessler and Sørensen (1999).
△ Less
Submitted 25 March, 2019;
originally announced March 2019.
-
Integral Equation Approach to Stationary Stochastic Counting Process with Independent Increments
Authors:
Enzhi Li
Abstract:
Stationary stochastic processes with independent increments, of which the Poisson process is a prominent example, are widely used to describe real world events. With the basic assumption that a counting process is stationary and has independent increments, here I derive two integral equations to capture the time evolution of any such process. In order to solve these two integral equations explicit…
▽ More
Stationary stochastic processes with independent increments, of which the Poisson process is a prominent example, are widely used to describe real world events. With the basic assumption that a counting process is stationary and has independent increments, here I derive two integral equations to capture the time evolution of any such process. In order to solve these two integral equations explicitly, I need to introduce one more restriction condition. For sake of simplicity, I have imposed the Poisson condition on the two equations and successfully reproduced the renown Poisson results. The methods proposed here may also be applicable for investigating other stationary processes with independent increments.
△ Less
Submitted 17 November, 2018;
originally announced November 2018.
-
Cooperative Control of Heterogeneous Connected Vehicles with Directed Acyclic Interactions
Authors:
Yang Zheng,
Yougang Bian,
Shen Li,
Shengbo Eben Li
Abstract:
Cooperation of multiple connected vehicles has the potential to benefit the road traffic greatly. In this paper, we consider analysis and synthesis problems of the cooperative control of a platoon of heterogeneous connected vehicles with directed acyclic interactions (characterized by directed acyclic graphs). In contrast to previous works that view heterogeneity as a type of uncertainty, this pap…
▽ More
Cooperation of multiple connected vehicles has the potential to benefit the road traffic greatly. In this paper, we consider analysis and synthesis problems of the cooperative control of a platoon of heterogeneous connected vehicles with directed acyclic interactions (characterized by directed acyclic graphs). In contrast to previous works that view heterogeneity as a type of uncertainty, this paper directly takes heterogeneity into account in the problem formulation, allowing us to develop a deeper understanding of the influence of heterogeneity on the collective behavior of a platoon of connected vehicles. Our major strategies include an application of the celebrated internal model principle and an exploitation of lower-triangular structures for platoons with directed acyclic interactions. The major findings include: 1) we explicitly highlight the tracking ability of heterogeneous platoons, showing that the followers can only track the leader's spacing and velocity; 2) we analytically derive a stability region of feedback gains for platoons with directed acyclic interactions; 3) and consequently we propose a synthesis method based on the solution to an algebraic Riccati equation that shares the dimension of single vehicle dynamics. Numerical experiments are carried out to validate the effectiveness of our results.
△ Less
Submitted 20 August, 2018; v1 submitted 11 May, 2018;
originally announced May 2018.
-
Platooning of Connected Vehicles with Undirected Topologies: Robustness Analysis and Distributed H-infinity Controller Synthesis
Authors:
Yang Zheng,
Shengbo Eben Li,
Keqiang Li,
Wei Ren
Abstract:
This paper considers the robustness analysis and distributed $\mathcal{H}_{\infty}$ (H-infinity) controller synthesis for a platoon of connected vehicles with undirected topologies. We first formulate a unified model to describe the collective behavior of homogeneous platoons with external disturbances using graph theory. By exploiting the spectral decomposition of a symmetric matrix, the collecti…
▽ More
This paper considers the robustness analysis and distributed $\mathcal{H}_{\infty}$ (H-infinity) controller synthesis for a platoon of connected vehicles with undirected topologies. We first formulate a unified model to describe the collective behavior of homogeneous platoons with external disturbances using graph theory. By exploiting the spectral decomposition of a symmetric matrix, the collective dynamics of a platoon is equivalently decomposed into a set of subsystems sharing the same size with one single vehicle. Then, we provide an explicit scaling trend of robustness measure $γ$-gain, and introduce a scalable multi-step procedure to synthesize a distributed $\mathcal{H}_{\infty}$ controller for large-scale platoons. It is shown that communication topology, especially the leader's information, exerts great influence on both robustness performance and controller synthesis. Further, an intuitive optimization problem is formulated to optimize an undirected topology for a platoon system, and the upper and lower bounds of the objective are explicitly analyzed, which hints us that coordination of multiple mini-platoons is one reasonable architecture to control large-scale platoons. Numerical simulations are conducted to illustrate our findings.
△ Less
Submitted 16 July, 2017; v1 submitted 4 November, 2016;
originally announced November 2016.
-
Distributed Model Predictive Control for Heterogeneous Vehicle Platoons under Unidirectional Topologies
Authors:
Yang Zheng,
Shengbo Eben Li,
Keqiang Li,
Francesco Borrelli,
J. Karl Hedrick
Abstract:
This paper presents a distributed model predictive control (DMPC) algorithm for heterogeneous vehicle platoons with unidirectional topologies and a priori unknown desired set point. The vehicles (or nodes) in a platoon are dynamically decoupled but constrained by spatial geometry. Each node is assigned a local open-loop optimal control problem only relying on the information of neighboring nodes,…
▽ More
This paper presents a distributed model predictive control (DMPC) algorithm for heterogeneous vehicle platoons with unidirectional topologies and a priori unknown desired set point. The vehicles (or nodes) in a platoon are dynamically decoupled but constrained by spatial geometry. Each node is assigned a local open-loop optimal control problem only relying on the information of neighboring nodes, in which the cost function is designed by penalizing on the errors between predicted and assumed trajectories. Together with this penalization, an equality based terminal constraint is proposed to ensure stability, which enforces the terminal states of each node in the predictive horizon equal to the average of its neighboring states. By using the sum of local cost functions as a Lyapunov candidate, it is proved that asymptotic stability of such a DMPC can be achieved through an explicit sufficient condition on the weights of the cost functions. Simulations with passenger cars demonstrate the effectiveness of proposed DMPC.
△ Less
Submitted 4 August, 2016; v1 submitted 10 March, 2016;
originally announced March 2016.
-
Full waveform inversion with extrapolated low frequency data
Authors:
Yunyue Elita Li,
Laurent Demanet
Abstract:
The availability of low frequency data is an important factor in the success of full waveform inversion (FWI) in the acoustic regime. The low frequencies help determine the kinematically relevant, low-wavenumber components of the velocity model, which are in turn needed to avoid convergence of FWI to spurious local minima. However, acquiring data below 2 or 3 Hz from the field is a challenging and…
▽ More
The availability of low frequency data is an important factor in the success of full waveform inversion (FWI) in the acoustic regime. The low frequencies help determine the kinematically relevant, low-wavenumber components of the velocity model, which are in turn needed to avoid convergence of FWI to spurious local minima. However, acquiring data below 2 or 3 Hz from the field is a challenging and expensive task. In this paper we explore the possibility of synthesizing the low frequencies computationally from high-frequency data, and use the resulting prediction of the missing data to seed the frequency sweep of FWI. As a signal processing problem, bandwidth extension is a very nonlinear and delicate operation. It requires a high-level interpretation of bandlimited seismic records into individual events, each of which is extrapolable to a lower (or higher) frequency band from the non-dispersive nature of the wave propagation model. We propose to use the phase tracking method for the event separation task. The fidelity of the resulting extrapolation method is typically higher in phase than in amplitude. To demonstrate the reliability of bandwidth extension in the context of FWI, we first use the low frequencies in the extrapolated band as data substitute, in order to create the low-wavenumber background velocity model, and then switch to recorded data in the available band for the rest of the iterations. The resulting method, EFWI for short, demonstrates surprising robustness to the inaccuracies in the extrapolated low frequency data. With two synthetic examples calibrated so that regular FWI needs to be initialized at 1 Hz to avoid local minima, we demonstrate that FWI based on an extrapolated [1, 5] Hz band, itself generated from data available in the [5, 15] Hz band, can produce reasonable estimations of the low wavenumber velocity models.
△ Less
Submitted 20 January, 2016;
originally announced January 2016.
-
Half-integral finite surgeries on knots in $S^3$
Authors:
Eileen Li,
Yi Ni
Abstract:
Suppose that a hyperbolic knot in $S^3$ admits a finite surgery, Boyer and Zhang proved that the surgery slope must be either integral or half-integral, and they conjectured that the latter case does not happen. Using the correction terms in Heegaard Floer homology, we prove that if a hyperbolic knot in $S^3$ admits a half-integral finite surgery, then the knot must have the same knot Floer homolo…
▽ More
Suppose that a hyperbolic knot in $S^3$ admits a finite surgery, Boyer and Zhang proved that the surgery slope must be either integral or half-integral, and they conjectured that the latter case does not happen. Using the correction terms in Heegaard Floer homology, we prove that if a hyperbolic knot in $S^3$ admits a half-integral finite surgery, then the knot must have the same knot Floer homology as one of eight non-hyperbolic knots which are known to admit such surgeries, and the resulting manifold must be one of ten spherical space forms. As knot Floer homology carries a lot of information about the knot, this gives a strong evidence to Boyer--Zhang's conjecture.
△ Less
Submitted 4 October, 2013;
originally announced October 2013.
