# Zero-Shot Object Searching
Using Large-scale Object Relationship Prior

Hongyi Chen1, Ruinian Xu1, Shuo Cheng2, Patricio A. Vela1, Danfei Xu 2 1H.
Chen, R. Xu and P.A. Vela are with the School of Electrical and Computer
Engineering, Georgia Institute of Technology, Atlanta, GA 30308, USA.
{hchen657<EMAIL_ADDRESS>Cheng and D. Xu the School of Interactive
Computing, Georgia Institute of Technology, Atlanta, GA 30308, USA.
{shuocheng<EMAIL_ADDRESS>
###### Abstract

Home-assistant robots have been a long-standing research topic, and one of the
biggest challenges is searching for required objects in housing environments.
Previous object-goal navigation requires the robot to search for a target
object category in an unexplored environment, which may not be suitable for
home-assistant robots that typically have some level of semantic knowledge of
the environment, such as the location of static furniture. In our approach, we
leverage this knowledge and the fact that a target object may be located close
to its related objects for efficient navigation. To achieve this, we train a
graph neural network using the Visual Genome dataset to learn the object co-
occurrence relationships and formulate the searching process as iteratively
predicting the possible areas where the target object may be located. This
approach is entirely zero-shot, meaning it doesn’t require new accurate object
correlation in the test environment. We empirically show that our method
outperforms prior correlational object search algorithms. As our ultimate goal
is to build fully autonomous assistant robots for everyday use, we further
integrate the task planner for parsing natural language and generating task-
completing plans with object navigation to execute human instructions. We
demonstrate the effectiveness of our proposed pipeline in both the AI2-THOR
simulator and a Stretch robot in a real-world environment.

##  I INTRODUCTION

Home-assistant robots that share the same indoor space with humans are
designed to assist them by interpreting human instructions and completing the
corresponding home activities. In related work, researchers have evaluated the
different aspects of home-assistant robots [1][2][3]. Our paper focuses on
developing an efficient object searching algorithm in the household
environment for assistant robots.

Object search is a crucial ability for home-assistant robots and has been
extensively studied [4]. Various approaches such as end-to-end reinforcement
or imitation learning are commonly used to search for objects in unexplored
environments [5][6][4]. However, for home-assistant robots that are accustomed
to their daily working environments, it is more practical to use partially
observable Markov decision process (POMDP)-based approaches to maintain and
update a measure of uncertainty over the location of the target object via its
belief state, instead of building an episodic map [7][8][9]. Existing POMDP-
based approaches typically make assumptions about object independence to
reason about belief states, which makes them scalable but less accurate in
their search for objects [9]. Alternatively, these approaches may rely on
accurate object correlation information, which may not always be available
[10]. In such cases, the success rate of the search process may decrease
significantly.

Figure 1: Illustration of the proposed framework for object searching and
human instruction following. The human query is parsed into action sequence.
Based on learned object co-occurrence relationships, GNN predicts possible
areas to search for missing knife and complete the generated plan.

This paper proposes a new approach for object search that does not rely on
accurate object correlation information. Instead, the approach leverages the
co-occurrence between object pairs to facilitate the search. Our approach
involves predicting related objects whose positions are already known to the
robot (e.g., furniture, fixtures) and searching areas with a high probability
of finding a particular object. For instance, a knife is likely to be placed
on a kitchen countertop. To model the object relationships, we construct a
graph neural network (GNN) where nodes represent objects and edges represent
the geometrical relationships between objects. We train our GNN model on the
Visual Genome dataset, which contains over 100,000 natural images with object
and relationship annotations. During the search, the trained GNN updates its
prior knowledge about object relationships based on newly detected objects in
the scene to make more accurate predictions. Our approach circumvents
scalability issues present in traditional methods by implicitly encoding
object relationships extracted from a large-scale real-world dataset in a
flexible GNN model.

Toward the goal of fully autonomous assistant robots for everyday use, we
further integrate our task planner with object navigation to execute human
instructions. We build upon a hybrid task planner [2] that can generate task-
completing action sequences based on human instructions. But the task planner
assumes all required objects are located within the current field of view
(FoV) of robot. Combining with the GNN-based object navigation, we enable the
task planner to generate plans for searching missing objects that are outside
of the current FoV. Our framework is illustrated in fig. 1. We assess the
effectiveness of our proposed pipeline through simulations and real-world
experiments. To benchmark the simulation results, we conduct object navigation
in four room types, namely kitchen, bedroom, living room and bathroom, and
four demanding tasks – cut, cook, clean, and pick-and-place – in AI2-THOR
[11], a realistic simulator of interactive household environments.
Furthermore, we showcase that our pipeline can deliver reliable performance
when applied to a real mobile manipulator Stretch RE2 robot [12].

##  II Related Works

Object Navigation In previous works, object navigation is defined as the task
of navigating to an object (specified by its category label) in an unexplored
environment [4]. One popular approach is to use end-to-end reinforcement or
imitation learning to build episodic memory and learn semantic priors
implicitly [5, 6]. However, these methods struggle at this task as they are
ineffective at exploration and long-term planning. To improve the efficiency
of exploration and searching, approaches like language guidance [13] and
semantic map construction [14] are proposed and used. Another parallel line of
works have studied using partially observable Markov decision process (POMDP)
to maintain and update a measure of uncertainty over the location of the
target object, via its belief state [7, 10, 9]. This formalization is useful
because object search over long horizons is naturally a sequential, partially
observed decision-making problem. But current POMDP-based approaches for
object search often assume object independence to maintain and reason about
belief states, which enables scalability but may compromise the accuracy of
the search [9]. Alternatively, these approaches may rely on accurate object
correlation information, which may not always be readily available. In such
cases, the success rate of the search process may significantly decrease [10].
In contrast, our approach does not require prior knowledge of object
correlation and addresses the scalability issue by implicitly encoding
relationships inside the GNN model. This is achieved by training the model
with a large-scale object relationship dataset. Therefore, our approach does
not suffer from performance decrease due to inaccurate object correlation
information.

Task Planning from Human Instruction Based on manually defined symbols, early
symbolic planners exploited the syntactic structure of language to understand
human instructions and statically generated a sequence of actions
[15][16][17]. However, this type of approach fails to interpret the diverse
human instructions nor captures semantic meaning in incomplete sentences.
Learning-based methods can automatically learn linguistic features via deep
neural networks, eliminating the need for engineered symbolic structures to
process natural language [18][19]. However, it remains challenging to plan a
sequence of admissible actions through end-to-end learning approaches. Recent
studies show that well-trained large language models (LLM) already contain
information necessary to work as task planner when prompted with a single
fixed example of a task description and its associated sequence of actions
[20][21][22]. However, due to the open-ended nature of the LLM, it is
difficult to guarantee the success of generated plan. To ensure a task-
completing plan, we leverage the strengths of symbolic and learning based
approaches which adopts neural networks for goal learning and symbolic
approaches for task planning.

##  III Approach

Figure 2: Illustration of the proposed human instruction following pipeline.
The query from human will be parsed into a set of action, subject and object.
To search for the missing knife, GNN predicts possible areas, such as bowl and
bread, based on object co-occurrence relationships. Once the knife is
retrieved, the robot moves back to apple and complete the action sequence
generated via symbolic planner.

In this section, we will first introduce our solution for object navigation,
followed by a description of the whole instruction following pipeline for
assistant robots (fig. 2). This pipeline includes task planning from human
instructions as well as the object navigation algorithm.

###  III-A Object Navigation using Relationship Priors

Figure 3: Illustration of correlation prediction. Given the current graph $G$,
GNN predicts the probabilities of edge existence between target object knife
and other known objects. KR means known relationship and UKR means unknown
relationship.

Problem Formulation The problem is for a robot to search for a object with a
specific category within an environment containing stationary and movable
objects. The robot has access to a discrete 2D grid map of the environment
that contains information about the positions of the $n$ stationary objects
(e.g., furniture and fixtures), denoted by $x_{1},\ldots,x_{n}$. However, the
positions of the target object, denoted by $x_{\text{target}}$, and the $m$
movable objects, denoted by $y_{1},\ldots,y_{m}$, are initially unknown to the
robot. The objective is to efficiently locate the target object with the
minimum number of steps.

Object Search as object relationship prediction. When searching for
$x_{\text{target}}$, we aim to exploit the knowledge of the environment, such
as the locations of stationary objects and detected moveable objects during
navigation, and leverage the co-occurrence between object pairs to facilitate
the search. Object searching is then formulated as iteratively predicting
related objects whose positions are known to the robot until we find out
$x_{\text{target}}$. To model, learn, and predict object relationships, we use
the Graph Neural Network (GNN) structure, which is a powerful tool for
processing graph data and modeling correlations [23]. We denote our graph by
$G=(V,E)$, where $V$ and $E$ denote the nodes and the edges between nodes,
respectively. Specifically, each node $v\in V$ denotes an object category, and
each edge $e\in E$ denotes a relationship between a pair of object categories.
The input to each node $v$ is a feature vector $x_{v}$, which is the embedding
of semantic object category. The goal is to learn to predict whether an edge
exists between any two nodes.

Learning object relationships from real-world data. Visual Genome dataset [24]
enables us to learn real-world object correlations. This dataset contains over
100,000 natural images with object and relationship annotations. We can count
the occurrence of spatial relationships between object pairs in the dataset,
such as a bowl sitting in a sink, and connect two nodes if the occurrence
frequency of any relationship is more than three. To compute node embeddings
$h_{v}$, we use the Graph Attention Networks (GAT) architecture [25]. GAT
allows us to implicitly specify weights to neighbor nodes. We compute the node
embeddings using $h_{v}=GAT(x_{v},G)$. After we get the node embeddings,
another prediction header would compute the probability of link existence,
$\hat{z}_{uv}=Predictor(h_{u},h_{v})$, see fig. 3.

Search-time object relationship update. During testing, the robot only has the
location of $n$ stationary objects $x_{1},\ldots,x_{n}$ at the start. The
graph $G$ contains the relationships between these $n$ objects. The GNN model
predicts the probability of link existence
$E(x_{\text{target}},x_{1})\ldots,E(x_{\text{target}},x_{n})$ between the
target object $x_{\text{target}}$ and each of the stationary objects
$x_{1},\ldots,x_{n}$. The model selects the object with the highest
probability and searches its surrounding area. During navigation, the moveable
objects in $y_{1},\ldots,y_{m}$ will be detected and their locations will be
estimated (assume rgbd image is available), thus new relationship would be
computed and added into the graph $G$. This process allows the GNN to update
its estimation of the object relationships for the environment and improve its
predictions for the related object of $x_{\text{target}}$. We repeat the above
process until the robot finds the target object $x_{\text{target}}$ or reaches
the step limits.

###  III-B Object Search to Follow Human Instruction

In this subsection, we present the complete pipeline for following human
instructions, which includes task planning and object navigation, as
illustrated in the fig. 2. A task-completing plan necessitates the successful
execution of human instructions. We build upon the hybrid task planner that
uses vision-and-language network to learn the goal symbol from the
instruction, and then sending it to a symbolic planner to generate a task-
completing plan [2]. However, this approach assumed that all required objects
were always within the current FoV of the robot.

Our approach removes the reliance on images for task planning and eliminates
the assumption that all required objects are within the FoV of the robot. To
provide more detail, our approach begins with a natural language sentence $L$
composed of $K$ tokens, and outputs a sequence of primitive actions (e.g.,
search object, grasp object, and cut object) that will reach the desired goal
state upon execution, see green box in fig. 2. In detail, the goal state is
parsed by a goal prediction network which predict the action $a$, subject $s$,
and object $o$. Then, the task planning problem is addressed by transferring
from an initial state to the desired goal state, using the Planning Domain
Definition Language (PDDL) [26], a commonly used symbolic planning language.
The PDDL planner produces a task-completing action sequence if the domain and
problem are well-defined and specified, which includes a list of pre-defined
objects and their corresponding predicates (e.g., ”dirty” or ”graspable”), as
well as primitive actions and their corresponding effects. If either the
required subject $s$ or object $o$ is missing, an additional searching step is
added to the plan to locate the missing object using the navigation algorithm
discussed above, shown in the red box in fig. 2. This allows our pipeline to
extend the capabilities of home-assistant robots by enabling them to search
for objects if they are missing, making robots more flexible and adaptable in
real-world scenarios.

##  IV Experimental Results

Our experiments aim to show that (1) Object co-occurrences relationship can be
captured using GNN model and used for efficient object navigation; (2) The
integration of object navigation with a task planner enables home assistant
robots to successfully complete everyday household tasks based on human
instructions. We demonstrate the above two key points through the experiments
in AI2-THOR simulator and the physical Stretch robot.

###  IV-A AI2-THOR Simulation Results

The AI2-THOR [11] simulator provides accurate modeling of 120 interactive
scenes, evenly split between kitchens, living rooms, bedrooms, and bathrooms.
It includes hundreds of unique objects that have visual state changes such as
open/close, on/off, and clean/dirty. The robot can take primitive move actions
from the set:
$\\{\texttt{MoveAhead},\texttt{RotateLeft},\texttt{RotateRight}\\}$. MoveAhead
moves the robot forward by 0.25m. RotateLeft, RotateRight rotate the robot in
place by 45∘. Moreover, robot can change the positions and states of objects
through action primitives:
$\\{\texttt{Pick},\texttt{Put},\texttt{Move},\texttt{Cook},\texttt{Slice},$
Toggle$\\}$.

Zero-shot Object Link Prediction: As described in sec. III-A, we train our GNN
model using the Visual Genome dataset. Here we evaluate the link prediction
performance of the trained GNN model using both the Visual Genome test split
and the AI2-Thor environment. We consider 94 unique object categories in
AI2-Thor to construct the ground truth object relationship graph. A pair of
objects are considered connected if they are in close proximity based on
Euclidean distance or have receptacle relationship. The receptacle
relationship indicates that one of the objects is a receptacle, and the other
object is either inside or on top of it. An example of this relationship would
be an apple located on a desk. The edge label is created using the following
rule:

$\displaystyle E(obj_{i},obj_{j})=$ $\displaystyle\begin{cases}1&\left\lVert
obj_{i}-obj_{j}\right\rVert<d_{\text{thre}}\\\ 1&$is receptacle
relation$$($obj_{i},obj_{j}$)$\\\ 0&$else$\\\ \end{cases}$ (1)

where $obj_{i}$ and $obj_{j}$ are the locations of an object pair, and
$d_{\text{thre}}$ is a predefined threshold (1.0m).

The link prediction performance is shown in tab. I. Our model achieved high
accuracy in the Visual Genome test split and is able to transfer its knowledge
to AI2-THOR environment and achieve a zero-shot prediction accuracy of $67\%$
(without the search-time update described in sec. III-A). We hypothesize that
this is because the AI2-THOR scenes closely resemble real-world environments,
and the Visual Genome dataset provides a vast amount of data to aid in
learning object relationships in such environments. Overall, these results
support our hypothesis that object co-occurrences can be effectively captured
with GNN models trained on real-world scene dataset.

TABLE I: Link Prediction Accuracy in Visual Genome dataset and AI2-THOR Scenes. | Visual Genome test split | AI2-THOR scenes
---|---|---
Link Pred. Accuracy | 86.66% | 67.36%

Object Navigation: We compared our approach to Zheng et al.’s methods [10],
COS-POMDP, Target-POMDP, and Greedy-NBV. All of these search approaches use
object correlation, either based on ground-truth or estimated relationship.
They maintain and update a probability measurement of the target object over
its belief state for searching. We ensure a fair comparison by allowing all
algorithms to take the same number of steps for searching and the same set of
target object classes in test scenes. We also use the same YOLOv5 object
detector [27] as the perception module for all methods. The robot’s success
condition is to detect the target object and be within 1.0m Euclidean distance
from it by the end of an episode. As shown in table II, our approach
outperforms these baselines in both searching success rate and efficiency. The
example process of object searching in AI2-THOR is shown in fig. 4.

It is important to note that the baseline models rely on accurate
correlational information. In particular, these models label object pairs as
”close” if their distance is smaller than 2.0m. When using estimated object
correlation instead of the ground truth information, the performance of COS-
POMDP (indicated by the “est” variant) declines significantly. This finding
highlights the importance of leveraging large-scale knowledge source when
object correlations are difficult to estimate during the search process. And
our approach provides the complement for these methods and makes it suitable
for a wide range of unseen environments without object correlations
information.

TABLE II: AI2-THOR Object Navigation Quantitative Performance. The task success rate (SR) and navigation efficiency which is the success weighted by path length (SPL) of our approach and a variety of prior algorithms on AI2-THOR. | Kitchen | Bathroom | Bedroom | Living room
---|---|---|---|---
Model | SPL | SR | SPL | SR | SPL | SR | SPL | SR
Greedy-NBV | 11.61% | 31.03% | 14.34% | 34.48% | 16.92% | 26.67% | 7.13% | 20.00%
Target-POMDP | 13.80% | 34.48% | 19.88% | 55.17% | 19.79% | 26.67% | 24.36% | 40.00%
COS-POMDP | 20.45% | 41.38% | 30.64% | 55.17% | 24.76% | 40.00% | 24.99% | 43.33%
COS-POMDP (est) | 8.39% | 20.69% | 17.20% | 41.38% | 16.78% | 30.00% | 14.07% | 26.67%
GNN-Nav | 23.56% | 46.67% | 56.62% | 86.67% | 28.91% | 53.33% | 35.01% | 59.25%

Figure 4: Example sequence of searching for book in a living room scene. Top:
first-person view with object detection. Bottom: grid map of the environment.
GNN first predicts bed as related but failed to find book, then it predicts
dresser table and successfully finds the book on it.

Human Instruction Following: Our ultimate goal is to enable a home-assistant
robot to follow and execute human instruction. To verify the effectiveness of
our human instruction following pipeline discussed in sec. III-B, we conducted
tests on four daily activities: cutting, cooking, cleaning, and pick-and-
place. To complete the tasks, we utilized the default action space defined in
AI2-THOR, which includes slice, toggle, and clean. Each task involves the
robot receiving explicit human instruction 111Explicit human instruction
contains the subject and object inside which would make the training easier..
Target objects that are required to complete the task are initially not in the
FoV of robot. While the location of the subject is assumed to be known to the
robot. The list of target and subject classes and the task descriptions are
provided below.

  * •

Pick-and-place. _Targets_ are apple, bread, fork, lettuce, potato, tomato;
_Subjects_ are plate, bowl, sink; _Task_ is pick the _target_ and place it on
_subject_.

  * •

Cook. _Targets_ are bread, egg, lettuce, potato, tomato; _subjects_ are
microwave, toaster, stoveburner; _Task_ is cook the _target_ with _subject_.

  * •

Clean. _Targets_ are mug, spatula, cup, butterknife, pan, bowl, plate, pot;
_subject_ is sink; _Task_ is clean the _target_ inside the _subject_.

  * •

Cut. _Targets_ are bread, lettuce, potato, tomato; _subject_ is knife; _Task_
is cut the _target_ with _subject_.

We carry out evaluation in 30 distinct kitchen environments, and our criterion
for successful completion of a human instruction task involved several
factors. Specifically, the robot must correctly parse the instructions and
plan the task-completing action sequence (task planning), search for the
target object (object navigation), and accurately identify the relevant
subjects for performing the necessary actions (perception and manipulation).

In detail, we use the Symbolic Goal Learning
Dataset222https://smartech.gatech.edu/handle/1853/66305, and select 8163
explicit human instructions to train and test the language model. We adopt the
Multi Modal Framework (MMF) [28] and only train the LSTM language encoder with
human instructions and corresponding ground-truth goal states. Our goal
prediction network achieves $100\%$ prediction accuracy in 1024 unseen
explicit human instructions, and the symbolic PDDL planner can create an
optimal task plan once the goal state is correctly identified. For navigation
and execution, the success rate is summarized in table III. There are two
failure modes in our tests. The first mode is when the object navigation
algorithm is unable to locate the target object within the step limit. The
second failure mode arises when the robot is unable to find the required
subject, such as a knife, due to either a perception error or additional
actions being required, such as opening a drawer to retrieve the subject.

TABLE III: AI2-THOR Human Instruction Following Quantitative Performance. Nav means the success rate of navigation part, Exe means the success rate of task execution. Task | Navigation (Nav) | Execution (Exe)
---|---|---
Cook | 47.5% | 42.5%
Clean | 62.5% | 62.5%
Cut | 55.0% | 20.0%
Pick-and-Place | 47.5% | 45.0%

###  IV-B Real Robots Results

In order to further demonstrate the effectiveness of our object navigation
algorithm and human instruction following pipeline in real-world, we conduct
experiments on a Stretch RE2 robot, which is specifically designed for
navigation and manipulation in human environments. To create a realistic
household scene, we place moveable objects in semantically related areas, as
shown in fig. 5. We also provide the robot with the locations of stationary
objects, including the table, desk, counter, sink, sofa, and microwave.
Moreover, to prevent the perception module from detecting target objects that
are far away and sidestepping the search process, we create obstructions such
that the robot can only detect the object when being physically close to the
object. We adopt the Detic open-vocabulary [29] object detector as the
perception module and use the built-in depth camera to perform 3D pose
estimation for the subsequent navigation and manipulation decisions.

Figure 5: Real-world setup. Left: Robot. Right: Testing Scene.

(a) Predict related object

(b) Search sink

(c) Sink detection

(d) Search table

(e) Table detection

Figure 6: Real world object navigation test (search for bottle).

(a) Task planning

(b) Search sink

(c) Search counter

(d) Grasp box

(e) Place box

Figure 7: Real world human instruction following (pick&place test).

(a) Task planning

(b) Search table

(c) Grasp mug

(d) Place mug

(e) Toggle faucet

Figure 8: Real world human instruction following (clean test).

Object Navigation: The criterion of a successful object search requires the
robot to search at most two target areas (relative to a selected stationary
object) to find the target object. The targets objects include
$\\{\texttt{bottle},\texttt{knife},\texttt{plate},\texttt{pot},\texttt{toaster},\texttt{mug},\texttt{sponge},\\\
\texttt{bowl},\texttt{book},\texttt{banana}\\}$. We conduct 10 evaluation
trials, with a success rate of 6 out of 10. See fig. 6 for a successful search
example. The failed trials including searching for
$\\{\texttt{book},\texttt{banana},\texttt{bowl},\texttt{knife}\\}$. The
primary cause for failure is the bias of the GNN model inherited from the
Visual Genome training data. Specifically, the model often predicts sink or
counter as related objects, as the co-occurrence between sink or counter and
other target objects are common in the dataset. Although GNN detects objects
and updates information during the search, it may still converge to incorrect
predictions in some cases. For instance, when searching for banana, the model
initially predicts sink, followed by counter and desk and misses the correct
prediction table.

Human Instruction Following: Due to mechanical limitation of the gripper, we
limit our task to the ones that only involve transporting objects and simple
kinematic motion.

  * •

Pick-and-place. _Targets_ are mug, bottle, orange, box; Based on human
instruction, the robot should correctly plan and execute a sequence of actions
including searching for and picking up the _target_ and placing it on the
counter or desk.

  * •

Clean. _Target_ is mug; Based on human instruction, the robot should correctly
plan and execute a sequence of actions including searching for and picking up
the _mug_ , placing it inside sink, and toggling to turn on the faucet.

For each pick-and-place task, we place one target object on the table. The
evaluation success rate is 3 out of 4 objects. See fig. 7 for the successful
cases. The failed trial is caused by the perception module failing to estimate
the correct 3D position for the _orange_ , which results in a failed grasp. In
the clean task, we place the mug on the table and change its location slightly
each time, repeating the experiment four times. The success rate is 3 out of 4
times, see fig. 8 for visualization. The robot is able to locate the mug
reliably. The failure case is again caused by a failed grasp (the mug slipped
out of the gripper).

##  V Conclusion

This work proposes a zero-shot object navigation approach, which leverages
object co-occurrence to achieve efficient search. Unlike prior correlation-
based methods, we learn the object correlation from a large-scale Visual
Genome dataset and don’t require accurate correlation information in new
environments. We apply this approach to object navigation and integrate it
into human instruction following tasks, and demonstrate the effectiveness in
both AI2-THOR simulator and real-world household settings. The current
limitations of our system lie in the object manipulation and grasping
algorithms. For instance, the system fails to open containers for object
detection and struggles to hold onto objects securely. Exploring more advanced
planners that can take additional manipulation actions to search object and
learning to predict viable grasp candidates [30] would be interesting for
future works.

## References

  * [1] Kimitoshi Yamazaki, Ryohei Ueda, Shunichi Nozawa, Mitsuharu Kojima, Kei Okada, Kiyoshi Matsumoto, Masaru Ishikawa, Isao Shimoyama, and Masayuki Inaba.  Home-assistant robot for an aging society.  Proceedings of the IEEE, 100(8):2429–2441, 2012.
  * [2] Ruinian Xu, Hongyi Chen, Yunzhi Lin, and Patricio A. Vela.  Sgl: Symbolic goal learning in a hybrid, modular framework for human instruction following.  IEEE Robotics and Automation Letters, 7(4):10375–10382, 2022.
  * [3] Bingjie Tang, Matthew Corsaro, George Konidaris, Stefanos Nikolaidis, and Stefanie Tellex.  Learning collaborative pushing and grasping policies in dense clutter.  In 2021 IEEE International Conference on Robotics and Automation (ICRA), pages 6177–6184. IEEE, 2021.
  * [4] Dhruv Batra, Aaron Gokaslan, Aniruddha Kembhavi, Oleksandr Maksymets, Roozbeh Mottaghi, Manolis Savva, Alexander Toshev, and Erik Wijmans.  Objectnav revisited: On evaluation of embodied agents navigating to objects.  arXiv preprint arXiv:2006.13171, 2020.
  * [5] Arsalan Mousavian, Alexander Toshev, Marek Fišer, Jana Košecká, Ayzaan Wahid, and James Davidson.  Visual representations for semantic target driven navigation.  In 2019 International Conference on Robotics and Automation (ICRA), pages 8846–8852. IEEE, 2019.
  * [6] Saurabh Gupta, James Davidson, Sergey Levine, Rahul Sukthankar, and Jitendra Malik.  Cognitive mapping and planning for visual navigation.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2616–2625, 2017.
  * [7] Yuchen Xiao, Sammie Katt, Andreas ten Pas, Shengjian Chen, and Christopher Amato.  Online planning for target object search in clutter under partial observability.  In 2019 International Conference on Robotics and Automation (ICRA), pages 8241–8247, 2019.
  * [8] Jue Kun Li, David Hsu, and Wee Sun Lee.  Act to see and see to act: Pomdp planning for objects search in clutter.  In 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 5701–5707. IEEE, 2016.
  * [9] Luc Holzherr, Julian Förster, Michel Breyer, Juan Nieto, Roland Siegwart, and Jen Jen Chung.  Efficient multi-scale pomdps for robotic object search and delivery.  In 2021 IEEE International Conference on Robotics and Automation (ICRA), pages 6585–6591. IEEE, 2021.
  * [10] Kaiyu Zheng, Rohan Chitnis, Yoonchang Sung, George Konidaris, and Stefanie Tellex.  Towards optimal correlational object search.  In 2022 International Conference on Robotics and Automation (ICRA), pages 7313–7319. IEEE, 2022.
  * [11] Eric Kolve, Roozbeh Mottaghi, Winson Han, Eli VanderBilt, Luca Weihs, Alvaro Herrasti, Daniel Gordon, Yuke Zhu, Abhinav Gupta, and Ali Farhadi.  Ai2-thor: An interactive 3d environment for visual ai.  arXiv preprint arXiv:1712.05474, 2017.
  * [12] Stretch re2 robot, https://hello-robot.com/stretch-2.
  * [13] Jacob Krantz, Erik Wijmans, Arjun Majumdar, Dhruv Batra, and Stefan Lee.  Beyond the nav-graph: Vision-and-language navigation in continuous environments.  In Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part XXVIII 16, pages 104–120. Springer, 2020.
  * [14] Devendra Singh Chaplot, Dhiraj Prakashchand Gandhi, Abhinav Gupta, and Russ R Salakhutdinov.  Object goal navigation using goal-oriented semantic exploration.  Advances in Neural Information Processing Systems, 33:4247–4258, 2020.
  * [15] Stefanie Tellex, Thomas Kollar, Steven Dickerson, Matthew R. Walter, Ashis Gopal Banerjee, Seth Teller, and Nicholas Roy.  Understanding natural language commands for robotic navigation and mobile manipulation.  In Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, AAAI’11, page 1507–1514. AAAI Press, 2011.
  * [16] Cameron Finucane, Gangyuan Jing, and Hadas Kress-Gazit.  Ltlmop: Experimenting with language, temporal logic and robot control.  In 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 1988–1993, 2010.
  * [17] Kai-yuh Hsiao, Stefanie Tellex, Soroush Vosoughi, Rony Kubat, and Deb Roy.  Object schemas for grounding language in a responsive robot.  Connect. Sci, 20(4):253–276, 2008.
  * [18] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805, 2018.
  * [19] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  Advances in neural information processing systems, 33:1877–1901, 2020.
  * [20] Wenlong Huang, Pieter Abbeel, Deepak Pathak, and Igor Mordatch.  Language models as zero-shot planners: Extracting actionable knowledge for embodied agents.  In International Conference on Machine Learning, pages 9118–9147. PMLR, 2022.
  * [21] Michael Ahn, Anthony Brohan, Noah Brown, Yevgen Chebotar, Omar Cortes, Byron David, Chelsea Finn, Keerthana Gopalakrishnan, Karol Hausman, Alex Herzog, et al.  Do as i can, not as i say: Grounding language in robotic affordances.  arXiv preprint arXiv:2204.01691, 2022.
  * [22] Wenlong Huang, Fei Xia, Ted Xiao, Harris Chan, Jacky Liang, Pete Florence, Andy Zeng, Jonathan Tompson, Igor Mordatch, Yevgen Chebotar, et al.  Inner monologue: Embodied reasoning through planning with language models.  arXiv preprint arXiv:2207.05608, 2022.
  * [23] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  arXiv preprint arXiv:1810.00826, 2018.
  * [24] Ranjay Krishna, Yuke Zhu, Oliver Groth, Justin Johnson, Kenji Hata, Joshua Kravitz, Stephanie Chen, Yannis Kalantidis, Li-Jia Li, David A Shamma, Michael Bernstein, and Li Fei-Fei.  Visual genome: Connecting language and vision using crowdsourced dense image annotations.  2016\.
  * [25] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  stat, 1050:20, 2017.
  * [26] Constructions Aeronautiques, Adele Howe, Craig Knoblock, ISI Drew McDermott, Ashwin Ram, Manuela Veloso, Daniel Weld, David Wilkins SRI, Anthony Barrett, Dave Christianson, et al.  Pddl— the planning domain definition language.  Technical Report, Tech. Rep., 1998.
  * [27] Glenn Jocher, Ayush Chaurasia, Alex Stoken, Jirka Borovec, NanoCode012, Yonghye Kwon, Kalen Michael, TaoXie, Jiacong Fang, imyhxy, Lorna, Zeng Yifu, Colin Wong, Abhiram V, Diego Montes, Zhiqiang Wang, Cristi Fati, Jebastin Nadar, Laughing, UnglvKitDe, Victor Sonck, tkianai, yxNONG, Piotr Skalski, Adam Hogan, Dhruv Nair, Max Strobel, and Mrinal Jain.  ultralytics/yolov5: v7.0 - YOLOv5 SOTA Realtime Instance Segmentation, November 2022.
  * [28] Amanpreet Singh, Vedanuj Goswami, Vivek Natarajan, Yu Jiang, Xinlei Chen, Meet Shah, Marcus Rohrbach, Dhruv Batra, and Devi Parikh.  Mmf: A multimodal framework for vision and language research, 2020.
  * [29] Xingyi Zhou, Rohit Girdhar, Armand Joulin, Philipp Krähenbühl, and Ishan Misra.  Detecting twenty-thousand classes using image-level supervision.  CoRR, abs/2201.02605, 2022.
  * [30] Fu-Jen Chu, Ruinian Xu, and Patricio A Vela.  Real-world multiobject, multigrasp detection.  IEEE Robotics and Automation Letters, 3(4):3355–3362, 2018.


110

# Best polynomial approximation for non-autonomous linear ODEs in the
$\star$-product framework††thanks: This work was supported by Charles
University Research Centre program No. PRIMUS/21/SCI/009 and UNCE/24/SCI/005,
and by the Magica project ANR-20-CE29-0007 funded by the French National
Research Agency.

Stefano Pozza Faculty of Mathematics and Physics, Charles University,
Sokolovská 83, 186 75 Praha 8, Czech Republic,(pozza@karlin.mff.cun.cz).

###### Abstract

We present the first formulation of the optimal polynomial approximation of
the solution of linear non-autonomous systems of ODEs in the framework of the
so-called $\star$-product. This product is the basis of new approaches for the
solution of such ODEs, both in the analytical and the numerical sense. The
paper shows how to formally state the problem and derives upper bounds for its
error.

###### keywords:

Non-autonomous linear ODEs, polynomial approximation, error analysis,

46F10, 37C60, 65L05

##  1 Introduction

Recently, a new approach has been introduced for the solution of systems of
linear non-autonomous ordinary differential equations based on the so-called
$\star$-product [6, 7, 12, 16]. Such an approach has proved to be valuable and
effective analytically, by producing new explicit expressions for the solution
of certain problems [5, 6, 8], and numerically, being the basis of new
efficient algorithms in quantum chemistry problems [3, 13, 14, 15].

Given a Hermitian matrix-valued function $\tilde{A}(t)\in\mathbb{C}^{N\times
N}$ analytic on the bounded interval $I$, and the nonzero vector
$\tilde{v}\in\mathbb{C}^{N\times N}$ we consider the initial value problem

$\frac{\partial}{\partial
t}\tilde{u}(t)=\tilde{A}(t)\tilde{u}(t),\quad\tilde{u}(a)=\tilde{v},\quad t\in
I=[a,b].$ (1)

The $\star$-product is defined over a Fréchet-Lie group on distributions [16].
In such a group, the initial value problem becomes a _$\star$ -linear system_.
Thanks to this “linearization” of the ODE, new techniques can be applied to
solve the problem. Here, we focus on the polynomial approximation approach,
which can be used both in numerical approaches and in the theoretical
framework. In particular, in the latter one, a symbolic algorithm named
$\star$-Lanczos [8] is able to produce a Krylov-like subspace approximation,
that is, a polynomial approximation in the $\star$-product sense.

In this work, we will show that it is possible to formulate the problem of a
best polynomial approximation for $\tilde{u}$ in the $\star$-framework.
Moreover, we will show that its error can be bounded by the best uniform norm
polynomial approximation error for the exponential [11]. This result is
crucial to understand the numerical behavior of polynomial-based numerical
methods when solving linear systems derived by using the $\star$-approach.
Indeed, the polynomial approximation is central in the analysis of standard
Krylov subspace methods (e.g., [10]), and its extension to the
$\star$-framework will also allow extending this kind of numerical analysis.

In Section 2, we introduce the basics of the $\star$-product, and we state the
main result. Section 3 shows how to extend matrix analysis results to the
$\star$-framework. The prove of the main result is given in Section 4 and
Section 5 draw some conclusions.

Table 1: List of the main $\star$-definitions and related objects, $f,g,x$ are generally from $\mathcal{A}(I)$. Name | Symbol | Definition | Comments / Properties
---|---|---|---
$\star$-product | $f\star g$ | $\int_{I}f(t,\tau)g(\tau,s)\text{d}\tau$ |
$\star$-identity | $\delta$ | $f\star\delta=\delta\star f=f$ | $\delta(t-s)$: Dirac delta
$\star$-inverse | $f^{-\star}$ | $f\star f^{-\star}=f^{-\star}\star f=\delta$ | Existence [7, 16]
Heaviside function | $\Theta$ | $\Theta(t-s)=1,t\geq s$, $0$ otherwise |
Analytic $\Theta$-set | $\mathcal{A}_{\Theta}(I)$ | {$\tilde{f}(t,s)\Theta(t-s)$: $\tilde{f}$ analytic on $I^{2}$} | $\star$-product-closed set
Dirac 1st derivative | $\delta^{\prime}$ | $\delta^{\prime}(t-s)$ | $\delta^{\prime}\star\Theta=\Theta\star\delta^{\prime}=\delta$
Dirac derivatives | $\delta^{(j)}$ | $\delta^{(j)}(t-s)$ | $\delta^{(j)}\star\delta^{(i)}=\delta^{(i+j)}$
$\star$-powers | $f^{\star j}$ | $f\star f\star\cdots\star f$, $j$ times | $f^{\star 0}:=\delta$, by convention
$\star$-resolvent | $R^{\star}(x)$ | $\sum_{j=0}^{\infty}x^{\star j},\,x\in\mathcal{A}_{\Theta}(I)$ | $R^{\star}(x)=(\delta-x)^{-\star}$
$\star$-polynomial | $p^{\star}(x)$ | $\sum_{j=0}^{n}\alpha_{j}x^{\star j}$, $\alpha_{j}\in\mathbb{C}$ | if $\alpha_{n}\neq 0$, $n$ is the degree
Table 2: Useful properties of $\star$-product actions on $\mathcal{A}_{\Theta}(I)$ elements. Description | Definition | Property
---|---|---
“Integration” in $t$ | $\tilde{F}\Theta$, $\tilde{F}(t,s)$ primitive of $\tilde{f}$ in $t$, $F(s,s)=0$ | $\tilde{F}\Theta=\Theta\star\tilde{f}\Theta$
“Integration” in $s$ | $\tilde{F}\Theta$, $\tilde{F}(t,s)$ primitive of $\tilde{f}$ in $s$, $\tilde{F}(t,t)=0$ | $\tilde{F}\Theta=\tilde{f}\Theta\star\Theta$
“Differentiation” in $t$ | $\tilde{f}^{(1,0)}\Theta$, $\tilde{f}^{(1,0)}(t,s)$ derivative of $\tilde{f}$ in $t$ | $\delta^{\prime}\star\tilde{f}\Theta=\tilde{f}^{(1,0)}\Theta+\tilde{f}\delta$
“Differentiation” in $s$ | $\tilde{f}^{(0,1)}\Theta$, $\tilde{f}^{(0,1)}(t,s)$ derivative of $\tilde{f}$ in $s$ | $\tilde{f}\Theta\star\delta^{\prime}=-\tilde{f}^{(0,1)}\Theta+\tilde{f}\delta$

##  2 Basics and main result

In order to state the main result, we first summarize the $\star$-product
basics. Refer to [16] for the general definition of this product and the
related properties. Given a bounded interval $I$, let us denote with
$\mathcal{A}(I)$ the set of the bivariate distributions of the kind

$f(t,s)=\tilde{f}_{-1}(t,s)\Theta(t-s)+\tilde{f}_{0}(t)\delta(t-s)+\tilde{f}_{1}(t)\delta^{\prime}(t-s)+\dots+\tilde{f}_{k}(t)\delta^{(k)}(t-s),$

where $\tilde{f}_{-1},\dots,\tilde{f}_{k}$ are analytic functions over $I$
both in $t$ and $s$, $\Theta$ is the Heaviside function ($\Theta(t-s)=1$ for
$t\geq s$, and $0$ otherwise), and $\delta,\delta^{\prime},\dots,\delta^{(k)}$
are the Dirac delta and its derivatives. Then, the $\star$-product of
$f_{1},f_{2}\in\mathcal{A}(I)$ is

$(f_{1}\star
f_{2})(t,s):=\int_{I}f_{1}(t,\tau)f_{2}(\tau,s)\,\text{d}\tau\in\mathcal{A}(I).$

Some of the important properties, definitions, and facts about the
$\star$-product can be found in Tables 1 and 2. Specifically, it is easy to
see that $\delta(t-s)$ is the $\star$-product identity. Moreover, since
$\mathcal{A}(I)$ is closed under $\star$-product, we can define the
$\star$-powers of $f\in\mathcal{A}(I)$, denoted as $f^{\star n}$ with the
convention $f^{\star 0}=\delta$. Therefore, for $x\in\mathcal{A}(I)$, we can
define the _$\star$ -polynomial of degree $n$_ as

$p^{\star}(t,s):=\alpha_{0}\delta(t-s)+\alpha_{1}x(t,s)+\alpha_{2}x(t,s)^{\star
2}+\dots+\alpha_{n}x(t,s)^{\star n},$ (2)

with constants $\alpha_{0},\dots,\alpha_{n}\in\mathbb{C}$, $\alpha_{n}\neq 0$.
We call $\mathcal{P}^{\star}_{n}$ the set of all such $\star$-polynomials.

We define the subset $\mathcal{A}_{\Theta}(I)\subset\mathcal{A}(I)$ of the
distributions of the form $f(t,s)=\tilde{f}(t,s)\Theta(t-s)$, with $\tilde{f}$
a function analytic over $I^{2}$. The _$\star$ -resolvent_ is defined as

$R^{\star}(x):=\sum_{j=0}^{\infty}x^{\star j}.$

Note that $R^{\star}(x)$ is well-defined (i.e., convergent) for every
$x\in\mathcal{A}_{\Theta}$ [6].

When $A,B$ are matrices with compatible sizes composed of elements from
$\mathcal{A}(I)$, the $\star$-product straightforwardly extends to a matrix-
matrix (or matrix-vector) $\star$-product. In the following, we denote with
$\mathcal{A}^{N\times M}(I)$ and $\mathcal{A}_{\Theta}^{N\times M}(I)$ the
spaces of $N\times M$ matrices with elements from those sets. We denote with
$I_{\star}=\tilde{I}\delta(t-s)$ the identity matrix in $\mathcal{A}^{N\times
N}(I)$, with $\tilde{I}$ the standard $N\times N$ identity matrix.

Setting $I=[a,b]$, the solution $\tilde{u}(t)$ of the ODE (1) can be expressed
by

$\tilde{u}(t)=U(t,a)\tilde{v},\;t\in I,\quad U(t,s)=\Theta(t-s)\star
R^{\star}\left(\tilde{A}(t)\Theta(t-s)\right);$ (3)

as proven in [6]. From now on, we will skip the distribution arguments $t,s$
whenever it is useful and clear from the context. Since
$R^{\star}(\tilde{A}\Theta)$ is the $\star$-inverse of
$I_{\star}-\tilde{A}\Theta$ (e.g., [12]), then solving (3) means solving the
system of $\star$-linear equations

$(I_{\star}-\tilde{A}\Theta)\star
x=\tilde{v}\delta,\quad\tilde{u}(t)=(\Theta\star x)(t,a)\quad t\in I.$

Note that this is not just a theoretical result since there is an efficient
way to transform the $\star$-linear system into a usual linear system that can
be solved numerically [13, 14, 15].

It is reasonable to consider a $\star$-polynomial approximation
$p^{\star}(\tilde{A}\Theta)\tilde{v}\approx
R^{\star}(\tilde{A}\Theta)\tilde{v}$. Specifically, we aim at finding the best
$\star$-polynomial $p^{\star}(t,s)$ of degree $n$ that approximates the
$\star$-resolvent $R^{\star}(A)\tilde{v}$ in the $L_{2}$ norm sense, i.e., the
polynomial $q^{\star}$ that minimizes the error

$\|\tilde{u}(t)-(\Theta\star
q^{\star}(A)\tilde{v})(t,a)\|_{L_{2}}:=\left(\int_{a}^{b}|\tilde{u}(\tau)-(\Theta\star
q^{\star}(A))(\tau,a)\tilde{v}|^{2}\right)^{\frac{1}{2}},\;t\in I.$

Note that $\Theta\star q^{\star}(A)\in\mathcal{A}_{\Theta}^{N\times N}$, while
$q^{\star}(A)\in\mathcal{A}^{N\times N}$.

######  Theorem 2.1 (Main result).

Consider the initial value problem (1) and let
$\tilde{\lambda}_{1}(t),\dots,\tilde{\lambda}_{N}(t)$ be the eigenvalues of
$\tilde{A}(t)\in\mathbb{C}^{N\times N}$. We define the interval

$J:=\left[\min_{t\in I,i=1,\dots,N}\tilde{\lambda}_{i}(t),\max_{t\in
I,i=1,\dots,N}\tilde{\lambda}_{i}(t)\right]\times\emph{length}(I),$

and denote with $E_{n}(J)$ the minimal uniform error of the polynomial
approximation of the exponential over $J$, i.e.,

$E_{n}(J):=\min_{p\in\mathcal{P}_{n}}\max_{t\in J}|\exp(t)-p(t)|.$

Define $A(t,s)=\tilde{A}(t)\Theta(t-s)$. Then the error of the $L_{2}$-best
$\star$-polynomial approximant $q^{\star}$ can be bounded by

$\|\tilde{u}(t)-(\Theta\star q^{\star}(A)\tilde{v})(t,a)\|_{L_{2}}\leq
E_{n}(J)\leq M\rho^{n+1},\;t\in I$

for some constant $M>0$ and $0<\rho<1$ depending on $J$.

The proof of this Theorem will be the outcome of the rest of the paper. The
first step towards the proof is to derive an explicit form for the
$\star$-monomials $f^{\star n}$ in the case in which
$f(t,s)=\tilde{f}(t)\Theta(t-s)\in\mathcal{A}_{\Theta}(I)$.

######  Lemma 2.2.

Consider the function $f(t,s)=\tilde{f}(t)\Theta(t-s)\in\mathcal{A}_{\Theta}$
and let $\tilde{F}(t)$ be a primitive of $\tilde{f}(t)$. Then, for
$n=1,2,\dots$,

$\displaystyle f(t,s)^{\star n}$
$\displaystyle=\frac{\tilde{f}(t)}{(n-1)!}\left(\tilde{F}(t)-\tilde{F}(s)\right)^{n-1}\Theta(t-s),$
(4) $\displaystyle\Theta(t-s)\star f(t,s)^{\star n}$
$\displaystyle=\frac{1}{n!}\left(\tilde{F}(t)-\tilde{F}(s)\right)^{n}\Theta(t-s).$
(5)

Moreover, $\Theta(t-s)\star f(t,s)^{\star 0}=\Theta(t-s)$ since $f(t,s)^{\star
0}=\delta(t-s)$ by convention.

######  Proof 2.3.

For $n=2$, the expression (4) is trivially obtained by

$f(t,s)^{\star
2}=\tilde{f}(t)\Theta(t-s)\int_{s}^{t}\tilde{f}(\tau)\,\textrm{d}\tau=\tilde{f}(t)\left(\tilde{F}(t)-\tilde{F}(s)\right)\Theta(t-s).$

Now, by induction, assuming (4) we get

$\displaystyle f(t,s)^{\star
n+1}=\frac{\tilde{f}(t)}{(n-1)!}\Theta(t-s)\int_{s}^{t}\tilde{f}(\tau)\left(\tilde{F}(\tau)-\tilde{F}(s)\right)^{n-1}\textrm{d}\tau.$
(6)

Integrating by part gives

$\displaystyle\int_{s}^{t}\tilde{f}(\tau)\left(\tilde{F}(\tau)-\tilde{F}(s)\right)^{n-1}\textrm{d}\tau$
$\displaystyle=(\tilde{F}(t)-\tilde{F}(s))^{n}-$
$\displaystyle(n-1)\int_{s}^{t}\tilde{f}(\tau)\left(\tilde{F}(\tau)-\tilde{F}(s)\right)^{n-1}\,\textrm{d}\tau.$

Therefore,

$\displaystyle
n\int_{s}^{t}\tilde{f}(\tau)\left(\tilde{F}(\tau)-\tilde{F}(s)\right)^{n-1}\textrm{d}\tau$
$\displaystyle=(\tilde{F}(t)-\tilde{F}(s))^{n}.$

Together with (6), this proves (4). Eq. (5) comes from observing that

$\displaystyle\Theta(t-s)\star f(t,s)^{\star n}$
$\displaystyle=\Theta(t-s)\star\frac{\tilde{f}(t)}{(n-1)!}\left(\tilde{F}(t)-\tilde{F}(s)\right)^{n-1}\Theta(t-s)$
$\displaystyle=\frac{\Theta(t-s)}{(n-1)!}\int_{s}^{t}\tilde{f}(\tau)\left(\tilde{F}(\tau)-\tilde{F}(s)\right)^{n-1}\textrm{d}\tau$
$\displaystyle=\frac{1}{n!}(\tilde{F}(t)-\tilde{F}(s))^{n}\Theta(t-s),$

which concludes the proof.

An immediate consequence of Lemma 2.2 is that

$\exp\left(\tilde{F}(t)-\tilde{F}(s)\right)=\Theta(t-s)\star
R^{\star}(f)(t,s),$

a well-known result; see, e.g., [6].

##  3 Matrix spectral decomposition and the $\star$-product

Consider a time-dependent $N\times N$ Hermitian matrix-valued function
$\tilde{A}(t)$ analytic over the closed interval $I$. Then, for every $t\in I$
there exist matrix-valued functions $\tilde{Q}(t)$ and $\tilde{\Lambda}(t)$
analytic over $I$ such that:

$\tilde{A}(t)=\tilde{Q}(t)\tilde{\Lambda}(t)\tilde{Q}(t)^{H},\text{ with
}\tilde{\Lambda}(t)=\text{diag}(\tilde{\lambda}_{1}(t),\dots,\tilde{\lambda}_{n}(t)),\;\tilde{Q}(t)^{H}\tilde{Q}(t)=I,$
(7)

for every $t\in I$; see [9, Chapter II, Section 6] (we refer to [4] for
extensions to the non-analytic case). The elements of the diagonal matrix
$\tilde{\Lambda}(t)$ are analytic functions and, for every $t\in I$, the
$\tilde{\lambda}_{j}(t)$ are the eigenvalues (eigencurves) of $\tilde{A}(t)$.
The columns of $\tilde{Q}(t)$, denoted
$\tilde{q}_{1}(t),\dots,\tilde{q}_{N}(t)$, are the corresponding eigenvectors
(analytic over $I$).

Given $A(t,s)\in\mathcal{A}_{\Theta}^{N\times N}(I)$, the $\star$-eigenproblem
is to find the $\star$-eigenvalues $\lambda(t,s)\in\mathcal{A}_{\Theta}(I)$
and the $\star$-eigenvector $q(t,s)\in\mathcal{A}^{N\times 1}(I)$ such that

$A(t,s)\star q(t,s)=\lambda(t,s)\star q(t,s).$ (8)

If $\lambda(t,s)$ and $q(t,s)$ exist, then $q(t,s)\star a(t,s)$ is also a
$\star$-eigenvector, for every $a(t,s)\not\equiv 0$ from $\mathcal{A}(I)$. For
the specific case of interest, where $A(t,s)=\tilde{A}(t)\Theta(t-s)$, the
solution to the $\star$-eigenproblem is in the following theorem.

######  Theorem 3.1.

Let $A(t,s)=\tilde{A}(t)\Theta(t-s)$ be in $\mathcal{A}_{\Theta}(I)$, and let
$\tilde{\lambda}_{i}(t)$ and $\tilde{q}_{i}(t)$, be the (analytic) eigencurves
and the corresponding eigenvectors as defined in (7) for $i=1,\dots,N$. Then,
the solution to the $\star$-eigenvalue problem (8) is given by

$\lambda_{i}(t,s)=\tilde{\lambda}_{i}(t)\Theta(t-s),\quad
q_{i}(t,s)=\tilde{q}_{i}^{\prime}(t)\Theta(t-s)+\tilde{q}_{i}(t)\delta(t-s),\quad
i=1,\dots,N.$

where $\tilde{q}_{i}^{\prime}(t)$ is the derivative of $\tilde{q}_{i}(t)$.

######  Proof 3.2.

First, note that

$\displaystyle\tilde{\lambda}_{i}(t)\delta(t-s)\star\tilde{q}_{i}(t)\Theta(t-s)$
$\displaystyle=\tilde{\lambda}_{i}(t)\int_{I}\delta(t-\tau)\tilde{q}_{i}(\tau)\Theta(\tau-s)\,\text{d}\tau$
$\displaystyle=\tilde{\lambda}_{i}(t)\tilde{q}_{i}(t)\Theta(t-s)=\tilde{A}(t)\tilde{q}_{i}(t)\Theta(t-s)$
$\displaystyle=\tilde{A}(t)\delta(t-s)\star\tilde{q}_{i}(t)\Theta(t-s).$

Using the fact that
$\tilde{\lambda}_{i}(t)\delta(t-s)\star\Theta(t-s)=\tilde{\lambda}_{i}(t)\Theta(t-s)$,
and that
$\delta^{\prime}(t-s)\star\Theta(t-s)=\Theta(t-s)\star\delta^{\prime}(t-s)=\delta(t-s)$,
see Table 1, we obtain (we omit the variables for the sake of readability)

$\displaystyle\tilde{\lambda}_{i}\delta\star\tilde{q}_{i}\Theta$
$\displaystyle=\tilde{\lambda}_{i}\delta\star\Theta\star\delta^{\prime}\star\tilde{q}_{i}\Theta=\tilde{\lambda}_{i}\Theta\star\delta^{\prime}\star\tilde{q}_{i}\Theta=\tilde{\lambda}_{i}\Theta\star
q_{i},$

where $q_{i}(t,s):=\delta^{\prime}(t-s)\star\tilde{q}_{i}(t)\Theta(t-s)$.
Similarly, $\tilde{A}\delta\star\tilde{q}_{i}\Theta=\tilde{A}\Theta\star
q_{i}$. Combining these results, we get

$\displaystyle\tilde{\lambda}_{i}\Theta\star
q_{i}=\tilde{\lambda}_{i}\delta\star\tilde{q}_{i}\Theta=\tilde{\lambda}_{i}\tilde{q}_{i}\Theta=\tilde{A}\tilde{q}_{i}\Theta=\tilde{A}\delta\star\tilde{q}_{i}\Theta=\tilde{A}\Theta\star
q_{i}.$

Finally, we obtain the following expression for the $\star$-eigenvectors:

$\displaystyle q_{i}(t,s)$
$\displaystyle=\delta^{\prime}(t-s)\star\tilde{q}_{i}(t)\Theta(t-s)$
$\displaystyle=\tilde{q}_{i}^{\prime}(t)\Theta(t-s)+\tilde{q}_{i}(t)\delta(t-s);$

see Table 2. As a final remark, note that all the $\star$-products are well-
defined thanks to the fact that the $\tilde{\lambda}_{i}(t)$ and
$\tilde{q}_{i}(t)$ are analytic functions.

Consider the matrix

$A(t,s)=\tilde{A}_{-1}(t,s)\Theta(t-s)+\sum_{j=0}^{k}\tilde{A}_{j}(t)\delta^{(j)}(t-s)\in\mathcal{A}^{N\times
M}(I)$ (9)

we define the Hermitian transpose of $A$ as

$A^{H}(t,s)=\tilde{A}_{-1}^{H}(t,s)\Theta(t-s)+\sum_{j=0}^{k}\tilde{A}^{H}_{j}(t)\delta^{(j)}(t-s)\in\mathcal{A}^{M\times
N}(I),$ (10)

with $\tilde{A}_{j}^{H}$ the usual Hermitian transpose of a matrix. As an
immediate consequence of Theorem 3.1, we have the following
$\star$-factorization of $A(t,s)$.

######  Corollary 3.3.

Under the same assumption of Theorem 3.1, we have

$A(t,s)=Q(t,s)\star\Lambda(t,s)\star Q(t,s)^{H},$

with $\Lambda(t,s)=\tilde{\Lambda}(t)\Theta(t-s)$ and
$Q(t,s)=[q_{1}(t,s),\dots,q_{N}(t,s)]$. Moreover, it holds

$Q(t,s)\star Q(t,s)^{H}=Q(t,s)^{H}\star Q(t,s)=I_{\star},$

that is, $Q(t,s)^{H}$ is the matrix $\star$-inverse of $Q(t,s)$.

######  Proof 3.4.

We first show that for every $i,j=1,\dots,N$ we have

$q_{i}(t,s)^{H}\star q_{j}(t,s)=\delta_{ij}\delta(t-s),$

with $\delta_{ij}$ the Kronecker delta. Since
$q_{k}(t,s)=\delta^{\prime}(t-s)\star\tilde{q}_{k}\Theta(t-s)$, for
$k=1,\dots,N$, then

$\displaystyle q_{i}(t,s)^{H}\star q_{j}(t,s)$
$\displaystyle=\big{(}\delta^{\prime}(t-s)\star\tilde{q}_{i}^{H}(t)\Theta(t-s)\big{)}\star\big{(}\delta^{\prime}(t-s)\star\tilde{q}_{j}(t)\Theta(t-s)\big{)}$
$\displaystyle=\delta^{\prime}(t-s)\star\big{(}\tilde{q}_{i}^{H}(t)\Theta(t-s)\star\delta^{\prime}(t-s)\big{)}\star\tilde{q}_{j}(t)\Theta(t-s)$
$\displaystyle=\delta^{\prime}(t-s)\star\big{(}\tilde{q}_{i}^{H}(t)\delta(t-s)\star\tilde{q}_{j}(t)\Theta(t-s)\big{)}$
$\displaystyle=\delta^{\prime}(t-s)\star\tilde{q}_{i}^{H}(t)\tilde{q}_{j}(t)\Theta(t-s)=\delta^{\prime}(t-s)\star\delta_{ij}\Theta(t-s)$
$\displaystyle=\delta_{ij}\delta(t-s).$

From Theorem 3.1 we get the equality

$A(t,s)\star Q(t,s)=Q(t,s)\star\Lambda(t,s).$

The conclusion follows from $\star$-multiplying from the right by
$Q(t,s)^{H}$.

Since our final goal is to measure an error, we need to introduce a
$\star$-inner product and the relative $\star$-norm. To this aim, we take
inspiration from the results in [16], but we develop them in a different
direction. Following [16], we define the _$\star$ -Hermitian-transpose_ of
$A(t,s)$ in (9) as

$A^{\star
H}(t,s):=A^{H}(s,t)=\tilde{A}^{H}_{-1}(s,t)\Theta(s-t)+\sum_{j=0}^{k}\tilde{A}_{j}^{H}(s)\delta^{(j)}(s-t)\in\mathcal{A}^{M\times
N}(I).$

Roughly speaking, one has to take the usual Hermitian transpose and then swap
the variable $t,s$. Note the difference with the Hermitian transpose (10).
Now, setting $I=[a,b]$, and given $v,w$ such that $\Theta\star v,\Theta\star
w\in\mathcal{A}_{\Theta}^{N\times 1}(I)$, for any fixed $s\in[a,b)$ we can
define the inner product:

$\langle v,w\rangle_{\star}(s):=\left((\Theta\star v)^{\star
H}\star\Theta\star
w\right)(s,s)=\int_{I}v^{H}(\tau,s)w(\tau,s)\,\text{d}\tau.$

Note that, denoting $\Theta(t-s)\star v(t,s)=\tilde{V}(t,s)\Theta(t-s)$ and
$\Theta(t-s)\star w(t,s)=\tilde{W}(t,s)\Theta(t-s)$, then

$\langle
v,w\rangle_{\star}(s)=\int_{s}^{b}\tilde{V}^{H}(\tau,s)\tilde{W}(\tau,s)\,\text{d}\tau,$

which, for the fixed $s$, is the classical inner product of the functions
$\tilde{V}(\cdot,s)$ and $\tilde{W}(\cdot,s)$ on the interval $[s,b]$ (note
that $v,w\equiv 0$ if and only if $\tilde{V},\tilde{W}\equiv 0$). The inner
product $\langle v,w\rangle_{\star}(s)$ is, in fact, a family of inner
products depending on the parameter $s\in[a,b)$. With an abuse of notation, we
refer to the function $\langle v,w\rangle_{\star}:[a,b)\rightarrow\mathbb{C}$
as the _$\star$ -inner product_ of $v$ and $w$. Thus, again with a notation
abuse, we define the _$\star$ -norm_ as

$\|v\|_{\star}(s):=\sqrt{\langle v,v\rangle_{\star}}(s),\quad s\in[a,b).$

The definition is justified by the following theorem.

######  Theorem 3.5 (Properties of the $\star$-norm).

Given $v,w$ such that $\Theta\star v,\Theta\star
w\in\mathcal{A}_{\Theta}^{N\times 1}(I)$, with $I=[a,b]$, then the following
properties hold for every $s\in[a,b)$:

  1. 1.

$\|v\|_{\star}(s)\geq 0$;

  2. 2.

$\|v\|_{\star}(s)\equiv 0$ if and only if $v\equiv 0$;

  3. 3.

$\|\alpha v\|_{\star}(s)=\|\alpha\delta\star
v\|_{\star}(s)=|\alpha|\|v\|_{\star}(s)$ for any scalar $\alpha\in\mathbb{C}$;

  4. 4.

$\|v+w\|_{\star}(s)\leq\|v\|_{\star}(s)+\|w\|_{\star}(s)$.

Hence $\|v\|_{\star}(s)$ is a norm for every fixed $s\in[a,b)$.

######  Proof 3.6.

Since $\Theta\star v=\tilde{V}\Theta$, with $\tilde{V}$ an analytic function
over $I^{2}$, then

$\|v\|_{\star}^{2}(s)=\int_{s}^{b}\tilde{V}^{H}(\tau,s)\tilde{V}(\tau,s)\,\text{d}\tau,$

is the classical norm of the function $\tilde{V}(\cdot,s)$ over the interval
$[s,b]$. Thus Item 1. is trivial. Item 2. is true since $\tilde{V}(t,s)\equiv
0$ over $I^{2}$ if and only if $v\equiv 0$ over $I^{2}$. Item 3. and 4. hold
since $\Theta\star\alpha v=\alpha(\Theta\star v)$ and
$\Theta\star(v+w)=\Theta\star v+\Theta\star w$.

######  Lemma 3.7.

Let $Q(t,s)$ as in Corollary 3.3, then for every
$v,w\in\mathcal{A}_{\Theta}^{N\times 1}(I)$, it holds

$\langle Q\star v,Q\star w\rangle_{\star}(s)=\langle Q^{H}\star v,Q^{H}\star
w\rangle_{\star}(s)=\langle v,w\rangle_{\star}(s),\quad s\in[a,b),$

that is $Q$ and $Q^{H}$ are unitary with respect to
$\langle\cdot,\cdot\rangle_{\star}$ (note that $Q^{H}\neq Q^{\star H}$).

######  Proof 3.8.

Recalling that $Q(t,s)=\delta^{\prime}(t-s)\star\tilde{Q}(t)\Theta(t-s)$, we
get $\Theta(t-s)\star Q(t,s)=\tilde{Q}(t)\Theta(t-s)$. Therefore,

$\displaystyle\langle Q\star v,Q\star w\rangle_{\star}(s)$
$\displaystyle=\left[(\tilde{Q}\Theta\star v)^{\star
H}\star\tilde{Q}\Theta\star w\right](s,s).$

Now, denoting $\tilde{V}(t,s)\Theta(t-s):=\Theta(t-s)\star v(t,s)$ and
$\tilde{W}(t,s)\Theta(t-s):=\Theta(t-s)\star v(t,s)$, we observe

$\displaystyle\tilde{Q}(t)\Theta(t-s)\star v(t,s)$
$\displaystyle=\tilde{Q}(t)\left(\Theta(t-s)\star
v(t,s)\right)=\tilde{Q}(t)\tilde{V}(t,s)\Theta(t-s),$
$\displaystyle\tilde{Q}(t)\Theta(t-s)\star w(t,s)$
$\displaystyle=\tilde{Q}(t)\left(\Theta(t-s)\star
w(t,s)\right)=\tilde{Q}(t)\tilde{W}(t,s)\Theta(t-s).$

Therefore,

$\displaystyle\left[(\tilde{Q}\Theta\star v)^{\star
H}\star\tilde{Q}\Theta\star w\right](s,s)$
$\displaystyle=\int_{s}^{b}\tilde{V}^{H}(\tau,s)\tilde{Q}^{H}(\tau)\tilde{Q}(\tau)\tilde{W}(\tau,s)\,\text{d}\tau$
$\displaystyle=\int_{s}^{b}\tilde{V}^{H}(\tau,s)\tilde{W}(\tau,s)\,\text{d}\tau$
$\displaystyle=\left[(\Theta\star v)^{\star H}\star\Theta\star
w\right](s,s)=\langle v,w\rangle_{\star}(s).$

Analogous arguments show that $\langle Q^{H}\star v,Q^{H}\star
w\rangle_{\star}=\langle v,w\rangle_{\star}$.

Finally, given a matrix $A$ so that $\Theta\star
A\in\mathcal{A}_{\Theta}^{N\times N}(I)$, we define the _induced matrix
$\star$-norm_ of $A$ as

$\|A\|_{\star}(s):=\sup_{v\not\equiv 0\,:\,\Theta\star
v\in\mathcal{A}_{\Theta}^{N\times 1}(I)}\frac{\|A\star
v\|_{\star}(s)}{\|v\|_{\star}(s)},\quad s\in[a,b).$ (11)

The term norm is again an abuse of notation. The following theorem explains in
which sense $\|A\|_{\star}$ is a norm and provides several useful properties.

######  Theorem 3.9 (Properties of the induced matrix $\star$-norm).

Let $A,B$ such that $\Theta\star A,\Theta\star
B\in\mathcal{A}_{\Theta}^{N\times N}(I)$ with $I=[a,b]$. Then, $\|A\|_{\star}$
satisfies the following properties for every $s\in[a,b)$:

  1. 1.

$\|A\|_{\star}(s)\geq 0$;

  2. 2.

$\|A\|_{\star}(s)\equiv 0$ if and only if $A\equiv 0$;

  3. 3.

$\|\alpha A\|_{\star}(s)=\|\alpha\delta\star
A\|_{\star}(s)=|\alpha|\|A\|_{\star}(s)$ for any scalar $\alpha\in\mathbb{C}$;

  4. 4.

$\|A+B\|_{\star}(s)\leq\|A\|_{\star}(s)+\|B\|_{\star}(s)$;

  5. 5.

$\|A\star B\|_{\star}(s)\leq\|A\|_{\star}(s)\star\|B\|_{\star}(s)$.

Therefore, $\|\cdot\|_{\star}(s)$ is a sub-multiplicative matrix norm for
every fixed $s\in[a,b)$.

######  Proof 3.10.

Items 1–4 are corollaries of Theorem 3.5. Note that

$\|A\star v\|_{\star}(s)=\frac{\|A\star
v\|_{\star}(s)}{\|v\|_{\star}(s)}\|v\|_{\star}(s)\leq\|A\|_{\star}(s)\,\|v\|_{\star}(s),\quad
s\in[a,b).$

Therefore, $\|A\star B\star v\|_{\star}(s)\leq\|A\|_{\star}(s)\star\|B\star
v\|_{\star}(s)\leq\|A\|_{\star}(s)\star\|B\|_{\star}(s)$, proving Item 5.

##  4 Approximation of the $\star$-resolvent

Let $\tilde{v}\in\mathbb{C}^{N}$ be a (constant) vector and the
$A(t,s)=\tilde{A}(t)\Theta(t-s)\in\mathcal{A}_{\Theta}^{N\times N}(I)$ a
matrix-valued function, with $\tilde{A}(t)$ Hermitian for $t\in I$ and
$I=[a,b]$. We want to find the optimal $\star$-polynomials of degree at most
$n$ approximating the $\star$-resolvent $R^{\star}(A)\tilde{v}$ in the sense
of the $\star$-norm. That is, finding $q^{\star}\in\mathcal{P}_{n}^{\star}$ so
that

$\|R^{\star}(A)\tilde{v}-q^{\star}(A)\tilde{v}\|_{\star}(s)=\min_{p^{\star}\in\mathcal{P}^{\star}_{n}}\|R^{\star}(A)\tilde{v}-p^{\star}(A)\tilde{v}\|_{\star}(s),\quad
s\in[a,b).$ (12)

By Corollary 3.3, $A(t,s)=Q(t,s)\star\Lambda(t,s)\star Q(t,s)^{H}$, where the
diagonal elements of $\Lambda$ are the $\star$-eigenvalues
$\lambda_{j}(t,s)=\tilde{\lambda}_{j}(t)\Theta(t-s)$, $j=1,\dots,n$. Since
$Q^{H}\star Q=I_{\star}$, then we have $A^{\star 2}=Q\star\Lambda\star
Q^{H}\star Q\star\Lambda\star Q^{H}=Q\star\Lambda^{\star 2}\star Q^{H}$, and
hence

$A^{\star k}=Q\star\Lambda^{\star k}\star Q^{H},\quad k=0,1,2,\dots\,.$ (13)

######  Theorem 4.1.

Let $w=Q^{H}\star\tilde{v}\delta=Q^{H}\tilde{v}$. Then, the problem (12) is
equivalent to finding the $n$-degree $\star$-polynomial $q^{\star}$ such that

$\|R^{\star}(A)\tilde{v}-q^{\star}(A)\tilde{v}\|_{\star}(s)=\min_{p^{\star}\in\mathcal{P}^{\star}_{n}}\|R^{\star}(\Lambda)\star
w-p^{\star}(\Lambda)\star w\|_{\star}(s),\quad s\in[a,b).$

Moreover, for a fixed $s\in[a,b)$, the error can be bounded by

$\frac{\|R^{\star}(A)\tilde{v}-q^{\star}(A)\tilde{v}\|_{\star}(s)}{\|\tilde{v}\delta\|_{\star}(s)}\leq\min_{p^{\star}\in\mathcal{P}^{\star}_{n}}\,\max_{i=1,\dots,N}\|R^{\star}(\lambda_{i})-p^{\star}(\lambda_{i})\|_{\star}(s),\quad
s\in[a,b),$

where $\lambda_{1}(t,s),\dots\lambda_{N}(t,s)$ are the $\star$-eigenvalues of
$A(t,s)$.

######  Proof 4.2.

Every $\star$-polynomial can be expanded in the $\star$-monomial basis, i.e.,
$p^{\star}(x)=\alpha_{0}\delta+\alpha_{1}x+\dots+\alpha_{n}x^{\star n}$.
Therefore, by using (13), we get

$p^{\star}(A)=Q\star p^{\star}(\Lambda)\star Q^{H},\quad R^{\star}(A)=Q\star
R^{\star}(\Lambda)\star Q^{H}.$

Hence, by Lemma 3.7 and Theorem 3.9, for every fixed $s\in[a,b)$, we get

$\displaystyle\|R^{\star}(A)\tilde{v}-p^{\star}(A)\tilde{v}\|_{\star}(s)$
$\displaystyle=\|Q\star(R^{\star}(\Lambda)-p^{\star}(\Lambda))\star
Q^{H}\star\tilde{v}\delta\|_{\star}(s)$
$\displaystyle=\|(R^{\star}(\Lambda)-p^{\star}(\Lambda))\star
Q^{H}\star\tilde{v}\delta\|_{\star}(s)$
$\displaystyle\leq\|R^{\star}(\Lambda)-p^{\star}(\Lambda)\|_{\star}(s)\;\|Q^{H}\star\tilde{v}\delta\|_{\star}(s)$
$\displaystyle\leq\|R^{\star}(\Lambda)-p^{\star}(\Lambda)\|_{\star}(s)\;\|\tilde{v}\delta\|_{\star}(s)$
$\displaystyle\leq\max_{i=1,\dots,N}\|R^{\star}(\lambda_{i})-p^{\star}(\lambda_{i})\|_{\star}(s)\;\|\tilde{v}\delta\|_{\star}(s),$

concluding the proof.

Now we can prove the main result of this paper.

###  4.1 Proof of Theorem 2.1

Denote $p^{\star}(x)=\sum_{k=0}^{n}\alpha_{k}x^{\star k}$. By Lemma 2.2 and
Theorem 4.1, for $s\in[a,b)$ we get

$\displaystyle\|R^{\star}(\lambda_{i})-p^{\star}(\lambda_{i})\|_{\star}^{2}(s)$
$\displaystyle=\int_{s}^{b}\left|\sum_{k=0}^{\infty}\frac{(L_{i}(\tau,s))^{k}}{k!}-\sum_{k=0}^{n}\alpha_{k}\frac{(L_{i}(\tau,s))^{k}}{k!}\right|^{2}\,\text{d}\tau$
$\displaystyle=\int_{s}^{b}\left|\exp(L_{i}(\tau,s))-p(L_{i}(\tau,s))\right|^{2}\,\text{d}\tau,$

where $L_{i}(\cdot,s)$ is the primitive of $\tilde{\lambda}_{i}(\cdot)$ so
that $L_{i}(s,s)=0$ and $p(t)=\sum_{k=0}^{n}\frac{\alpha_{k}}{k!}t^{k}$ is a
(usual) polynomial. Note that $L_{i}(\tau,s)$ is a real function with values
in the interval

$J_{i}(s)=\left[\min_{\tau\in[s,b]}L_{i}(\tau,s),\max_{\tau\in[s,b]}L_{i}(\tau,s)\right].$

Therefore,

$\|R^{\star}(\lambda_{i})-p^{\star}(\lambda_{i})\|_{\star}(s)\leq
E_{n}(J_{i}(s))\sqrt{(b-s)}.$

Under the assumptions of the Theorem, the interval $J_{i}(s)\subset J$ for
every $s\in[a,b)$. By the classical Bernstein’s Theorem (see, e.g., [11, page
91]), there exist constant $M>0$ and $0<\rho<1$ such that

$E_{n}(J)\sqrt{(b-a)}\leq M\rho^{n+1}.$

Now, note that

$\left(\int_{s}^{b}|U(\tau,s)\tilde{v}-(\Theta\star
q^{\star}(A))(\tau,s)\tilde{v}|^{2}\right)^{\frac{1}{2}}=\|R^{\star}(A)\tilde{v}-q^{\star}(A)\tilde{v}\|_{\star}(s)\;\|\tilde{v}\delta\|_{\star}(s).$

Therefore,

$\left(\int_{s}^{b}|U(\tau,s)\tilde{v}-(\Theta\star
q^{\star}(A))(\tau,s)\tilde{v}|^{2}\right)^{\frac{1}{2}}\leq
M\rho^{n+1}\|\tilde{v}\delta\|_{\star}(s).$

Setting $s=a$ concludes the proof.

##  5 Conclusion

The results presented are a first step in the direction of a new approach for
the analysis of $\star$-product approximations of the solution of linear non-
autonomous ordinary differential equations. The error analysis can affect the
study of the related analytic expression and symbolic algorithms [5, 8] as
well as their numerical counterparts [3] opening the way to the use of
efficient Krylov subspace methods. Moreover, they can open the way to the
analysis of the _localization_ (or _decay_) phenomenon of the time-ordered
exponential [2, 6] by extending the techniques presented, e.g., in [1].
Finally, future works will try to derive more refined bounds for the error
than the one in Theorem 2.1. This will be possible by using more information
on the eigecurves’ behavior.

## References

  * [1] M. Benzi and P. Boito, Decay properties for functions of matrices over $C^{*}$-algebras, Linear Algebra Appl., 456 (2014), pp. 174–198.
  * [2] M. Benzi, V. Simoncini, editors, Exploiting hidden structure in matrix computations: Algorithms and applications, Springer; 2016.
  * [3] C. Bonhomme, S. Pozza, and N. V. Buggenhout, A new fast numerical method for the generalized Rosen-Zener model, arXiv preprint arXiv:2311.04144, (2023).
  * [4] L. Dieci and T. Eirola, On smooth decompositions of matrices, SIAM J. Matrix Anal. Appl., 20 (1999), pp. 800–19.
  * [5] P.-L. Giscard and C. Bonhomme, Dynamics of quantum systems driven by time-varying Hamiltonians: Solution for the Bloch-Siegert Hamiltonian and applications to NMR, Phys. Rev. Research, 2 (2020), p. 023081.
  * [6] P.-L. Giscard, K. Lui, S. J. Thwaite, and D. Jaksch, An exact formulation of the time-ordered exponential using path-sums, J. Math. Phys., 56 (2015), p. 053503.
  * [7] P.-L. Giscard and S. Pozza, Lanczos-like algorithm for the time-ordered exponential: The $\ast$-inverse problem, Appl. Math., 65 (2020), pp. 807–827.
  * [8] P.-L. Giscard and S. Pozza, A Lanczos-like method for non-autonomous linear ordinary differential equations, Boll. Unione Mat. Ital., 16 (2023), pp. 81–102.
  * [9] T. Kato, Perturbation Theory for Linear Operators, Second ed., Springer-Verlag, Berlin, 1976.
  * [10] J. Liesen and Z. Strakos, Krylov subspace methods: principles and analysis, Oxford University Press, 2012.
  * [11] G. Meinardus, Approximation of Functions: Theory and Numerical Methods, Springer Tracts Natur. Philos., vol. 13, Springer, New York, 1967.
  * [12] S. Pozza, A new closed-form expression for the solution of ODEs in a ring of distributions and its connection with the matrix algebra, Linear Multilinear Algebra, to appear. arXiv:2302.11375 [math.NA]
  * [13] S. Pozza and N. Van Buggenhout, A new Legendre polynomial-based approach for non-autonomous linear ODEs, Electron. Trans. Numer. Anal., to appear. arXiv:2303.11284 [math.NA]
  * [14] S. Pozza and N. Van Buggenhout, A new matrix equation expression for the solution of non-autonomous linear systems of ODEs, Proc. Appl. Math. Mech., 22 (2023), p. e202200117.
  * [15] , A $\star$-product solver with spectral accuracy for non-autonomous ordinary differential equations, Proc. Appl. Math. Mech., 23 (2023), p. e202200050.
  * [16] M. Ryckebusch, A Fréchet-Lie group on distributions, arXiv preprint arXiv:2307.09037, (2023).