# Higher Order Lipschitz Greedy Recombination Interpolation Method (HOLGRIM)

Terry Lyons and Andrew D. McLeod

###### Abstract

In this paper we introduce the _Higher Order Lipschitz Greedy Recombination
Interpolation Method_ (HOLGRIM) for finding sparse approximations of
${\mathrm{Lip}}(\gamma)$ functions, in the sense of Stein, given as a linear
combination of a (large) number of simpler ${\mathrm{Lip}}(\gamma)$ functions.
HOLGRIM is developed as a refinement of the _Greedy Recombination
Interpolation Method_ (GRIM) in the setting of ${\mathrm{Lip}}(\gamma)$
functions. HOLGRIM combines dynamic growth-based interpolation techniques with
thinning-based reduction techniques in a data-driven fashion. The dynamic
growth is driven by a greedy selection algorithm in which multiple new points
may be selected at each step. The thinning reduction is carried out by
_recombination_ , the linear algebra technique utilised by GRIM. We establish
that the number of non-zero weights for the approximation returned by HOLGRIM
is controlled by a particular packing number of the data. The level of data
concentration required to guarantee that HOLGRIM returns a good sparse
approximation is decreasing with respect to the regularity parameter
$\gamma>0$. Further, we establish complexity cost estimates verifying that
implementing HOLGRIM is feasible.

###### Contents

  1. 1 Introduction
  2. 2 Lipschitz Functions and Sandwich Theorems
  3. 3 Sparse Approximation Problem Formulation
  4. 4 Extension to Compact Domains
  5. 5 Pointwise Values Via Linear Functionals
  6. 6 The HOLGRIM Algorithm
  7. 7 Complexity Cost
  8. 8 Theoretical Guarantees Inherited from GRIM
  9. 9 Point Separation Lemma
  10. 10 The HOLGRIM Convergence Theorem

##  1 Introduction

Approximating the behaviour of a complex system via a linear combination of
simpler functions is a central challenge within machine learning. Models
following this guiding ethos have, for example, been used for facial
recognition [BGLT97], COVID-19 deaths prediction [BS22], image recognition
[HRSZ15, HKR15, KTT18], language translation [CDLT18], anomaly detection
[CCFLS20, ACLLN24], landmark-based action recognition [JLNSY17, JNYZ24],
emotion recognition [LLNNSW19], early sepsis detection [HKLMNS19, HKLMNS20],
Bipolar and Borderline Personality Disorder classification [AGGLS18,
LLNSTWW20, LLSVWW21], longitudinal language modelling [BCKLLT24], and learning
solutions to differential equations [FKLM20, FKLMS21, FKLLO21, FKLL21,
CLLMQW24].

A priori, considering a larger number of simple functions enables one to
capture the affects of more complicated systems. However, a large number of
simple functions can lead to a linear combination with a high computational
complexity. One approach to reducing this computational complexity is to find
a sparse approximation of the linear combination of functions. Sparse
representations have been applied to tasks including, for example, image
processing [EMS08, BMPSZ08, BMPSZ09], data assimilation [MM13], sensor
placement in nuclear reactors [ABGMM16, ABCGMM18], DNA denoising [KK20], and
inference within machine learning [ABDHP21, NPS22].

Numerous techniques have been developed for finding sparse approximations,
including _Least Absolute Shrinkage and Selection Operator_ (LASSO) regression
[CM73, SS86, Tib96, LY07, DGOY08, GO09, XZ16, TW19], the Empirical
Interpolation Method [BMNP04, GMNP07, MNPP09], its subsequent generalisation
the Generalised Empirical Interpolation Method (GEIM) [MM13, MMT14], Pruning
[Ree93, AK13, CHXZ20, GLSWZ21], Kernel Herding [Wel09a, Wel09b, CSW10, BLL15,
BCGMO18, TT21, PTT22], Convex Kernel Quadrature [HLO21], and Kernel Thinning
[DM21-I, DM21-II, DMS21]. In this paper we focus on the _Greedy Recombination
Interpolation Method_ (GRIM) introduced in [LM22-I].

GRIM is a technique for finding sparse approximations of linear combinations
of functions that combines dynamic growth-based interpolation techniques with
thinning-based reduction techniques to inductively refine a sequence of
approximations. Theoretical guarantees for the performance of GRIM are
established in Section 6 of [LM22-I], whilst empirical demonstrations of its
performance are provided by the numerical examples covered in Section 7 of
[LM22-I]. It is established in [LM22-I] that GRIM can be applied in several
familiar settings including kernel quadrature and approximating sums of
continuous functions; see Section 2 in [LM22-I].

For the readers convenience, we briefly recall the general sparse
approximation problem that GRIM is designed to tackle [LM22-I]. Let $X$ be a
real Banach space and ${\cal N}\in{\mathbb{Z}}_{\geq 1}$ be a (large) positive
integer. Assume that ${\cal F}=\\{f_{1},\ldots,f_{{\cal N}}\\}\subset X$ is a
collection of non-zero elements, and that $a_{1},\ldots,a_{{\cal
N}}\in{\mathbb{R}}\setminus\\{0\\}$. Consider the element $\varphi\in X$
defined by $\varphi:=\sum_{i=1}^{{\cal N}}a_{i}f_{i}$. Let $X^{\ast}$ denote
the dual of $X$ and suppose that $\Sigma\subset X^{\ast}$ is a finite subset
with cardinality $\Lambda\in{\mathbb{Z}}_{\geq 1}$. We adopt the same
terminology as used in [LM22-I] that the set ${\cal F}$ consists of the
_features_ whilst the set $\Sigma$ consists of _data_. Then GRIM is designed
to tackle the following sparse approximation problem. Given $\varepsilon>0$,
find an element $u=\sum_{i=1}^{{\cal N}}b_{i}f_{i}\in\operatorname{Span}({\cal
F})\subset X$ such that the cardinality of the set $\\{i\in\\{1,\ldots,{\cal
N}\\}:b_{i}\neq 0\\}$ is _less_ than ${\cal N}$ and that $u$ is close to
$\varphi$ throughout $\Sigma$ in the sense that, for every $\sigma\in\Sigma$,
we have $|\sigma(\varphi-u)|\leq\varepsilon$.

We briefly recall the strategy of the Banach GRIM algorithm developed in
[LM22-I] to tackle this problem. The Banach GRIM algorithm is a hybrid
combination of the dynamic growth of a greedy selection algorithm, in a
similar spirit to GEIM [MM13, MMT14, MMPY15], with the thinning reduction of
recombination that underpins the successful convex kernel quadrature approach
of [HLO21]. A collection of linear functionals $L\subset\Sigma$ is greedily
grown during the Banach GRIM algorithm. After each extension of $L$,
recombination is applied to find an approximation of $\varphi$ that coincides
with $\varphi$ throughout $L$ (cf. the _Recombination Thinning Lemma 3.1_ in
[LM22-I]). The subset $L$ is extended by first fixing an integer
$m\in{\mathbb{Z}}_{\geq 1}$, and then adding to $L$ the $m$ linear functionals
from $\Sigma$ achieving the largest absolute value when applied to the
difference between $\varphi$ and the current approximation of $\varphi$ (cf.
Section 4 of [LM22-I]). These steps are iteratively applied a set number of
times during the Banach GRIM algorithm detailed in Section 4 of [LM22-I].

In this article we consider the use of the Banach GRIM algorithm for finding
sparse approximations of sums of continuous functions. That is, we assume that
the Banach space $X$ in the formulation above can be embedded into a space of
continuous functions. We assume that $X$ embeds into a space of continuous
functions rather than assuming $X$ is itself a space of continuous functions
since continuity alone is insufficient regularity for interpolation methods.
Interpolation methods, broadly speaking, work on the premise that knowing the
value of a function at a point informs one about the functions values at
nearby points.

However, this is _not_ true for continuous functions. Indeed, suppose that
$\Omega\subset{\mathbb{R}}^{d}$ and $f\in C^{0}(\Omega)$ is a real-valued
continuous function $\Omega\to{\mathbb{R}}$. Assume that $p\in\Omega$ and
$f(p)=0$. Then, regardless of how close a point $q\in\Omega\setminus\\{p\\}$
is to $p$, we cannot obtain any better bound for the value $f(q)$ than the
immediate naive estimate that $|f(q)|\leq||f||_{C^{0}(\Omega)}$. Knowing that
$f$ vanishes at $p$ does not enable us to conclude that $f$ must remain small
on some definite neighbourhood of the point $p$.

A consequence of this simple observation is that the theoretical guarantees
for the performance of the Banach GRIM algorithm established in Theorem 6.2 in
[LM22-I] are essentially useless for the case that $X=C^{0}(\Omega)$ and
$\Sigma$ is taken to be the finite collection of point masses in the dual-
space $C^{0}(\Omega)^{\ast}$ associated to a finite subset of $\Omega$. Given
$p,q\in\Omega$ with $p\neq q$, the existence of a continuous function $f\in
C^{0}(\Omega)$ with $||f||_{C^{0}(\Omega)}=1$ and $f(p)=1$ and $f(q)=-1$ means
that the point masses $\delta_{p},\delta_{q}\in C^{0}(\Omega)^{\ast}$ satisfy

$\left|\left|\delta_{p}-\delta_{q}\right|\right|_{C^{0}(\Omega)^{\ast}}=\sup\left\\{\left|\left(\delta_{p}-\delta_{q}\right)(f)\right|~{}:~{}f\in
C^{0}(\Omega)\text{ with }||f||_{C^{0}(\Omega)}=1\right\\}=2.$ (1.1)

Consequently, if $\varepsilon/2C<2$ then (1.1) means that the upper bound $N$
on the maximum number of steps the Banach GRIM algorithm can complete without
terminating established in Theorem 6.2 in [LM22-I] is simply the cardinality
of $\Sigma$, i.e. $N=\\#(\Sigma)$. Thus Theorem 6.2 in [LM22-I] provides only
the obvious (and essentially useless) guarantee that the Banach GRIM algorithm
will return an approximation that is within $\varepsilon$ of $\varphi$ at
every $\sigma\in\Sigma$ once we have grown the collection of linear
functionals $L\subset\Sigma$ at which we require the approximation to match
$\varphi$ (see Section 4 in [LM22-I]) to be the entirety of $\Sigma$.

In this article we overcome the limitations outlined above by achieving the
following main goals. MAIN GOALS

  1. (1)

Fix a choice of a Banach space $X$ of functions exhibiting an appropriate
level of regularity from the perspective of interpolation.

  2. (2)

Adapt the Banach GRIM algorithm from [LM22-I] to the setting of the particular
choice of the Banach space $X$ determined in MAIN GOALS ((1)).

From the perspective of interpolation, we want the notion of regularity
determined by our choice of Banach space $X$ to ensure, in a quantified sense,
that for $f\in X$ the knowledge of the value of $f$ at a point determines its
values at nearby points up to an arbitrarily small error. Moreover, given our
machine learning motivations, we want the notion of regularity determined by
our choice of Banach space $X$ to make sense on finite subsets.

The class of ${\mathrm{Lip}}(\gamma)$ functions, for some $\gamma>0$, in the
sense of Stein [Ste70] exhibit an appropriate level of regularity. This notion
of regularity is central to the study of _rough paths_ initiated by the first
author in [Lyo98]; an introduction to the theory of rough paths may be found
in [CLL04], for example. Rough path theory has subsequently underpinned
numerous machine learning techniques developed through the use of the
_signature_ of a path as a feature map; an introductory coverage of such
signature methods may be found in the survey articles [CK16] and [LM22-II],
for example. Moreover, ${\mathrm{Lip}}(\gamma)$ regularity is essential in the
recent efforts to extend the theory of rough paths to the setting of manifolds
[CLL12, BL22], has been combined with classical ODE techniques to obtain the
terminal solutions of _Rough Differential Equations_ (RDEs) [Bou15, Bou22],
and is central to the introduction of _Log Neural Controlled Differential
Equations_ (Log-NCDEs) in [CLLMQW24].

We consider the notion of ${\mathrm{Lip}}(\gamma)$ regularity in similar
generality to that considered in [LM24]. In particular, we let $V$ and $W$ be
finite-dimensional real Banach spaces, ${\cal M}\subset V$ be an arbitrary
closed subset, $\gamma>0$, and consider $X:={\mathrm{Lip}}(\gamma,{\cal M},W)$
to be the space of ${\mathrm{Lip}}(\gamma)$ functions from ${\cal M}$ to $W$
defined, for example, in Definition 2.2 of [LM24] (cf. Definition 2.2 in this
paper). The class ${\mathrm{Lip}}(\gamma,{\cal M},W)$ is a generalisation of
the more familiar notion of $\gamma$-Hölder continuous functions ${\cal M}\to
W$ in the following sense. For $\gamma\in(0,1]$ the space
${\mathrm{Lip}}(\gamma,{\cal M},W)$ coincides with the space of bounded
$\gamma$-Hölder continuous functions ${\cal M}\to W$. That is,
$\psi\in{\mathrm{Lip}}(\gamma,{\cal M},W)$ means that $\psi:{\cal M}\to W$ and
there exists a constant $C>0$ such that whenever $x,y\in{\cal M}$ we have both
$||\psi(x)||_{W}\leq C$ and $||\psi(y)-\psi(x)||_{W}\leq
C||y-x||_{V}^{\gamma}$. For $\gamma>1$ the space ${\mathrm{Lip}}(\gamma,{\cal
M},W)$ gives a sensible higher-order Hölder continuity condition. If
$k\in{\mathbb{Z}}_{\geq 0}$ such that $\gamma\in(k,k+1]$ and $O\subset V$ is
open, then the space ${\mathrm{Lip}}(\gamma,O,W)$ coincides with the space
$C^{k,\gamma-k}(O;W)$ of $k$-times Fréchet differentiable functions $O\to W$
with $(\gamma-k)$-Hölder continuous $k^{\text{th}}$ derivative (cf. Remark
2.6). Stein’s notion of ${\mathrm{Lip}}(\gamma)$ regularity extends this
notion to arbitrary closed subsets. For any $\gamma>0$ and a general closed
subset ${\cal M}\subset V$ there is a natural embedding map
${\mathrm{Lip}}(\gamma,{\cal M},W)\hookrightarrow C^{0}({\cal M};W)$ (cf.
Remark 2.4).

The choice $X:={\mathrm{Lip}}(\gamma,{\cal M},W)$ satisfies both our desired
properties. Firstly, the class ${\mathrm{Lip}}(\gamma,{\cal M},W)$ is well-
defined for _any_ closed subset ${\cal M}\subset V$, and hence the class
${\mathrm{Lip}}(\gamma,\Sigma,W)$ is well-defined for a finite subset
$\Sigma\subset V$. Secondly, the _Lipschitz Sandwich Theorems_ established in
[LM24] yield that the value of $\psi\in{\mathrm{Lip}}(\gamma,{\cal M},W)$ at a
point $p\in{\cal M}$ determines the behaviour of $\psi$, up to arbitrarily
small errors, at points that are sufficiently close to $p$. The _Lipschitz
Sandwich Theorem 3.1_ and the _Pointwise Lipschitz Sandwich Theorem 3.11_ in
[LM24] exhibit quantified statements of this phenomena in which both the sense
in which the behaviour of $\psi$ is determined and the notion of sufficiently
close to the point $p$ are made precise (cf. Theorems 2.9 and 2.10 in this
paper).

There are additional properties that make the class ${\mathrm{Lip}}(\gamma)$
functions an attractive choice from a learning perspective. Given a closed
subset ${\cal M}\subset V$, a function in ${\mathrm{Lip}}(\gamma,{\cal M},W)$
is defined only through its values at the points in ${\cal M}$. No knowledge
of its behaviour outside ${\cal M}$ is required; we do not need to even define
their value at _any_ point in the complement $V\setminus{\cal M}\subset V$ of
${\cal M}$.

Further, any function in ${\mathrm{Lip}}(\gamma,{\cal M},W)$ admits an
extension to the entirety of $V$ possessing the same regularity. That is, if
$\psi\in{\mathrm{Lip}}(\gamma,{\cal M},W)$ then there exists
$\Psi\in{\mathrm{Lip}}(\gamma,V,W)$ with $\Psi\equiv\psi$ throughout ${\cal
M}$. When $V={\mathbb{R}}^{d}$ and $W={\mathbb{R}}$ this is a consequence of
the Stein-Whitney extension theorem presented as Theorem 4 in Chapter VI of
[Ste70]. Often referred to as the Stein extension theorem, we include Whitney
to reflect the reliance of Stein’s proof on the machinery introduced by
Whitney in his own extension theorems in [Whi34, Whi44]. Since $V$ is finite
dimensional, a verbatim repetition of the argument presented in [Ste70]
establishes the extension result we claim above. Modulo defining a
${\mathrm{Lip}}(\gamma)$-norm (cf. Definition 2.2), it follows that the
resulting extension operator ${\mathrm{Lip}}(\gamma,{\cal
M},W)\to{\mathrm{Lip}}(\gamma,V,W)$ is a bounded linear operator.

This extension property ensures that ${\mathrm{Lip}}(\gamma)$ functions are
well-suited for inference on unseen data. That is, suppose we know that
$\psi\in{\mathrm{Lip}}(\gamma,\Sigma,W)$ well-approximates a system on a
finite subset $\Sigma\subset V$. Then, given an unseen point $p\in
V\setminus\Sigma$, we can extend $\psi$ to $\Psi\in{\mathrm{Lip}}(\gamma,V,W)$
and use the evaluation of the extension $\Psi$ at $p$ for the purpose of
inferring the systems response to the unseen input $p$. Moreover, if we know
that the underlying system satisfies some global ${\mathrm{Lip}}(\gamma)$
regularity, then we can quantify how well $\Psi$ approximates the system at
$p$ in terms of how well $\psi$ approximates the system on $\Sigma$ and the
$V$-distance from the point $p$ to the subset $\Sigma$ (cf. Remark 10.8).

With our choice of ${\mathrm{Lip}}(\gamma)$ regularity fixed, we turn our
attention to considering the Banach GRIM algorithm from [LM22-I] in the case
that $X={\mathrm{Lip}}(\gamma,\Sigma,W)$ for a finite subset $\Sigma\subset
V$. For this purpose we develop the _Higher Order Lipschitz Greedy
Recombination Interpolation Method_ (HOLGRIM) as a modification of the GRIM
tailored to the setting that $X:={\mathrm{Lip}}(\gamma,\Sigma,W)$. In
particular, the HOLGRIM algorithm, detailed in Section 6, is designed to seek
a sparse approximation of a given linear combination $\varphi$ of
${\mathrm{Lip}}(\gamma,\Sigma,W)$ functions. For a fixed choice of
$q\in\\{0,\ldots,k\\}$, The approximation is required to be close to $\varphi$
throughout $\Sigma$ in an “order $q$” pointwise sense; this is made precise in
Section 6, and is analogous to requiring the derivatives up to order $q$ or
the approximation to be close to the derivatives up to order $q$ of $\varphi$
at every point in $\Sigma$.

The HOLGRIM algorithm dynamically grows a subset $P\subset\Sigma$ of the data
at which we require approximations of the target $\varphi$ to coincide with
$\varphi$. As in the case of the Banach GRIM algorithm in [LM22-I], after each
extension of the subset $P$, the thinning or recombination is used to find an
approximation $u\in\operatorname{Span}({\cal F})$ coinciding with $\varphi$
throughout $P$. This is achieved via an application of the _Recombination
Thinning Lemma 3.1_ from [LM22-I] (cf. the HOLGRIM Recombination Step in
Section 6).

The applicability of the _Recombination Thinning Lemma 3.1_ from [LM22-I] to
find such an approximation of $\varphi$ is a consequence of the following
correspondence established in Section 5. Given a point $p\in\Sigma$ there is a
subset ${\cal T}_{p,k}\subset{\mathrm{Lip}}(\gamma,\Sigma,W)^{\ast}$ of
bounded linear functionals ${\mathrm{Lip}}(\gamma,\Sigma,W)\to{\mathbb{R}}$
such that the value of any $\psi\in{\mathrm{Lip}}(\gamma,\Sigma,W)$ at the
point $p$ _is_ determined by the set of real numbers
$\\{\sigma(\psi):\sigma\in{\cal T}_{p,k}\\}\subset{\mathbb{R}}$. The set
${\cal T}_{p,k}$ is defined carefully in Section 5, and a quantified estimate
regarding the sense in which the value set $\\{\sigma(\psi):\sigma\in{\cal
T}_{p,k}\\}\subset{\mathbb{R}}$ determines the value of $\psi$ at $p$ is
provided by Lemmas 5.4 and 5.5. This observation allows us to associate the
finite collection of bounded linear functionals
$\Sigma^{\ast}_{k}:=\cup_{p\in\Sigma}{\cal T}_{p,k}$ to the finite subset of
data $\Sigma\subset V$.

Both the dynamic growth of the subset $P\subset\Sigma$, governed by the
HOLGRIM Extension Step detailed in Section 6, and the use of recombination to
obtain an approximation coinciding with $\varphi$ throughout $P$, detailed in
the HOLGRIM Recombination Step in Section 6, are reliant on the correspondence
established in Section 5. Indeed, the dynamic growth detailed in the HOLGRIM
Extension Step in Section 6 is done in a similar spirit to the Modified
Extension Step appearing in Section 7 of [LM22-I].

Heuristically, to grow the subset $P$ we find the linear functional
$\sigma\in\Sigma^{\ast}_{k}$ returning the largest absolute value when applied
to the difference between $\varphi$ and the current approximation, and then
extend $P$ by addition of the point $p\in\Sigma$ for which $\sigma\in{\cal
T}_{p,k}$. In the HOLGRIM Extension Step in Section 6 we allow for the
extension of $P$ by more than a single new point and we only consider a
particular subset of the linear functionals $\Sigma_{k}^{\ast}$ determined by
the strength of approximation we seek (cf. the HOLGRIM Extension Step in
Section 6). The number of new points to be added at each step gives a
parameter that may be optimised.

After each extension of the subset $P$ we apply the _Recombination Thinning
Lemma 3.1_ from [LM22-I] to the collection of linear functionals
$L:=\cup_{p\in P}{\cal T}_{p,k}$ to find a new approximation that coincides
with $\varphi$ throughout $P$; see the HOLGRIM Recombination Step in Section 6
for full details. As in [LM22-I], we optimise our use of recombination over
multiple permutations of the ordering of the equations determining the linear
system to which recombination is applied (cf. the HOLGRIM Recombination Step
in Section 6). The number of permutations to be considered at each step gives
a parameter that may be optimised.

HOLGRIM inherits the same data-driven benefits enjoyed by GRIM. The growth in
HOLGRIM is data-driven rather than feature-driven. The extension of the data
to be interpolated with respect to in HOLGRIM does not involve making any
choices of features from ${\cal F}$. The new information to be matched is
determined by examining where in $\Sigma$ the current approximation is
furthest from the target $\varphi$ (cf. Section 6). Only a subset
$P\subset\Sigma$ of data is dynamically grown; there is no corresponding
subset $F\subset{\cal F}$ of functions that is dynamically grown. The
functions that an approximation will be a linear combination of are _not_
predetermined; they are determined by recombination (cf. the HOLGRIM
Recombination Step in Section 6). Besides an upper bound on the number of
functions used to construct an approximation at a given step (cf. Section 6),
we have no control over the functions used. Moreover, as is the case for GRIM,
there is no requirement that any of the functions used at a specific step must
be used in any of the subsequent steps.

The HOLGRIM algorithm detailed in Section 6 is designed to approximate a given
linear combination of ${\mathrm{Lip}}(\gamma,\Sigma,W)$ functions when
$\Sigma\subset V$ is a finite subset. However, a consequence of the _Lipschitz
Sandwich Theorems_ established in [LM24] is that a ${\mathrm{Lip}}(\gamma)$
function defined throughout a compact subset can be well-approximated
throughout the compact subset provided one can well-approximate the
${\mathrm{Lip}}(\gamma)$ function on a particular finite subset. (cf. Section
4 in [LM24]). In Section 4 of this paper we outline how this observation
enables the case of compact domains to be tackled via the case of finite
domains that the HOLGRIM algorithm is designed to solve. Moreover, we
additionally illustrate in Section 4 how the _Lipschitz Sandwich Theorem 3.1_
in [LM24] can be used to strengthen the pointwise closeness of an
approximation $u$ to $\varphi$ to an estimate on the ${\mathrm{Lip}}(\eta)$
norm of the difference $\varphi-u$ for a fixed $\eta\in(0,\gamma)$.

The complexity cost of the HOLGRIM algorithm is analysed in Section 7. The
HOLGRIM algorithm is designed to be a one-time tool that is applied a single
time to find a sparse approximation of the target $\varphi$. Repeated use of
the returned approximation, which will be more cost-effectively computed than
the original target $\varphi$, for inference on new inputs will recover the
up-front cost of the HOLGRIM algorithms implementation. Models, such as
recognition models or classification models, that will be repeatedly computed
on new inputs for the purpose of inference or prediction are ideal candidates
for HOLGRIM to approximate.

Consequently, the primary aim of our complexity cost considerations in Section
7 is to verify that implementing the HOLGRIM algorithm is feasible. This is
verified by proving that, at worst, the complexity cost of running the HOLGRIM
algorithm is

${\cal O}\left(scD(d,k)M{\cal N}\Lambda+sc^{2}D(d,k)^{2}M{\cal
N}\Lambda^{2}+sc^{3}D(d,k)^{3}M\log\left(\frac{{\cal
N}}{cD(d,k)}\right)\Lambda^{3}\right)$ (1.2)

where ${\cal N}$ is the number of functions in ${\cal F}$, $\Lambda$ is the
number of points in $\Sigma$, $M$ is the maximum number of steps for which the
HOLGRIM algorithm will be run, $s$ is the maximum number of shuffles
considered during each application of recombination, $c$ is the dimension of
$W$, $d$ is the dimension of $V$, $k\in{\mathbb{Z}}_{\geq 0}$ is the integer
for which $\gamma\in(k,k+1]$, and $D=D(d,k)$ is an integer that depends only
on $d$ and $k$ and whose precise definition may be found in (5.2) in Section
5. The upper bound on the complexity cost stated in (1.2) is a consequence of
the complexity cost bounds established in Lemma 7.3 in Section 7.

Performance guarantees for the HOLGRIM algorithm are considered in Sections 8,
9, and 10. The approach adopted in [LM22-I] leads to guarantees in terms of
specific geometric properties of the linear functionals
$\Sigma_{k}^{\ast}\subset{\mathrm{Lip}}(\gamma,\Sigma,W)$ (cf. Section 8). In
order to obtain guarantees involving the geometry of the data $\Sigma$ itself,
we utilise the _Lipschitz Sandwich Theorems_ established in [LM24].

Theoretical guarantees in terms of a particular packing number of $\Sigma$ in
$V$ are established for the HOLGRIM algorithm in which a single new point is
chosen at each step in the _HOLGRIM Convergence Theorem_ 10.1. Packing
numbers, and the closely related notion of covering numbers, were first
considered by Kolmogorov [Kol56], and have subsequently arisen in contexts
including eigenvalue estimation [Car81, CS90, ET96], Gaussian Processes [LL99,
LP04], and machine learning [EPP00, SSW01, Zho02, Ste03, SS07, Kuh11, MRT12,
FS21]. The main technical result underpinning the _HOLGRIM Convergence
Theorem_ 10.1 is the _HOLGRIM Point Separation Lemma_ 9.1 which establishes
that points chosen during the HOLGRIM algorithm are a definite $V$ distance
apart.

The paper is structured as follows. In Section 2 we rigorously define the
notion of a ${\mathrm{Lip}}(\gamma,{\cal M},W)$ function for an arbitrary
closed subset ${\cal M}\subset V$, and additionally record variants of the
particular _Lipschitz Sandwich Theorems_ from [LM24] that will be used within
this article.

In Section 3 we rigorously formulate the sparse approximation problem that the
HOLGRIM algorithm is designed to tackle.

In Section 4 we outline how being able to solve the sparse approximation
problem detailed in Section 3 for a finite subset $\Sigma\subset V$ enables
one to solve the same sparse approximation problem for a compact subset
$\Omega\subset V$. Both a strategy utilising the _Pointwise Lipschitz Sandwich
Theorem 3.11_ of [LM24] (cf. Theorem 2.10 in this paper) to obtain a pointwise
approximation throughout $\Omega$ and a strategy utilising the _Lipschitz
Sandwich Theorem 3.1_ of [LM24] (cf. Theorem 2.9 in this paper) to obtain, for
a fixed $\eta\in(0,\gamma)$, a ${\mathrm{Lip}}(\eta,\Omega,W)$-norm
approximation throughout $\Omega$ are covered.

In Section 5, given an arbitrary closed subset ${\cal M}\subset V$ and a point
$z\in{\cal M}$, we define a finite subset ${\cal
T}_{z,k}\subset{\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$ of the dual-space
${\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$ of bounded linear functionals
${\mathrm{Lip}}(\gamma,{\cal M},W)\to{\mathbb{R}}$ such that for any
$\psi\in{\mathrm{Lip}}(\gamma,{\cal M},W)$ the value of $\psi$ at $z$ is
determined by the values $\sigma(\psi)$ for the linear functionals
$\sigma\in{\cal T}_{z,k}$ (cf. Lemma 5.5).

In Section 6 we present and discuss the HOLGRIM algorithm. We formulate both
the HOLGRIM Extension Step governing how we extend an existing collection of
points $P\subset\Sigma$ and the HOLGRIM Recombination Step governing the
_Recombination Thinning Lemma 3.1_ in [LM22-I] is used in the HOLGRIM
algorithm. Additionally, we establish an upper bound on the number of
functions used to construct the approximation at each step of the HOLGRIM
algorithm.

In Section 7 we analyse the complexity cost of the HOLGRIM algorithm. We prove
Lemma 7.3 establishing the complexity cost of any implementation of the
HOLGRIM algorithm. We further record an upper bound for the complexity cost of
the most expensive implementation.

In Section 8 we discuss both the performance guarantees inherited by the
HOLGRIM algorithm from the _Banach GRIM Convergence Theorem 6.2_ in [LM22-I]
and the limitations/issues of the results obtained via this approach.

In Section 9 we prove the _HOLGRIM Point Separation Lemma_ 9.1 establishing
that the points selected during the HOLGRIM algorithm in which a single new
point is chosen at each step are guaranteed to be a definite $V$-distance
apart from one and other.

In Section 10 we prove the _HOLGRIM Convergence Theorem_ 10.1. This result
establishes that a particular packing number of the data $\Sigma$ in $V$
provides an upper bound for the maximum number of steps that the HOLGRIM
algorithm can complete before an approximation of $\varphi$ possessing the
desired level of accuracy is returned. We subsequently discuss the
consequences of the _HOLGRIM Convergence Theorem_ 10.1. We convert the
assertions of the _HOLGRIM Convergence Theorem_ 10.1 into a reversed
implication establishing how well the HOLGRIM algorithm can approximate
$\varphi$ under a restriction on the maximum number of functions that can be
used to construct the approximation (cf. Remark 10.4). We verify that the data
concentration required to guarantee that the HOLGRIM algorithm returns a good
approximation of $\varphi$ using strictly less than ${\cal N}$ of the
functions in ${\cal F}$ decreases as the regularity parameter $\gamma>0$
increases (cf. Remark 10.7). We establish a robustness property satisfied by
the returned approximation (cf. Remark 10.8). We show that the guarantees of
Theorem 10.1 can be both extended to the setting of a compact subset
$\Omega\subset V$ and have the conclusion strengthened to, for a given
$\eta\in(0,\gamma)$, a ${\mathrm{Lip}}(\eta)$-norm estimates on the difference
between the target $\varphi$ and the returned approximation $u$ following the
strategies outlined in Section 4 (cf. Remarks 10.9, 10.10, 10.11, and 10.12).
Finally we illustrate a number of these consequences of the _HOLGRIM
Convergence Theorem_ 10.1 via an explicit example in the Euclidean setting
$\Omega:=[0,1]^{d}\subset{\mathbb{R}}^{d}$ (cf. Remark 10.13).
_Acknowledgements_ : This work was supported by the DataSıg Program under the
EPSRC grant ES/S026347/1, the Alan Turing Institute under the EPSRC grant
EP/N510129/1, the Data Centric Engineering Programme (under Lloyd’s Register
Foundation grant G0095), the Defence and Security Programme (funded by the UK
Government) and the Hong Kong Innovation and Technology Commission (InnoHK
Project CIMDA). This work was funded by the Defence and Security Programme
(funded by the UK Government).

##  2 Lipschitz Functions and Sandwich Theorems

In this section we provide a rigorous definition of a ${\mathrm{Lip}}(\gamma)$
function in the sense of Stein [Ste70] in the same generality considered in
[LM24]. Additionally, we record the particular _Lipschitz Sandwich Theorems_
from [LM24] that will be useful within this article.

Let $V$ and $W$ be real Banach spaces and assume that ${\cal M}\subset V$ is a
closed subset. Throughout this article we adopt the convention that balls
denoted by ${\mathbb{B}}$ are taken to be open, whilst those denoted by
${\overline{\mathbb{B}}}$ are taken to be closed. To define
${\mathrm{Lip}}(\gamma,{\cal M},W)$ functions, we must first make a choice of
norm on the tensor powers of $V$. We restrict to considering norms that are
_admissible_ in the following sense.

######  Definition 2.1 (Admissible Norms on Tensor Powers).

Let $V$ be a Banach space. We say that its tensor powers are endowed with
admissible norms if for each $n\in{\mathbb{Z}}_{\geq 2}$ we have equipped the
tensor power $V^{\otimes n}$ of $V$ with a norm $||\cdot||_{V^{\otimes n}}$
such that the following conditions hold.

  * •

For each $n\in{\mathbb{Z}}_{\geq 2}$ the symmetric group $S_{n}$ acts
isometrically on $V^{\otimes n}$, i.e. for any $\rho\in S_{n}$ and any $v\in
V^{\otimes n}$ we have

$||\rho(v)||_{V^{\otimes n}}=||v||_{V^{\otimes n}}.$ (2.1)

The action of $S_{n}$ on $V^{\otimes n}$ is given by permuting the order of
the letters, i.e. if $a_{1}\otimes\ldots\otimes a_{n}\in V^{\otimes n}$ and
$\rho\in S_{n}$ then $\rho(a_{1}\otimes\ldots\otimes
a_{n}):=a_{\rho(1)}\otimes\ldots\otimes a_{\rho(n)}$, and the action is
extended to the entirety of $V^{\otimes n}$ by linearity.

  * •

For any $n,m\in{\mathbb{Z}}_{\geq 1}$ and any $v\in V^{\otimes n}$ and $w\in
V^{\otimes m}$ we have

$||v\otimes w||_{V^{\otimes(n+m)}}\leq||v||_{V^{\otimes n}}||w||_{V^{\otimes
m}}.$ (2.2)

  * •

For any $n,m\in{\mathbb{Z}}_{\geq 1}$ and any $\phi\in\left(V^{\otimes
n}\right)^{\ast}$ and $\sigma\in\left(V^{\otimes m}\right)^{\ast}$ we have

$||\phi\otimes\sigma||_{\left(V^{\otimes(n+m)}\right)^{\ast}}\leq||\phi||_{\left(V^{\otimes
n}\right)^{\ast}}||\sigma||_{\left(V^{\otimes m}\right)^{\ast}}.$ (2.3)

Here, given any $k\in{\mathbb{Z}}_{\geq 1}$, the norm
$||\cdot||_{\left(V^{\otimes k}\right)^{\ast}}$ denotes the dual-norm induced
by $||\cdot||_{V^{\otimes k}}$.

A consequence of having _both_ the inequalities (2.2) and (2.3) being
satisfied is that we may conclude that there is actually equality in both
estimates (see [Rya02]). Thus if the tensor powers of $V$ are all equipped
with admissible tensor norms in the sense of Definition 2.1, we have equality
in both (2.2) and (2.3).

We next use this notion of admissible tensor norm to rigorously define a
${\mathrm{Lip}}(\gamma,{\cal M},W)$ function within this setting (cf.
Definition 2.2 in [LM24]).

######  Definition 2.2 (${\mathrm{Lip}}(\gamma,{\cal M},W)$ functions).

Let $V$ and $W$ be Banach spaces, ${\cal M}\subset V$ a closed subset, and
assume that the tensor powers of $V$ are all equipped with admissible norms.
Let $\gamma>0$ with $k\in{\mathbb{Z}}_{\geq 0}$ such that $\gamma\in(k,k+1]$.
Then let $\psi=(\psi^{(0)},\psi^{(1)},\ldots,\psi^{(k)})$ where
$\psi^{(0)}:{\cal M}\to W$ is a function taking its values in $W$ and, for
each $l\in\\{1,\ldots,k\\}$, $\psi^{(l)}:{\cal M}\to{\cal L}(V^{\otimes l};W)$
is a functions taking its values in the space of symmetric $l$-linear forms
from $V$ to $W$. Then $\psi$ is a ${\mathrm{Lip}}(\gamma,{\cal M},W)$ function
if there exists a constant $M\geq 0$ for which the following is true.

  * •

For each $l\in\\{0,\ldots,k\\}$ and every $z\in{\cal M}$ we have that

$||\psi^{(l)}(z)||_{{\cal L}(V^{\otimes l};W)}\leq M$ (2.4)

  * •

For each $j\in\\{0,\ldots,k\\}$ define $R^{\psi}_{j}:{\cal M}\times{\cal
M}\to{\cal L}(V^{\otimes j};W)$ for $z,p\in{\cal M}$ and $v\in V^{\otimes j}$
by

$R^{\psi}_{j}(z,p)[v]:=\psi^{(j)}(p)[v]-\sum_{s=0}^{k-j}\frac{1}{s!}\psi^{(j+s)}(z)\left[v\otimes(p-z)^{\otimes
s}\right].$ (2.5)

Then whenever $l\in\\{0,\ldots,k\\}$ and $x,y\in{\cal M}$ we have

$\left|\left|R^{\psi}_{l}(x,y)\right|\right|_{{\cal L}(V^{\otimes l};W)}\leq
M||y-x||_{V}^{\gamma-l}.$ (2.6)

We sometimes say that $\psi\in{\mathrm{Lip}}(\gamma,{\cal M},W)$ without
explicitly mentioning the functions $\psi^{(0)},\ldots,\psi^{(k)}$.
Furthermore, given $l\in\\{0,\ldots,k\\}$, we introduce the notation that
$\psi_{[l]}:=(\psi^{(0)},\ldots,\psi^{(l)})$. The ${\mathrm{Lip}}(\gamma,{\cal
M},W)$ norm of $\psi$, denoted by $||\psi||_{{\mathrm{Lip}}(\gamma,{\cal
M},W)}$, is the smallest $M\geq 0$ satisfying the requirements (2.4) and
(2.6).

######  Remark 2.3.

Assuming the same notation as in Definition 2.2, we adopt the same convention
as used in [LM24] regarding the choice of norm on the space ${\cal
L}(V^{\otimes l};W)$ for each $l\in\\{0,\ldots,W\\}$. That is, recall that
$V^{\otimes 0}:={\mathbb{R}}$ so that ${\cal L}(V^{\otimes 0};W)=W$. Hence we
take $||\cdot||_{{\cal L}(V^{\otimes 0};W)}$ to be the norm $||\cdot||_{W}$
given on $W$. Further, given $l\in\\{1,\ldots,k\\}$, we equip ${\cal
L}(V^{\otimes l};W)$ with its operator norm determined by

$||{\bf A}||_{{\cal L}(V^{\otimes l};W)}:=\sup\left\\{\left|\left|{\bf
A}[v]\right|\right|_{W}~{}:~{}v\in V^{\otimes l}\text{ and }||v||_{V^{\otimes
l}}=1\right\\}.$ (2.7)

This results in the same notion of a ${\mathrm{Lip}}(\gamma,{\cal M},W)$
function as considered in [LM24]. Consequently, it is the case that an upper
bound on the resulting ${\mathrm{Lip}}(\gamma)$-norm
$||\cdot||_{{\mathrm{Lip}}(\gamma,{\cal M},W)}$ is a stronger restriction than
the same upper bound on the corresponding notion of
${\mathrm{Lip}}(\gamma)$-norm considered in the works [Bou15, Bou22, BL22].

######  Remark 2.4.

Assuming the same notation as in Definition 2.2, suppose
$\psi=\left(\psi^{(0)},\ldots,\psi^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal
M},W)$. Let $C^{0}({\cal M};W)$ denote the space of continuous maps ${\cal
M}\to W$ and for $f\in C^{0}({\cal M};W)$ take $||f||_{C^{0}({\cal
M};W)}:=\sup\left\\{||f(x)||_{W}:x\in{\cal M}\right\\}$. Then $\psi^{(0)}\in
C^{0}({\cal M};W)$ and $||\psi^{(0)}||_{C^{0}({\cal
M};W)}\leq||\psi||_{{\mathrm{Lip}}(\gamma,{\cal M},W)}$. Consequently, the
mapping $\psi\mapsto\psi^{(0)}$ gives an embedding of
${\mathrm{Lip}}(\gamma,{\cal M},W)$ into the space $C^{0}({\cal M};W)$.

######  Remark 2.5.

Assuming the same notation as in Definition 2.2, suppose
$\psi=\left(\psi^{(0)},\ldots,\psi^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal
M},W)$, and that $\eta\in(0,\gamma)$ with $q\in{\mathbb{Z}}_{\geq 0}$ such
that $\eta\in(q,q+1]$. Then it follows that
$\psi_{[q]}=\left(\psi^{(0)},\ldots,\psi^{(q)}\right)\in{\mathrm{Lip}}(\eta,{\cal
M},W)$ and there exists a constant $C=C(\gamma,\eta)\geq 1$ for which
$||\psi_{[q]}||_{{\mathrm{Lip}}(\eta,{\cal M},W)}\leq
C||\psi||_{{\mathrm{Lip}}(\gamma,{\cal M},W)}$; see, for example, Lemma 6.1 in
[LM24]. Consequently, the mapping $\psi\mapsto\psi_{[q]}$ gives an embedding
of ${\mathrm{Lip}}(\gamma,{\cal M},W)$ into the space
${\mathrm{Lip}}(\eta,{\cal M},W)$.

######  Remark 2.6.

Suppose that $O\subset V$ is open and that
$\psi=\left(\psi^{(0)},\ldots,\psi^{(k)}\right)\in{\mathrm{Lip}}(\gamma,O,W)$.
Then the expansions (2.5) and the estimates (2.4) and (2.6) yield that
$\psi^{(0)}:O\to W$ is $k$-times Fréchet differentiable with, for
$l\in\\{0,\ldots,k\\}$, $l^{\text{th}}$ Fréchet derivative given by
$\psi^{(l)}$. Hence the $k^{\text{th}}$ Fréchet derivative of $\psi^{(0)}$ is
$(\gamma-k)$-Hölder continuous so that $\psi^{(0)}\in C^{k,\gamma-k}(O;W)$.
Consequently, the mapping $\psi\mapsto\psi^{(0)}$ gives an embedding of
${\mathrm{Lip}}(\gamma,O,W)$ into the space $C^{k,\gamma-k}(O;W)$. Moreover,
Taylor’s theorem establishes that this mapping is in fact a one-to-one
correspondence.

######  Remark 2.7.

A helpful way to think about ${\mathrm{Lip}}(\gamma,{\cal M},W)$ functions is
that they “locally looks like a polynomial function”. To elaborate, assume the
same notation as in Definition 2.2 and let
$\psi=\left(\psi^{(0)},\ldots,\psi^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal
M},W)$. For each point $x\in{\cal M}$ we can define a polynomial
$\Psi_{x}:V\to W$ for $v\in V$ by

$\Psi_{x}(v):=\sum_{s=0}^{k}\frac{1}{s!}\psi^{(s)}(x)\left[(v-x)^{\otimes
s}\right].$ (2.8)

For each $l\in\\{0,\ldots,k\\}$ and any point $x\in{\cal M}$ the element
$\psi^{(l)}(x)\in{\cal L}(V^{\otimes l};W)$ is the $l^{\text{th}}$ Fréchet
derivative of the polynomial $\Psi_{x}$ evaluated at the point $x\in{\cal M}$.
Moreover, the polynomial $\Psi_{x}$ provides a proposal, based at the point
$x\in{\cal M}$, for how $\psi^{(0)}$ could be extended to the entirety of $V$.
The expansions (2.5) and the estimates (2.6) ensure that for points $y\in{\cal
M}$ that are close, in the $||\cdot||_{V}$ norm sense, to $x$ that the values
$\psi^{(0)}(y)$ and $\Psi_{x}(y)$ must be close in a quantifiable
$||\cdot||_{W}$ sense. In fact, (2.5) and (2.6) ensure that if
$x_{1},x_{2}\in{\cal M}$ are close in the $||\cdot||_{V}$ sense, then the
polynomial proposals $\Psi_{x_{1}}$ and $\Psi_{x_{2}}$ must be close as
functions $V\to W$ in a pointwise sense. A precise estimate giving
quantifiable meaning to the notion of closeness can be found in Section 2 of
[LM24].

######  Remark 2.8.

Assuming the same notation as in Definition 2.2, and suppose
$\psi=\left(\psi^{(0)},\ldots,\psi^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal
M},W)$. To ease notation, given $l\in\\{0,\ldots,k\\}$ we define
$\Lambda_{\psi}^{l}:{\cal M}\to{\mathbb{R}}_{\geq 0}$ by setting, for
$x\in{\cal M}$,

$\Lambda^{l}_{\psi}(x):=\max_{j\in\\{0,\ldots,l\\}}\left|\left|\psi^{(j)}(x)\right|\right|_{{\cal
L}(V^{\otimes j};W)}.$ (2.9)

A consequence of (2.9) is that for any $l\in\\{0,\ldots,k\\}$ and any
$z\in{\cal M}$ we have that
$\Lambda^{l}_{\psi}(z)\leq||\psi||_{{\mathrm{Lip}}(\gamma,{\cal A},W)}$ for
any subset ${\cal A}\subset{\cal M}$ with $z\in{\cal A}$.

We end this subsection by stating the various _Lipschitz Sandwich Theorems_
from [LM24] that we will use in this article. We first record a variant of the
_Lipschitz Sandwich Theorem_ 3.1 in [LM24] in which both the constants $K_{1}$
and $K_{2}$ of that result are equal to the same constant $K_{0}>0$.

######  Theorem 2.9 (Lipschitz Sandwich Theorem 3.1 in [LM24]).

Let $V$ and $W$ be Banach spaces, and assume that the tensor powers of $V$ are
all equipped with admissible norms (cf. Definition 2.1). Assume that ${\cal
M}\subset V$ is non-empty and closed. Let $\varepsilon,K_{0}>0$, and
$\gamma>\eta>0$ with $k,q\in{\mathbb{Z}}_{\geq 0}$ such that
$\gamma\in(k,k+1]$ and $\eta\in(q,q+1]$. Then there exist constants
$\delta_{0}=\delta_{0}(\varepsilon,K_{0},\gamma,\eta)>0$ and
$\varepsilon_{0}=\varepsilon_{0}(\varepsilon,K_{0},\gamma,\eta)>0$ for which
the following is true.

Suppose $B\subset{\cal M}$ is a closed subset that is a $\delta_{0}$-cover of
${\cal M}$ in the sense that

${\cal M}\subset\bigcup_{x\in
B}{\overline{\mathbb{B}}}_{V}(x,\delta_{0})=B_{\delta_{0}}:=\left\\{v\in
V~{}:~{}\text{There exists }z\in B\text{ such that
}||v-z||_{V}\leq\delta_{0}\right\\}.$ (2.10)

Suppose
$\psi=\left(\psi^{(0)},\ldots,\psi^{(k)}\right),\phi=\left(\phi^{(0)},\ldots,\phi^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal
M},W)$ with $||\psi||_{{\mathrm{Lip}}(\gamma,{\cal
M},W)},||\phi||_{{\mathrm{Lip}}(\gamma,{\cal M},W)}\leq K_{0}$. Then, if
$\psi_{[q]}:=\left(\psi^{(0)},\ldots,\psi^{(q)}\right)$ and
$\psi_{[q]}:=\left(\phi^{(0)},\ldots,\phi^{(q)}\right)$, we have that

$\sup_{z\in
B}\Lambda^{k}_{\psi-\phi}(z)\leq\varepsilon_{0}\qquad\implies\qquad\left|\left|\psi_{[q]}-\phi_{[q]}\right|\right|_{{\mathrm{Lip}}(\eta,{\cal
M},W)}\leq\varepsilon.$ (2.11)

The following result records a variant of the _Pointwise Lipschitz Sandwich
Theorem_ 3.11 in [LM24] in which both the constants $K_{1}$ and $K_{2}$ of
that result are equal to the same constant $K_{0}>0$.

######  Theorem 2.10 (Pointwise Lipschitz Sandwich Theorem 3.11 in [LM24]).

Let $V$ and $W$ be Banach spaces, and assume that the tensor powers of $V$ are
all equipped with admissible norms (cf. Definition 2.1). Assume that ${\cal
M}\subset V$ is closed. Let $K_{0},\gamma,\varepsilon>0$ with
$k\in{\mathbb{Z}}_{\geq 0}$ such that $\gamma\in(k,k+1]$ and
$0\leq\varepsilon_{0}<\varepsilon\leq K_{0}$. Then given any
$l\in\\{0,\ldots,k\\}$, there exists a constant
$\delta_{0}=\delta_{0}(\varepsilon,\varepsilon_{0},K_{0},\gamma,l)>0$, defined
by

$\delta_{0}:=\sup\left\\{\theta>0~{}:~{}2K_{0}\theta^{\gamma-l}+\varepsilon_{0}e^{\theta}\leq\varepsilon\right\\}\in(0,1]$
(2.12)

for which the following is true.

Suppose $B\subset{\cal M}$ is a $\delta_{0}$-cover of ${\cal M}$ in the sense
that

${\cal M}\subset\bigcup_{x\in
B}{\overline{\mathbb{B}}}_{V}(x,\delta_{0})=B_{\delta_{0}}:=\left\\{v\in
V~{}:~{}\text{There exists }z\in B\text{ such that
}||v-z||_{V}\leq\delta_{0}\right\\}.$ (2.13)

Suppose
$\psi=\left(\psi^{(0)},\ldots,\psi^{(k)}\right),\phi=\left(\psi^{(0)},\ldots,\phi^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal
M},W)$ with $||\psi||_{{\mathrm{Lip}}(\gamma,{\cal
M},W)},||\phi||_{{\mathrm{Lip}}(\gamma,{\cal M},W)}\leq K_{0}$. Then we have
that

$\sup_{z\in
B}\Lambda^{k}_{\psi-\phi}(z)\leq\varepsilon_{0}\qquad\implies\qquad\sup_{z\in{\cal
M}}\Lambda^{l}_{\psi-\phi}(z)\leq\varepsilon.$ (2.14)

We end this subsection by recording the following explicit estimates pointwise
estimates for $\psi\in{\mathrm{Lip}}(\gamma,{\cal M},W)$ under the assumption
that, at a point $p\in{\cal M}$, we have
$\Lambda^{k}_{\psi}(p)\leq\varepsilon_{0}$. These estimates are contained in
the _Pointwise Estimates Lemma_ 7.1 in [LM24] under the choices of the
$\Gamma$, $F$, $A$, $r_{0}$, $\rho$, and $q$ in that result as ${\cal M}$,
$\psi$, $K_{0}$, $\varepsilon_{0}$, $\gamma$, and $k$ here. The precise result
is the following lemma.

######  Lemma 2.11 (Variant of Pointwise Estimates Lemma 7.1 in [LM24]).

Let $V$ and $W$ be Banach spaces, and assume that the tensor powers of $V$ are
all equipped with admissible norms (cf. Definition 2.1). Assume ${\cal
M}\subset V$ is closed with $p\in{\cal M}$. Let $K_{0},\gamma>0$,
$\varepsilon_{0}\geq 0$, and $k\in{\mathbb{Z}}_{\geq 0}$ such that
$\gamma\in(k,k+1]$. Let
$\psi=\left(\psi^{(0)},\ldots,\psi^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal
M},W)$ with $||\psi||_{{\mathrm{Lip}}(\gamma,{\cal M},W)}\leq K_{0}$. Then if
$\Lambda^{k}_{\psi}(p)\leq\varepsilon_{0}$ we may conclude, for any $z\in{\cal
M}$ and any $l\in\\{0,\ldots,k\\}$, that

$\left|\left|\psi^{(l)}(z)\right|\right|_{{\cal L}(V^{\otimes
l};W)}\leq\min\left\\{K_{0}~{},~{}K_{0}||z-p||_{V}^{\gamma-l}+\varepsilon_{0}\sum_{j=0}^{k-l}\frac{1}{j!}||z-p||_{V}^{j}\right\\}.$
(2.15)

##  3 Sparse Approximation Problem Formulation

In this section we rigorously formulate the sparse approximation problem that
the HOLGRIM algorithm will be designed to tackle. For this purpose we again
let $V$ and $W$ be real Banach spaces, but we now additionally impose that
both $V$ and $W$ are finite dimensional. In particular, we assume that $V$ has
dimension $d\in{\mathbb{Z}}_{\geq 1}$, and that $W$ has dimension
$c\in{\mathbb{Z}}_{\geq 1}$. Whilst we do not do so in this article, one could
work modulo isometric isomorphism and assume that $V={\mathbb{R}}^{d}$ and
$W={\mathbb{R}}^{c}$. Instead, we work directly with $V$ and $W$ and assume
that the tensor powers of $V$ are all equipped with admissible tensor norms in
the sense of Definition 2.1.

We now formulate the sparse approximation problem that we consider in this
article. Let $\gamma>0$ with $k\in{\mathbb{Z}}_{\geq 0}$ such that
$\gamma\in(k,k+1]$. Let ${\cal N},\Lambda\in{\mathbb{Z}}_{\geq 1}$ be (large)
positive integers. Let $\Sigma\subset V$ be a finite subset of cardinality
$\Lambda$. For every $i\in\\{1,\ldots,{\cal N}\\}$ we assume that
$f_{i}=\left(f_{i}^{(0)},\ldots,f^{(k)}_{i}\right)\in{\mathrm{Lip}}(\gamma,\Sigma,W)$
is non-zero, and set ${\cal F}:=\left\\{f_{i}:~{}i\in\\{1,\ldots,{\cal
N}\\}\right\\}\subset{\mathrm{Lip}}(\gamma,\Sigma,W)$. Fix a choice of scalars
$A_{1},\ldots,A_{{\cal N}}\in{\mathbb{R}}_{>0}$ such that, for every
$i\in\\{1,\ldots,{\cal N}\\}$, we have
$||f_{i}||_{{\mathrm{Lip}}(\gamma,\Sigma,W)}\leq A_{i}$. Fix a choice of non-
zero coefficients $a_{1},\ldots,a_{{\cal N}}\in{\mathbb{R}}\setminus\\{0\\}$
and consider
$\varphi=\left(\varphi^{(0)},\ldots,\varphi^{(k)}\right)\in{\mathrm{Lip}}(\gamma,\Sigma,W)$
defined by

$\varphi:=\sum_{i=1}^{{\cal N}}a_{i}f_{i}\quad\text{so that for every
}l\in\\{0,\ldots,k\\}\text{ we have}\quad\varphi^{(l)}=\sum_{i=1}^{{\cal
N}}a_{i}f_{i}^{(l)}.$ (3.1)

We consider the following sparse approximation problem. Given $\varepsilon>0$
and a fixed $l\in\\{0,\ldots,k\\}$, find an element $u=\sum_{i=1}^{{\cal
N}}b_{i}f_{i}\in\operatorname{Span}({\cal F})$ satisfying the following
properties. Finite Domain Approximation Conditions

  1. (1)

There exists an integer $M\in\\{1,\ldots,{\cal N}-1\\}$ for which the set

${\rm support}(u):=\left\\{i\in\\{1,\ldots,{\cal N}\\}:b_{i}\neq
0\right\\}\qquad\text{satisfies that}\qquad\\#\left({\rm
support}(u)\right)\leq M.$ (3.2)

  2. (2)

The coefficients $b_{1},\ldots,b_{{\cal N}}\in{\mathbb{R}}$ satisfy that

$\sum_{i=1}^{{\cal N}}|b_{i}|A_{i}\leq C:=\sum_{i=1}^{{\cal N}}|a_{i}|A_{i}.$
(3.3)

  3. (3)

The function $u\in\operatorname{Span}({\cal F})$ well-approximates $\varphi$
throughout $\Sigma$ in the pointwise sense that

$\max_{p\in\Sigma}\left\\{\Lambda^{l}_{\varphi-u}(p)\right\\}\stackrel{{\scriptstyle{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}({\ref{lip_eta_lip_norm_func}})}}}{{=}}\max_{p\in\Sigma}\left\\{\max_{j\in\\{0,\ldots,l\\}}\left\\{\left|\left|\varphi^{(j)}(p)-u^{(j)}(p)\right|\right|_{{\cal
L}(V^{\otimes j};W)}\right\\}\right\\}\leq\varepsilon.$ (3.4)

The choice of $l\in\\{0,\ldots,k\\}$ provides a gauge for the strength of
approximation we seek. Loosely, the condition
$\Lambda^{l}_{\varphi-u}(p)\leq\varepsilon$ generalises the notion of
approximating the derivatives of $\varphi$ up to order $l$ at the point $p$.
Indeed, if we have the situation that $f_{1},\ldots,f_{{\cal
N}}\in{\mathrm{Lip}}(\gamma,O,W)$ for some open subset $O\subset V$ satisfying
$\Sigma\subset O$, then each $f_{i}^{(0)}$ is $k$ times continuously Frechét
differentiable at $p$ with, for each $j\in\\{0,\ldots,k\\}$,
$f_{i}^{(j)}(p)=D^{j}f_{i}^{(0)}(p)$. Consequently, the condition that
$\Lambda^{l}_{\varphi-u}(p)\leq\varepsilon$ requires $\varphi^{(0)}$ and
$u^{(0)}$ to be close in the $C^{l}$-sense that their $j^{\text{th}}$
derivatives, for every $j\in\\{0,\ldots,l\\}$, at $p$ are within $\varepsilon$
of one and other as elements in ${\cal L}(V^{\otimes j};W)$. In the general
case that the functions $f_{1},\ldots,f_{{\cal N}}$ are defined only on the
finite subset $\Sigma\subset V$, the condition
$\Lambda^{l}_{\varphi-u}(p)\leq\varepsilon$ is a generalisation in which we
require, for every $j\in\\{0,\ldots,l\\}$, that at $p\in\Sigma$ the functions
$\varphi^{(j)}(p),u^{(j)}(p)\in{\cal L}(V^{\otimes j};W)$ are within
$\varepsilon$ of one and other in the $||\cdot||_{{\cal L}(V^{\otimes j};W)}$
norm sense.

Observe that the choice $u:=\varphi$, so that for every $i\in\\{1,\ldots,{\cal
N}\\}$ we have $b_{i}:=a_{i}$, satisfies both Finite Domain Approximation
Conditions (2) and (3). However, from the perspective of reducing
computational complexity, this trivial approximation of $\varphi$ is useless.
Finite Domain Approximation Condition (1) is imposed avoid this trivial
solution. The upper bound on the cardinality of ${\rm support}(u)$ required in
(3.2) in Finite Domain Approximation Condition (1) ensures that an
approximation is acceptable only if it is a linear combination of strictly
less than ${\cal N}$ of the functions in ${\cal F}$.

Perhaps the strangest requirements are those imposed on the coefficients
$b_{1},\ldots,b_{{\cal N}}\in{\mathbb{R}}$ by (3.3) in Finite Domain
Approximation Condition (2). There are two main reasons for this restriction.
Firstly, the requirement (3.3) in Finite Domain Approximation Condition (2)
ensures that the ${\mathrm{Lip}}(\gamma,\Omega,W)$ norm of the approximation
$u$ is bounded above by the fixed constant $C$. Secondly, Finite Domain
Approximation Condition (2) will enable us to tackle this sparse approximation
problem when the functions $f_{1},\ldots,f_{{\cal N}}$ have a compact domain
$\Omega\subset V$ rather than a finite domain $\Sigma\subset V$. We provide
the details of this extension in Section 4.

It is primarily for the purpose of tackling the compact domain sparse
approximation problem specified in Section 4 that we introduce the scalars
$A_{1},\ldots,A_{{\cal N}}\in{\mathbb{R}}_{>0}$ satisfying, for every
$i\in\\{1,\ldots,{\cal N}\\}$, that
$||f_{i}||_{{\mathrm{Lip}}(\gamma,\Sigma,W)}\leq A_{i}$, rather than simply
taking $A_{1}:=||f_{1}||_{{\mathrm{Lip}}(\gamma,\Sigma,W)},\ldots,A_{{\cal
N}}:=||f_{{\cal N}}||_{{\mathrm{Lip}}(\gamma,\Sigma,W)}$. If we are only
interested in approximating $\varphi$ on the finite subset $\Sigma$ then this
choice is arguably the most natural one to make. Under this choice, the
${\mathrm{Lip}}(\gamma,\Sigma,W)$ norm of the approximation is constrained to
be no worse than the best a priori upper bound we have for the
${\mathrm{Lip}}(\gamma,\Sigma,W)$ norm of $\varphi$. When we happen to know
that the functions $f_{1},\ldots,f_{{\cal N}}$ are additionally be defined at
points _not_ in $\Sigma$ then we consider scalars $A_{1},\ldots,A_{{\cal N}}$
that are not necessarily equal to
$||f_{1}||_{{\mathrm{Lip}}(\gamma,\Sigma,W)},\ldots,||f_{{\cal
N}}||_{{\mathrm{Lip}}(\gamma,\Sigma,W)}$. This situation is illustrated in the
extension to compact domains presented in Section 4.

As stated, there is of course no guarantee that a solution to our sparse
approximation problem satisfying conditions (1), (2), and (3) exists. Thus the
strategy we adopt in this paper is as follows. Firstly, we define the HOLGRIM
algorithm in Section 6 that is designed to find an approximation
$u\in\operatorname{Span}({\cal F})$ of $\varphi$ satisfying conditions (2) and
(3). We then subsequently establish conditions in Section 10 under which the
approximation returned by the HOLGRIM algorithm is guaranteed to additionally
satisfy condition (1) (cf. the _HOLGRIM Convergence Theorem_ 10.1 in Section
10).

##  4 Extension to Compact Domains

In this section we illustrate how being able to solve the sparse approximation
problem detailed in Section 3 for a finite domain $\Sigma\subset V$ enables
one to solve the same sparse approximation problem in the setting that the
finite domain $\Sigma\subset V$ is replaced by a compact domain $\Omega\subset
V$. This is achieved by utilising the _Lipschitz Sandwich Theorems_ obtained
in [LM24] and stated in Section 2 of this paper.

For this purpose we let $c,d\in{\mathbb{Z}}_{\geq 1}$ and assume that $V$ is a
$d$-dimensional real Banach space and that $W$ is a $c$-dimensional real
Banach space. Let $\gamma>0$ with $k\in{\mathbb{Z}}_{\geq 0}$ such that
$\gamma\in(k,k+1]$. Let ${\cal N}\in{\mathbb{Z}}_{\geq 1}$ be a (large)
positive integer, $\Omega\subset V$ a non-empty compact subset, and ${\cal
F}:=\\{f_{1},\ldots,f_{{\cal N}}\\}\subset{\mathrm{Lip}}(\gamma,\Omega,W)$ be
a finite collection of non-zero ${\mathrm{Lip}}(\gamma,\Omega,W)$ functions.
Fix a choice of non-zero coefficients $a_{1},\ldots,a_{{\cal
N}}\in{\mathbb{R}}\setminus\\{0\\}$ and consider
$\varphi\in{\mathrm{Lip}}(\gamma,\Omega,W)$ defined by
$\varphi:=\sum_{i=1}^{{\cal N}}a_{i}f_{i}$. Define $C:=\sum_{i=1}^{{\cal
N}}|a_{i}|||f_{i}||_{{\mathrm{Lip}}(\gamma,\Omega,W)}>0$ so that
$||\varphi||_{{\mathrm{Lip}}(\gamma,\Omega,W)}\leq C$.

Fix $\varepsilon>0$ and $l\in\\{0,\ldots,k\\}$. We first consider a sparse
approximation problem analogous to the sparse approximation problem specified
in Section 3. That is, find an element $u=\sum_{i=1}^{{\cal
N}}b_{i}f_{i}\in\operatorname{Span}({\cal F})$ satisfying the following
properties. Compact Domain Approximation Conditions

  1. (1)

There exists an integer $M\in\\{1,\ldots,{\cal N}-1\\}$ for which the set

${\rm support}(u):=\left\\{i\in\\{1,\ldots,{\cal N}\\}:b_{i}\neq
0\right\\}\qquad\text{satisfies that}\qquad\\#\left({\rm
support}(u)\right)\leq M.$ (4.1)

  2. (2)

The coefficients $b_{1},\ldots,b_{{\cal N}}\in{\mathbb{R}}$ satisfy that

$\sum_{i=1}^{{\cal N}}|b_{i}|||f_{i}||_{{\mathrm{Lip}}(\gamma,\Omega,W)}\leq
C:=\sum_{i=1}^{{\cal N}}|a_{i}|||f_{i}||_{{\mathrm{Lip}}(\gamma,\Omega,W)}.$
(4.2)

  3. (3)

The function $u\in\operatorname{Span}({\cal F})$ well-approximates $\varphi$
throughout $\Omega$ in the pointwise sense that

$\sup_{z\in\Sigma}\left\\{\Lambda^{l}_{\varphi-u}(z)\right\\}\stackrel{{\scriptstyle{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}({\ref{lip_eta_lip_norm_func}})}}}{{=}}\sup_{z\in\Sigma}\left\\{\max_{j\in\\{0,\ldots,l\\}}\left\\{\left|\left|\varphi^{(j)}(z)-u^{(j)}(z)\right|\right|_{{\cal
L}(V^{\otimes j};W)}\right\\}\right\\}\leq\varepsilon.$ (4.3)

Observe that if $C\leq\varepsilon$ then the zero function in
$\operatorname{Span}({\cal F})\subset{\mathrm{Lip}}(\gamma,\Omega,W)$ is an
approximation of $\varphi$ satisfying Compact Domain Approximation Conditions
(1), (2), and (3). Thus we restrict to the meaningful setting in which
$\varepsilon\in(0,C)$.

In this case, fix a choice of $\varepsilon_{0}\in(0,\varepsilon)$ and define a
constant $r=r(C,\gamma,\varepsilon,\varepsilon_{0},l)>0$ by (cf. (2.12))

$r:=\sup\left\\{\theta>0~{}:~{}2C\theta^{\gamma-l}+\varepsilon_{0}e^{\theta}\leq\varepsilon\right\\}\in(0,1].$
(4.4)

Subsequently define an integer
$\Lambda=\Lambda(\Omega,C,\gamma,\varepsilon,\varepsilon_{0},l)\in{\mathbb{Z}}_{\geq
1}$ by

$\Lambda:=\min\left\\{a\in{\mathbb{Z}}_{\geq
1}~{}:~{}\exists~{}z_{1},\ldots,z_{a}\in\Omega\text{ for which
}\Omega\subset\bigcup_{s=1}^{a}{\overline{\mathbb{B}}}_{V}(z_{s},r)\right\\}.$
(4.5)

A consequence of $\Omega\subset V$ being compact is that the integer
$\Lambda\in{\mathbb{Z}}_{\geq 1}$ defined in (4.5) is finite. Choose a subset
$\Sigma=\\{p_{1},\ldots,p_{\Lambda}\\}\subset\Omega\subset V$ such that
$\Omega\subset\cup_{s=1}^{\Lambda}{\overline{\mathbb{B}}}_{V}(p_{s},r)$.

It is evident that, by restriction, we have that $f_{1},\ldots,f_{{\cal
N}}\in{\mathrm{Lip}}(\gamma,\Sigma,W)$ with, for every $i\in\\{1,\ldots,{\cal
N}\\}$, the norm estimate
$||f_{i}||_{{\mathrm{Lip}}(\gamma,\Sigma,W)}\leq||f_{i}||_{{\mathrm{Lip}}(\gamma,\Omega,W)}$.
Thus we may consider the sparse approximation problem detailed in Section 3
for the $\varepsilon$ there as $\varepsilon_{0}$ here, finite subset
$\Sigma\subset V$ there as the finite subset $\Sigma\subset\Omega\subset V$
here, the functions $f_{1},\ldots,f_{{\cal N}}$ there as the restriction of
the functions $f_{1},\ldots,f_{{\cal N}}$ here to the finite subset $\Sigma$
here, the scalars $A_{1},\ldots,A_{{\cal N}}$ there as
$||f_{1}||_{{\mathrm{Lip}}(\gamma,\Omega,W)},\ldots,||f_{{\cal
N}}||_{{\mathrm{Lip}}(\gamma,\Omega,W)}$ here, and the integer
$l\in\\{0,\ldots,k\\}$ there as $k$ here. We assume that we are able to find a
solution $u\in\operatorname{Span}({\cal F})$ to this sparse approximation
problem satisfying Finite Domain Approximation Conditions (1), (2), and (3)
from Section 3.

That is, we assume that we can find coefficients $b_{1},\ldots,b_{{\cal
N}}\in{\mathbb{R}}$ such that (cf. (3.2))

$\\#\\{b_{s}\neq 0:s\in\\{1,\ldots,{\cal N}\\}\\}\leq M<{\cal N},$ (4.6)

with (cf. (3.3))

$\sum_{i=1}^{{\cal
N}}|b_{i}|||f_{i}||_{{\mathrm{Lip}}(\gamma,\Omega,W)}\leq\sum_{i=1}^{{\cal
N}}|a_{i}|||f_{i}||_{{\mathrm{Lip}}(\gamma,\Omega,W)}=C,$ (4.7)

and such that $u:=\sum_{i=1}^{{\cal N}}b_{i}f_{i}$ satisfies that (cf. (3.4))

$\max_{z\in\Sigma}\left\\{\Lambda^{k}_{\varphi-u}(z)\right\\}\leq\varepsilon_{0}.$
(4.8)

A particular consequence of (4.7) is that
$u\in{\mathrm{Lip}}(\gamma,\Omega,W)$ satisfies
$||u||_{{\mathrm{Lip}}(\gamma,\Omega,W)}\leq C$. Therefore, together with
(4.8), this yields the required hypotheses to appeal to the _Pointwise
Lipschitz Sandwich Theorem_ 2.10. Indeed, observe that the constant $r$
defined in (4.4) coincides with the constant $\delta_{0}$ defined in (2.12)
for the constants $\varepsilon$, $\varepsilon_{0}$, $K_{0}$, $\gamma$, and $l$
there as $\varepsilon$, $\varepsilon_{0}$, $C$, $\gamma$, and $l$ here
respectively. Moreover, the definition of $\Lambda$ in (4.5) ensures that
$\Sigma$ is a $r$-cover of $\Omega$ in the sense required in (2.13) for the
subsets $B$ and ${\cal M}$ there as $\Sigma$ and $\Omega$ here respectively.
Consequently we are able to apply the _Pointwise Lipschitz Sandwich Theorem_
2.10 with the subsets $B$ and ${\cal M}$ of that result as $\Sigma$ and
$\Omega$ here respectively, the constants $\varepsilon$, $\varepsilon_{0}$,
$K_{0}$, $\gamma$, and $l$ of that result as $\varepsilon$, $\varepsilon_{0}$,
$C$, $\gamma$, and $l$ here respectively, and the functions $\psi$ and $\phi$
of that result as $\varphi$ and $u$ here respectively. By doing so we may
conclude via the implication in (2.14) that
$\sup_{z\in\Omega}\left\\{\Lambda^{l}_{\varphi-u}(z)\right\\}\leq\varepsilon$.
Consequently, the function $u=\sum_{i=1}^{{\cal
N}}b_{i}f_{i}\in\operatorname{Span}({\cal F})$ is an approximation of
$\varphi$ on $\Omega$ that satisfies Compact Domain Approximation Conditions
(1), (2), and (3).

Moreover, at the cost of the involved constants becoming less explicit, the
_Lipschitz Sandwich Theorem_ 2.9 from [LM24] can be utilised to strengthen the
sense in which the returned approximation $u$ is required to approximate
$\varphi$ throughout $\Omega$ in Compact Domain Approximation Condition (3).
To be more precise, we now consider the following problem. For a fixed
$\eta\in(0,\gamma)$, find an element $u=\sum_{i=1}^{{\cal
N}}b_{i}f_{i}\in\operatorname{Span}({\cal F})$ satisfying the following
properties. Compact Domain Lipschitz Approximation Conditions

  1. (1)

There exists an integer $M\in\\{1,\ldots,{\cal N}-1\\}$ for which the set

${\rm support}(u):=\left\\{i\in\\{1,\ldots,{\cal N}\\}:b_{i}\neq
0\right\\}\qquad\text{satisfies that}\qquad\\#\left({\rm
support}(u)\right)\leq M.$ (4.9)

  2. (2)

The coefficients $b_{1},\ldots,b_{{\cal N}}\in{\mathbb{R}}$ satisfy that

$\sum_{i=1}^{{\cal
N}}|b_{i}|||f_{i}||_{{\mathrm{Lip}}(\gamma,\Omega,W)}\leq\sum_{i=1}^{{\cal
N}}|a_{i}|||f_{i}||_{{\mathrm{Lip}}(\gamma,\Omega,W)}=:C.$ (4.10)

  3. (3)

The function $u\in\operatorname{Span}({\cal F})$ well-approximates $\varphi$
throughout $\Omega$ in the ${\mathrm{Lip}}(\eta)$ sense that

$\left|\left|\varphi_{[q]}-u_{[q]}\right|\right|_{{\mathrm{Lip}}(\eta,\Omega,W)}\leq\varepsilon$
(4.11)

where $q\in\\{0,\ldots,k\\}$ is such that $\eta\in(q,q+1]$. Recall that if
$\phi=\left(\phi^{(0)},\ldots,\phi^{(k)}\right)\in{\mathrm{Lip}}(\gamma,\Omega,W)$
then $\phi_{[q]}:=\left(\phi^{(0)},\ldots,\phi^{[q]}\right)$.

Observe that if $C\leq\varepsilon$ for the constant $C$ defined in (4.10) then
the zero function in $\operatorname{Span}({\cal
F})\subset{\mathrm{Lip}}(\gamma,\Omega,W)$ is an approximation of $\varphi$
satisfying Compact Domain Lipschitz Approximation Conditions (1), (2), and
(3). Therefore we again restrict to the meaningful setting in which
$\varepsilon\in(0,C)$.

Retrieve the constants $r=r(C,\gamma,\eta,\varepsilon)>0$ and
$\varepsilon_{0}=\varepsilon_{0}(C,\gamma,\eta,\varepsilon)>0$ arising as
$\delta_{0}$ and $\varepsilon_{0}$ respectively in the _Lipschitz Sandwich
Theorem_ 2.9 for the constants $K_{0}$, $\gamma$, $\eta$, and $\varepsilon$
there as $C$, $\gamma$, $\eta$, and $\varepsilon$ here respectively. Note we
are not actually applying Theorem 2.9, but simply retrieving constants in
preparation for its future application. Subsequently define an integer
$\Lambda=\Lambda(\Omega,C,\gamma,\eta,\varepsilon)\in{\mathbb{Z}}_{\geq 1}$ by

$\Lambda:=\min\left\\{a\in{\mathbb{Z}}_{\geq
1}~{}:~{}\exists~{}z_{1},\ldots,z_{a}\in\Omega\text{ for which
}\Omega\subset\bigcup_{s=1}^{a}{\overline{\mathbb{B}}}_{V}(z_{s},r)\right\\}.$
(4.12)

The subset $\Omega\subset V$ being compact ensures that $\Lambda$ defined in
(4.12) is finite. Choose a subset
$\Sigma=\left\\{p_{1},\ldots,p_{\Lambda}\right\\}\subset\Omega\subset V$ such
that $\Omega\subset\cup_{s=1}^{\Lambda}{\overline{\mathbb{B}}}_{V}(p_{s},r)$.

As before, we assume that we are able to find a solution
$u\in\operatorname{Span}({\cal F})$ to this sparse approximation problem for
the finite subset $\Sigma$ satisfying Finite Domain Approximation Conditions
(1), (2), and (3) from Section 3. That is, we assume that we can find
coefficients $b_{1},\ldots,b_{{\cal N}}\in{\mathbb{R}}$ satisfying (4.6) and
(4.7), and such that $u:=\sum_{i=1}^{{\cal N}}b_{i}f_{i}$ satisfies (4.8) for
the constant $\varepsilon_{0}$ retrieved from the _Lipschitz Sandwich Theorem_
2.9 above. It is again a consequence of (4.7) that
$u\in{\mathrm{Lip}}(\gamma,\Omega,W)$ satisfies that
$||u||_{{\mathrm{Lip}}(\gamma,\Omega,W)}\leq C$, and so the pointwise
estimates (4.8) now provide the required hypothesis to appeal to the
_Lipschitz Sandwich Theorem_ 2.9.

Indeed we have specified that the constants $r$ and $\varepsilon_{0}$ here
coincide with the constants $\delta_{0}$ and $\varepsilon_{0}$ arising in the
_Lipschitz Sandwich Theorem_ 2.9, for the choices of the constants $K_{0}$,
$\gamma$, $\eta$ and $\varepsilon$ there as $C$, $\gamma$, $\eta$ and
$\varepsilon$ here, respectively. Further, the subset $\Sigma$ is chosen to be
a $r$-cover of $\Omega$ in the sense required in (2.10). Consequently we are
able to apply the _Lipschitz Sandwich Theorem_ for the choices of the subsets
$B$ and ${\cal M}$ there as $\Sigma$ and $\Omega$ here respectively, the
choices of the constants $K_{0}$, $\gamma$, $\eta$, and $\varepsilon$ there
are $C$, $\gamma$, $\eta$, and $\varepsilon$ here respectively, and for the
choices of the functions $\psi$ and $\phi$ there as $\varphi$ and $u$ here
respectively. By doing so we may conclude via the implication (2.11) that
$\left|\left|\varphi_{[q]}-u_{[q]}\right|\right|_{{\mathrm{Lip}}(\eta,\Omega,W)}\leq\varepsilon$.
Consequently, the function $u=\sum_{i=1}^{{\cal
N}}b_{i}f_{i}\in\operatorname{Span}({\cal F})$ is an approximation of
$\varphi$ on $\Omega$ that satisfies Compact Domain Lipschitz Approximation
Conditions (1), (2), and (3).

##  5 Pointwise Values Via Linear Functionals

In this section, given a closed subset ${\cal M}\subset V$ and a point
$z\in{\cal M}$, we define a finite subset ${\cal
T}_{z,k}\subset{\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$ of the dual-space
${\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$ of bounded linear functionals
${\mathrm{Lip}}(\gamma,{\cal M},W)\to{\mathbb{R}}$ such that for any
$\psi\in{\mathrm{Lip}}(\gamma,{\cal M},W)$ the value of $\psi$ at $z$ is
determined, up to a quantifiable error, by the values $\sigma(\psi)$ for the
linear functionals $\sigma\in{\cal T}_{z,k}$. We begin by introducing the
following particularly useful quantities.

For integers $a,b\in{\mathbb{Z}}_{\geq 0}$, define $\beta(a,b)$ by

$\beta(a,b):=\left(\begin{array}[]{c}a+b-1\\\
b\end{array}\right)=\frac{(a+b-1)!}{(a-1)!b!}=\left\\{\begin{array}[]{ll}1&\mbox{if
}b=0\\\ \frac{1}{b!}\prod_{s=0}^{b-1}(a+s)&\mbox{if }b\geq
1.\end{array}\right.$ (5.1)

Further, for integers $a,b,i,j\in{\mathbb{Z}}_{\geq 0}$ define $D(a,b)$ and
$Q(i,j,a,b)$ by

$D(a,b):=\sum_{l=0}^{b}\beta(a,l)\qquad\text{and}\qquad
Q(i,j,a,b):=1+ijD(a,b)=1+ij\sum_{l=0}^{b}\beta(a,l)$ (5.2)

respectively.

Let $d\in{\mathbb{Z}}_{\geq 1}$ and $V$ be a real $d$-dimensional Banach space
with ${\cal M}\subset V$ a closed subset. Assume that the tensor powers of $V$
are equipped with admissible norms (cf. Definition 2.1). Fix a choice of a
unit $V$-norm basis $v_{1},\ldots,v_{d}$ of $V$. Then, recalling that the
tensor powers of $V$ are assumed to be equipped with admissible tensor norms
in the sense of definition 2.1, for each $n\in{\mathbb{Z}}_{\geq 1}$ the set

${\cal V}_{n}:=\left\\{v_{l_{1}}\otimes\ldots\otimes
v_{l_{n}}:(l_{1},\ldots,l_{n})\in\\{1,\ldots,d\\}^{n}\right\\}$ (5.3)

is a unit $V^{\otimes n}$-norm basis for $V^{\otimes n}$. Consequently, for
each $j\in\\{1,\ldots,k\\}$ a symmetric $j$-linear form ${\bf B}\in{\cal
L}(V^{\otimes j};W)$ is determined by its action on the subset ${\cal
V}^{\operatorname{ord}}_{j}\subset{\cal V}_{j}$ defined by

${\cal V}^{\operatorname{ord}}_{j}:=\left\\{v_{l_{1}}\otimes\ldots\otimes
v_{l_{j}}:(l_{1},\ldots,l_{j})\in\\{1,\ldots,d\\}^{j}\text{ such that
}l_{1}\leq\ldots\leq l_{j}\right\\}\subset{\cal V}_{j}.$ (5.4)

That is, the collection of values ${\bf B}\left[v_{l_{1}}\otimes\ldots\otimes
v_{l_{j}}\right]$ for every $(l_{1},\ldots,l_{j})\in\\{1,\ldots,d\\}^{j}$ with
$l_{1}\leq\ldots\leq l_{j}$ determine the value ${\bf B}[v]$ for every $v\in
V^{\otimes j}$. The cardinality of ${\cal V}^{\operatorname{ord}}_{j}$ is
given by $\beta(d,j)$ defined in (5.1). The following lemma records how the
bases ${\cal V}_{n}$ for the tensor powers $V^{\otimes n}$ interact with a
choice of admissible tensor norms for the tensor powers $V^{\otimes n}$ (cf.
Definition 2.1).

######  Lemma 5.1.

Assume that $V$ is a Banach space of dimension $d\in{\mathbb{Z}}_{\geq 1}$ and
that the tensor powers of $V$ are equipped with admissible tensor norms (cf.
Definition 2.1). Suppose that $v_{1},\ldots,v_{d}\in V$ is a basis of $V$
normalised so that $||v_{1}||_{V}=\ldots=||v_{d}||_{V}=1$. Let
$m\in{\mathbb{Z}}_{\geq 1}$ and consider the basis ${\cal V}_{m}$ of
$V^{\otimes m}$ given by

${\cal V}_{m}:=\left\\{v_{l_{1}}\otimes\ldots\otimes
v_{l_{m}}:(l_{1},\ldots,l_{m})\in\\{1,\ldots,d\\}^{m}\right\\}.$ (5.5)

Then for any $v\in V^{\otimes m}$ there exist coefficients
$\left\\{C_{j_{1}\dots
j_{m}}:(j_{1},\ldots,j_{m})\in\\{1,\ldots,d\\}^{m}\right\\}$ for which

$v=\sum_{j_{1}=1}^{d}\ldots\sum_{j_{m}=1}^{d}C_{j_{1}\dots
j_{m}}v_{j_{1}}\otimes\ldots\otimes v_{j_{m}}.$ (5.6)

Moreover, if $A\geq 0$ and $||v||_{V^{\otimes m}}\leq A$, then

$\sum_{j_{1}=1}^{d}\dots\sum_{j_{m}=1}^{d}\left|C_{j_{1}\dots
j_{m}}\right|\leq Ad^{m}.$ (5.7)

###### Proof of Lemma 5.1.

Assume that $V$ is a Banach space of dimension $d\in{\mathbb{Z}}_{\geq 1}$ and
that the tensor powers of $V$ are equipped with admissible tensor norms (cf.
Definition 2.1). Suppose that $v_{1},\ldots,v_{d}\in V$ is a basis of $V$
normalised so that $||v_{1}||_{V}=\ldots=||v_{d}||_{V}=1$. We first verify the
claims made in (5.6) and (5.7) in the case that $m=1$.

Let $v\in V$; the existence of coefficients
$C_{1},\ldots,C_{d}\in{\mathbb{R}}$ such that $v=\sum_{j=1}^{d}C_{j}v_{j}$ is
an immediate consequence of $v_{1},\ldots,v_{d}\in V$ being a basis of $V$.
Now assume $A\geq 0$ and that $||v||_{V}\leq A$. It is convenient to consider
the dual-basis $v_{1}^{\ast},\ldots,v^{\ast}_{d}\in V^{\ast}$ corresponding to
$v_{1},\ldots,v_{d}\in V$. This means that whenever $i,j\in\\{1,\ldots,d\\}$
we have $v_{j}^{\ast}(v_{i})=\delta_{ij}$, and that for every
$j\in\\{1,\ldots,d\\}$ we have $||v_{j}^{\ast}||_{V^{\ast}}=1$. Here, for
$\sigma\in V^{\ast}$, we have
$||\sigma||_{V^{\ast}}=\sup\left\\{|\sigma(u)|:u\in V\text{ and }||u||_{V}\leq
1\right\\}$.

Being a finite dimensional Banach space means $V$ is reflexive. A particular
consequence of this is, for any $u\in V$, that
$||u||_{V}=||u||_{V^{\ast\ast}}$ where we view $u$ as an element in
$V^{\ast\ast}$ by defining its action on an element $\sigma\in V^{\ast}$ by
$u(\sigma):=\sigma(u)$. Further, since
$||u||_{V^{\ast\ast}}=\sup\left\\{|u(\sigma)|:\sigma\in V^{\ast}\text{ and
}||\sigma||_{V^{\ast}}\leq 1\right\\}$ , we have, for every
$j\in\\{1,\ldots,d\\}$, that
$|C_{j}|=\left|v^{\ast}_{j}(v)\right|\leq||v||_{V^{\ast\ast}}=||v||_{V}\leq
A$. It is now immediate that $\sum_{j=1}^{d}|C_{j}|\leq Ad$, verifying that
(5.7) is valid in the case that $m=1$.

It remains only to verify that (5.6) and (5.7) are valid in the case that
$m\in{\mathbb{Z}}_{\geq 2}$. For this purpose fix $m\in{\mathbb{Z}}_{\geq 2}$
and let $v\in V^{\otimes m}$. The existence of coefficients
$\left\\{C_{j_{1}\dots
j_{m}}:(j_{1},\ldots,j_{m})\in\\{1,\ldots,d\\}^{m}\right\\}$ for which (5.6)
is true is a consequence of the fact that the set ${\cal
V}_{m}:=\left\\{v_{j_{1}}\otimes\ldots\otimes
v_{j_{m}}:(j_{1},\ldots,j_{m})\in\\{1,\ldots,d\\}^{m}\right\\}$ defined in
(5.5) is a basis for $V^{\otimes m}$. Moreover, since the tensor powers of $V$
are equipped with admissible tensor norms, we have, for every
$(j_{1},\ldots,j_{m})\in\\{1,\ldots,d\\}^{m}$, that (cf. Definition 2.1)

$\left|\left|v_{j_{1}}\otimes\ldots\otimes v_{j_{m}}\right|\right|_{V^{\otimes
m}}=||v_{j_{1}}||_{V}\dots||v_{j_{m}}||_{V}=1.$ (5.8)

Now assume that $A\geq 0$ and that $||v||_{V^{\otimes m}}\leq A$. A
consequence of the tensor powers of $V$ being equipped with admissible norms
is that for any $u\in V^{\otimes m}$ we have (cf. Proposition 2.1 in [Rya02])

$||u||_{\operatorname{inj}(V^{\otimes m})}\leq||u||_{V^{\otimes
m}}\leq||u||_{\operatorname{proj}(V^{\otimes m})}.$ (5.9)

Here $||\cdot||_{\operatorname{inj}(V^{\otimes m})}$ denotes the _injective
cross norm_ on $V^{\otimes m}$ defined by

$||u||_{\operatorname{inj}(V^{\otimes
m})}:=\sup\left\\{\left|\phi_{1}\otimes\ldots\otimes\phi_{m}(u)\right|:\phi_{1},\ldots,\phi_{m}\in
V^{\ast}\text{ with
}||\phi_{1}||_{V^{\ast}}=\ldots=||\phi_{m}||_{V^{\ast}}=1\right\\},$ (5.10)

and $||\cdot||_{\operatorname{proj}(V^{\otimes m})}$ denotes the _projective
cross norm_ on $V^{\otimes m}$ defined by

$||u||_{\operatorname{proj}(V^{\otimes
m})}:=\inf\left\\{\sum_{i}||a_{1,i}||_{V}\ldots||a_{m,i}||_{V}:u=\sum_{i}a_{1,i}\otimes\ldots\otimes
a_{m,i}\right\\}.$ (5.11)

If we let $v_{1}^{\ast},\ldots,v^{\ast}_{d}\in V^{\ast}$ denote the dual-basis
to $v_{1},\ldots,v_{d}\in V$ then, for each
$(j_{1},\ldots,j_{m})\in\\{1,\ldots,d\\}^{m}$, it follows that

$A\geq||v||_{V^{\otimes
m}}\stackrel{{\scriptstyle{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}({\ref{inj_norm_proj_norm_bound}})}}}{{\geq}}||v||_{\operatorname{inj}(V^{\otimes
m})}\stackrel{{\scriptstyle{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}({\ref{inj_norm_def}})}}}{{\geq}}\left|v_{j_{1}}^{\ast}\otimes\ldots\otimes
v_{j_{m}}^{\ast}(v)\right|\stackrel{{\scriptstyle{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}({\ref{basis_expansion}})}}}{{=}}\left|C_{j_{1}\dots
j_{m}}\right|.$ (5.12)

Summing over $(j_{1},\ldots,j_{m})\in\\{1,\ldots,d\\}^{m}$ in (5.12) yields
(5.7), which completes the proof of Lemma 5.1. ∎

Let $c\in{\mathbb{Z}}_{\geq 1}$ and $W$ be a real $c$-dimensional Banach
space. Fix a choice of a unit $W$-norm basis $w_{1},\ldots,w_{c}$ of $W$, and
consider its corresponding dual basis $w_{1}^{\ast},\ldots,w_{c}^{\ast}$ of
$W^{\ast}$. Then whenever $a,b\in\\{1,\ldots,c\\}$ we have

$w_{a}^{\ast}(w_{b}):=\left\\{\begin{array}[]{ll}1&\mbox{if }a=b\\\ 0&\mbox{if
}a\neq b.\end{array}\right.$ (5.13)

A particularly useful consequence is that any $w\in W$ can be decomposed as

$w=\sum_{s=1}^{c}w^{\ast}_{s}(w)w_{s}.$ (5.14)

We use the these bases for $V$, $W$, and the tensor powers of $V$ to define,
for each point in ${\cal M}$, an associated collection of bounded linear
functionals in the dual-space ${\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$.

For $p\in{\cal M}$ and $s\in\\{1,\ldots,c\\}$ define
$\delta_{p,0,s}\in{\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$ by setting, for
$\phi=\left(\phi^{(0)},\ldots,\phi^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal
M},W)$,

$\delta_{p,0,s}(\phi):=w_{s}^{\ast}\left(\phi^{(0)}(p)\right).$ (5.15)

For $p\in{\cal M}$, $j\in\\{1,\ldots,k\\}$, $v\in V^{\otimes j}$, and
$s\in\\{1,\ldots,c\\}$ define $\delta_{p,j,v,s}\in{\mathrm{Lip}}(\gamma,{\cal
M},W)^{\ast}$ by setting, for
$\phi=\left(\phi^{(0)},\ldots,\phi^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal
M},W)$,

$\delta_{p,j,v,s}(\phi):=w_{s}^{\ast}\left(\phi^{(j)}(p)[v]\right).$ (5.16)

Then for a given $j\in\\{0,\ldots,k\\}$ define ${\cal
M}_{p,j}\subset{\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$ by

${\cal
M}_{p,j}:=\left\\{\begin{array}[]{ll}\left\\{\delta_{p,0,s}:s\in\\{1,\ldots,c\\}\right\\}&\mbox{if
}j=0\\\ \left\\{\delta_{p,j,v,s}:v\in{\cal V}_{j}^{\operatorname{ord}}\text{
and }s\in\\{1,\ldots,c\\}\right\\}&\mbox{if }j\geq 1.\end{array}\right.$
(5.17)

It follows from (5.1) and (5.17) that

$\\#\left({\cal M}_{p,j}\right)=c\beta(d,j).$ (5.18)

For a given $l\in\\{0,\ldots,k\\}$, define ${\cal
T}_{p,l}\subset{\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$ by

${\cal T}_{p,l}:=\bigcup_{j=0}^{l}{\cal M}_{p,j}.$ (5.19)

It follows from (5.19) that, since the union in (5.19) is disjoint we have

$\\#\left({\cal T}_{p,l}\right)=\sum_{j=0}^{l}\\#\left({\cal
M}_{p,j}\right)\stackrel{{\scriptstyle{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}({\ref{eq:not_sec_m_pj_card}})}}}{{=}}c\sum_{j=0}^{l}\beta(d,j)\stackrel{{\scriptstyle{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}({\ref{eq:D_ab_Q_ijab_def_not_sec}})}}}{{=}}cD(d,l).$
(5.20)

Finally, for a given $l\in\\{0,\ldots,k\\}$, define ${\cal
M}_{l}^{\ast}\subset{\mathrm{Lip}}(\gamma,{\cal M},W)$ by

${\cal M}_{l}^{\ast}:=\bigcup_{z\in{\cal M}}{\cal T}_{z,l}.$ (5.21)

A consequence of the union in (5.21) being disjoint is that when ${\cal
M}\subset V$ is finite with cardinality $\Lambda\in{\mathbb{Z}}_{\geq 1}$ we
have

$\\#\left({\cal M}_{l}^{\ast}\right)=\sum_{z\in{\cal M}}\\#\left({\cal
T}_{z,l}\right)\stackrel{{\scriptstyle{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}({\ref{eq:Tau_pl_card_not_sec}})}}}{{=}}\sum_{s=1}^{\Lambda}cD(d,l)=cD(d,l)\Lambda.$
(5.22)

In the remainder of this section we establish several lemmata in order to
provide a precise quantified meaning to the statement that the value of a
${\mathrm{Lip}}(\gamma,{\cal M},W)$ function
$\phi\in{\mathrm{Lip}}(\gamma,{\cal M},W)$ at a point $p\in{\cal M}$ is
determined by the set $\left\\{\sigma(\phi):\sigma\in{\cal
T}_{p,k}\right\\}\subset{\mathbb{R}}$. The first result records estimates
relating the values $|\delta_{p,0,s}(\phi)|$ for $s\in\\{1,\ldots,c\\}$ to the
value $\left|\left|\phi^{(0)}\right|\right|_{W}$ and, for each
$j\in\\{1,\ldots,k\\}$, the values $|\delta_{p,j,v,s}(\phi)|$ for
$s\in\\{1,\ldots,c\\}$ and $v\in V^{\otimes j}$ to the value
$\left|\left|\phi^{(j)}(v)\right|\right|_{{\cal L}(V^{\otimes j};W)}$. The
precise result is the following lemma.

######  Lemma 5.2 (Linear Functional Inequalities).

Let $c,d\in{\mathbb{Z}}_{\geq 1}$ and assume that $V$ and $W$ are real Banach
spaces of dimensions $d$ and $c$ respectively. Let ${\cal M}\subset V$ be
closed with $p\in{\cal M}$ and assume that the tensor powers of $V$ are all
equipped with admissible norms (cf. Definition 2.1). Let
$v_{1},\ldots,v_{d}\in V$ be a unit $V$-norm basis of $V$. Further, let
$w_{1},\ldots,w_{c}\in W$ be a unit $W$-norm basis of $W$, and let
$w_{1}^{\ast},\ldots,w_{c}^{\ast}\in W^{\ast}$ be the corresponding dual basis
of $W^{\ast}$. Let $\gamma>0$ with $k\in{\mathbb{Z}}_{\geq 0}$ such that
$\gamma\in(k,k+1]$. Given $s\in\\{1,\ldots,c\\}$, $j\in\\{1,\ldots,k\\}$, and
$v\in V^{\otimes j}$, define linear functionals
$\delta_{p,0,s},\delta_{p,j,v,s}\in{\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$
by, for $F=\left(F^{(0)},\ldots,F^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal
M},W)$, setting (cf. (5.15) and (5.16)).

$\delta_{p,0,s}(F):=w_{s}^{\ast}\left(F^{(0)}(p)\right)\qquad\text{and}\qquad\delta_{p,j,v,s}(F):=w_{s}^{\ast}\left(F^{(j)}(p)[v]\right).$
(5.23)

Suppose that
$\phi=\left(\phi^{(0)},\ldots,\phi^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal
M},W)$. Then, for any $s\in\\{1,\ldots,c\\}$, we have that

$\left|\delta_{p,0,s}(\phi)\right|\leq\left|\left|\phi^{(0)}\right|\right|_{W}\leq\sum_{a=1}^{c}\left|\delta_{p,0,a}(\phi)\right|.$
(5.24)

Now suppose that $k\geq 1$ and fix $j\in\\{1,\ldots,k\\}$. Then, for any $v\in
V^{\otimes j}$ and any $s\in\\{1,\ldots,c\\}$, we have that

$\left|\delta_{p,j,v,s}(\phi)\right|\leq\left|\left|\phi^{(j)}(p)[v]\right|\right|_{W}\leq\sum_{a=1}^{c}\left|\delta_{p,j,v,a}(\phi)\right|.$
(5.25)

###### Proof of Lemma 5.2.

Let $c,d\in{\mathbb{Z}}_{\geq 1}$ and assume that $V$ and $W$ are real Banach
spaces of dimensions $d$ and $c$ respectively. Let ${\cal M}\subset V$ be
closed with $p\in{\cal M}$ and assume that the tensor powers of $V$ are all
equipped with admissible norms (cf. Definition 2.1). Let
$v_{1},\ldots,v_{d}\in V$ be a unit $V$-norm basis of $V$. Further, let
$w_{1},\ldots,w_{c}\in W$ be a unit $W$-norm basis of $W$, and let
$w_{1}^{\ast},\ldots,w_{c}^{\ast}\in W^{\ast}$ be the corresponding dual basis
of $W^{\ast}$. Let $\gamma>0$ with $k\in{\mathbb{Z}}_{\geq 0}$ such that
$\gamma\in(k,k+1]$. Given $s\in\\{1,\ldots,c\\}$, $j\in\\{1,\ldots,k\\}$, and
$v\in V^{\otimes j}$, define linear functionals
$\delta_{p,0,s},\delta_{p,j,v,s}\in{\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$
by, for $F=\left(F^{(0)},\ldots,F^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal
M},W)$, setting (cf. (5.23)).

$\delta_{p,0,s}(F):=w_{s}^{\ast}\left(F^{(0)}(p)\right)\qquad\text{and}\qquad\delta_{p,j,v,s}(F):=w_{s}^{\ast}\left(F^{(j)}(p)[v]\right).$
(5.26)

Suppose that
$\phi=\left(\phi^{(0)},\ldots,\phi^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal
M},W)$ and fix $s\in\\{1,\ldots,c\\}$. Then, since
$||w_{1}^{\ast}||_{W^{\ast}}=\ldots=||w_{c}^{\ast}||_{W^{\ast}}=1$, we have

$\left|\delta_{p,0,s}(\phi)\right|=\left|w_{s}^{\ast}\left(\phi^{(0)}(p)\right)\right|\leq\left|\left|\phi^{(0)}(p)\right|\right|_{W}=\\\
\left|\left|\sum_{a=1}^{c}w_{a}^{\ast}\left(\phi^{(0)}(p)\right)w_{a}\right|\right|_{W}\leq\sum_{a=1}^{c}\left|w_{a}^{\ast}\left(\phi^{(0)}(p)\right)\right|=\sum_{a=1}^{c}\left|\delta_{p,0,a}(\phi)\right|.$
(5.27)

The arbitrariness of $s\in\\{1,\ldots,c\\}$ means that the estimates
established in (5.27) are precisely those claimed in (5.24).

Now suppose that $k\geq 1$ and fix $j\in\\{1,\ldots,k\\}$. Fix $v\in
V^{\otimes j}$ and $s\in\\{1,\ldots,c\\}$. Then, again since
$||w_{1}^{\ast}||_{W^{\ast}}=\ldots=||w_{c}^{\ast}||_{W^{\ast}}=1$, we have

$\left|\delta_{p,j,v,s}(\phi)\right|=\left|w_{s}^{\ast}\left(\phi^{(j)}(p)[v]\right)\right|\leq\left|\left|\phi^{(j)}(p)[v]\right|\right|_{W}=\\\
\left|\left|\sum_{a=1}^{c}w_{a}^{\ast}\left(\phi^{(j)}(p)[v]\right)w_{a}\right|\right|_{W}\leq\sum_{a=1}^{c}\left|w_{a}^{\ast}\left(\phi^{(j)}(p)[v]\right)\right|=\sum_{a=1}^{c}\left|\delta_{p,j,v,a}(\phi)\right|.$
(5.28)

The arbitrariness of $j\in\\{1,\ldots,k\\}$, $v\in V^{\otimes j}$, and
$s\in\\{1,\ldots,c\\}$ mean that the estimates established in (5.28) are
precisely those claimed in (5.25). This completes the proof of Lemma 5.2. ∎

We can use the inequalities established in Lemma 5.2 to establish the
following dual norm estimates for linear functionals in ${\cal T}_{p,l}$ (cf.
(5.19)).

######  Lemma 5.3 (Dual Norm Estimates).

Let $c,d\in{\mathbb{Z}}_{\geq 1}$ and assume that $V$ and $W$ are real Banach
spaces of dimensions $d$ and $c$ respectively. Let ${\cal M}\subset V$ be
closed with $p\in{\cal M}$ and assume that the tensor powers of $V$ are all
equipped with admissible norms (cf. Definition 2.1). Let
$v_{1},\ldots,v_{d}\in V$ be a unit $V$-norm basis of $V$. For each integer
$n\in{\mathbb{Z}}_{\geq 1}$ define (cf. (5.3))

${\cal V}_{n}:=\left\\{v_{l_{1}}\otimes\ldots\otimes
v_{l_{n}}:(l_{1},\ldots,l_{n})\in\\{1,\ldots,d\\}^{n}\right\\}\subset
V^{\otimes n}$ (5.29)

and (cf. (5.4))

${\cal V}_{n}^{\operatorname{ord}}:=\left\\{v_{l_{1}}\otimes\ldots\otimes
v_{l_{n}}:(l_{1},\ldots,l_{n})\in\\{1,\ldots,d\\}^{n}\text{ such that
}l_{1}\leq\ldots\leq l_{n}\right\\}\subset{\cal V}_{n}\subset V^{\otimes n}.$
(5.30)

Further, let $w_{1},\ldots,w_{c}\in W$ be a unit $W$-norm basis of $W$, and
let $w_{1}^{\ast},\ldots,w_{c}^{\ast}\in W^{\ast}$ be the corresponding dual
basis of $W^{\ast}$.

Let $\gamma>0$ with $k\in{\mathbb{Z}}_{\geq 0}$ such that $\gamma\in(k,k+1]$.
For a given $j\in\\{0,\ldots,k\\}$, define ${\cal
M}_{p,j}\subset{\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$ by

${\cal
M}_{p,j}:=\left\\{\begin{array}[]{ll}\left\\{\delta_{p,0,s}:s\in\\{1,\ldots,c\\}\right\\}&\mbox{if
}j=0\\\ \left\\{\delta_{p,j,v,s}:v\in{\cal V}_{j}^{\operatorname{ord}}\text{
and }s\in\\{1,\ldots,c\\}\right\\}&\mbox{if }j\geq 1.\end{array}\right.$
(5.31)

For every $s\in\\{1,\ldots,c\\}$, the linear functional
$\delta_{p,0,s}\in{\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$ is defined, for
$F=\left(F^{(0)},\ldots,F^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal M},W)$,
by $\delta_{p,0,s}(F):=w_{s}^{\ast}\left(F^{(0)}(p)\right)$ (cf. (5.15)). For
every $s\in\\{1,\ldots,c\\}$, $j\in\\{1,\ldots,k\\}$, and $v\in{\cal
V}_{j}^{\operatorname{ord}}$, the linear functional
$\delta_{p,j,v,s}\in{\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$ is defined, for
$F=\left(F^{(0)},\ldots,F^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal M},W)$,
by $\delta_{p,j,v,s}(F):=w_{s}^{\ast}\left(F^{(j)}(p)[v]\right)$ (cf. (5.16)).
For a given $l\in\\{0,\ldots,k\\}$ define ${\cal
T}_{p,l}\subset{\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$ by (cf. (5.19))

${\cal T}_{p,l}:=\bigcup_{j=0}^{l}{\cal M}_{p,j}.$ (5.32)

Then for every $\sigma\in{\cal T}_{p,l}$ and any
$\phi\in{\mathrm{Lip}}(\gamma,{\cal M},W)$ we have

$|\sigma(\phi)|\leq\Lambda^{l}_{\phi}(p)\leq||\phi||_{{\mathrm{Lip}}(\gamma,{\cal
M},W)}.$ (5.33)

Consequently, for every $\sigma\in{\cal T}_{p,l}$, we have

$||\sigma||_{{\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}}\leq 1\qquad\text{so
that}\qquad{\cal
T}_{p,l}\subset{\overline{\mathbb{B}}}_{{\mathrm{Lip}}(\gamma,{\cal
M},W)^{\ast}}(0,1).$ (5.34)

###### Proof of Lemma 5.3.

Let $c,d\in{\mathbb{Z}}_{\geq 1}$ and assume that $V$ and $W$ are real Banach
spaces of dimensions $d$ and $c$ respectively. Let ${\cal M}\subset V$ be
closed with $p\in{\cal M}$ and assume that the tensor powers of $V$ are all
equipped with admissible norms (cf. Definition 2.1). Let
$v_{1},\ldots,v_{d}\in V$ be a unit $V$-norm basis of $V$. For each integer
$n\in{\mathbb{Z}}_{\geq 1}$ define (cf. (5.29))

${\cal V}_{n}:=\left\\{v_{l_{1}}\otimes\ldots\otimes
v_{l_{n}}:(l_{1},\ldots,l_{n})\in\\{1,\ldots,d\\}^{n}\right\\}\subset
V^{\otimes n}$ (5.35)

and (cf. (5.30))

${\cal V}_{n}^{\operatorname{ord}}:=\left\\{v_{l_{1}}\otimes\ldots\otimes
v_{l_{n}}:(l_{1},\ldots,l_{n})\in\\{1,\ldots,d\\}^{n}\text{ such that
}l_{1}\leq\ldots\leq l_{n}\right\\}\subset{\cal V}_{n}\subset V^{\otimes n}.$
(5.36)

Further, let $w_{1},\ldots,w_{c}\in W$ be a unit $W$-norm basis of $W$, and
let $w_{1}^{\ast},\ldots,w_{c}^{\ast}\in W^{\ast}$ be the corresponding dual
basis of $W^{\ast}$.

Let $\gamma>0$ with $k\in{\mathbb{Z}}_{\geq 0}$ such that $\gamma\in(k,k+1]$.
For a given $j\in\\{0,\ldots,k\\}$, define ${\cal
M}_{p,j}\subset{\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$ by (cf. (5.31))

${\cal
M}_{p,j}:=\left\\{\begin{array}[]{ll}\left\\{\delta_{p,0,s}:s\in\\{1,\ldots,c\\}\right\\}&\mbox{if
}j=0\\\ \left\\{\delta_{p,j,v,s}:v\in{\cal V}_{j}^{\operatorname{ord}}\text{
and }s\in\\{1,\ldots,c\\}\right\\}&\mbox{if }j\geq 1.\end{array}\right.$
(5.37)

For every $s\in\\{1,\ldots,c\\}$, the linear functional
$\delta_{p,0,s}\in{\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$ is defined, for
$F=\left(F^{(0)},\ldots,F^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal M},W)$,
by $\delta_{p,0,s}(F):=w_{s}^{\ast}\left(F^{(0)}(p)\right)$ (cf. (5.15)). For
every $s\in\\{1,\ldots,c\\}$, $j\in\\{1,\ldots,k\\}$, and $v\in{\cal
V}_{j}^{\operatorname{ord}}$, the linear functional
$\delta_{p,j,v,s}\in{\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$ is defined, for
$F=\left(F^{(0)},\ldots,F^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal M},W)$,
by $\delta_{p,j,v,s}(F):=w_{s}^{\ast}\left(F^{(j)}(p)[v]\right)$ (cf. (5.16)).
For a given $l\in\\{0,\ldots,k\\}$ define ${\cal
T}_{p,l}\subset{\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$ by (cf. (5.32))

${\cal T}_{p,l}:=\bigcup_{j=0}^{l}{\cal M}_{p,j}.$ (5.38)

Now fix $p\in{\cal M}$ and $l\in\\{0,\ldots,k\\}$. Consider $\sigma\in{\cal
T}_{p,l}$. It follows from (5.37) and (5.38) that either
$\sigma=\delta_{p,0,s}$ for some $s\in\\{1,\ldots,c\\}$, or
$\sigma=\delta_{p,j,v,s}$ for some $j\in\\{0,\ldots,l\\}$, some $v\in{\cal
V}_{j}^{\operatorname{ord}}$, and some $s\in\\{1,\ldots,c\\}$.

If $\sigma=\delta_{p,0,s}$ for some $s\in\\{1,\ldots,c\\}$ then, given any
$\phi=\left(\phi^{(0)},\ldots,\phi^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal
M},W)$, we may appeal to Lemma 5.2 to deduce that (cf. (5.24))

$\left|\sigma(\phi)\right|=\left|\delta_{p,0,s}(\phi)\right)\leq\left|\left|\phi^{(0)}(p)\right|\right|_{W}\leq\Lambda^{l}_{\phi}(p)\leq||\phi||_{{\mathrm{Lip}}(\gamma,{\cal
M},W)}.$ (5.39)

If $\sigma=\delta_{p,j,v,s}$ for some $j\in\\{0,\ldots,l\\}$, some $v\in{\cal
V}_{j}^{\operatorname{ord}}$, and some $s\in\\{1,\ldots,c\\}$, then we first
note that $||v||_{V^{\otimes j}}=1$. Thus, given any
$\phi=\left(\phi^{(0)},\ldots,\phi^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal
M},W)$, we may appeal to Lemma 5.2 to deduce that (cf. (5.25))

$\left|\sigma(\phi)\right|=\left|\delta_{p,j,v,s}(\phi)\right|\leq\left|\left|\phi^{(j)}(p)[v]\right|\right|_{W}\leq\left|\left|\phi^{(j)}(p)\right|\right|_{{\cal
L}(V^{\otimes
j};W)}\leq\Lambda^{l}_{\phi}(p)\leq||\phi||_{{\mathrm{Lip}}(\gamma,{\cal
M},W)}.$ (5.40)

Together, (5.39) and (5.40) establish the claim made in (5.33). Since the
${\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$ norm of $\sigma$ is given by
$||\sigma||_{{\mathrm{Lip}}(\gamma,{\cal
M},W)^{\ast}}:=\sup\left\\{|\sigma(\phi)|:\phi\in{\mathrm{Lip}}(\gamma,{\cal
M},W)\text{ with }||\phi||_{{\mathrm{Lip}}(\gamma,{\cal M},W)}=1\right\\}$,
the claims made in (5.34) are an immediate consequence of (5.33). This
completes the proof of Lemma 5.3. ∎

We now use the inequalities established in Lemma 5.2 to establish, for each
$j\in\\{0,\ldots,k\\}$, that the symmetric $j$-linear form from $V$ to $W$
given by $\phi^{(j)}(p)\in{\cal L}(V^{\otimes j};W)$ is determined, in a
quantified sense, by the set real numbers $\left\\{\sigma(\phi):\sigma\in{\cal
M}_{p,j}\right\\}\subset{\mathbb{R}}$ where ${\cal M}_{p,j}$ is defined in
(5.17). The precise result is stated in the following lemma.

######  Lemma 5.4 (Linear Functionals Determine Pointwise Value).

Let $c,d\in{\mathbb{Z}}_{\geq 1}$ and assume that $V$ and $W$ are real Banach
spaces of dimensions $d$ and $c$ respectively. Let ${\cal M}\subset V$ be
closed with $p\in{\cal M}$ and assume that the tensor powers of $V$ are all
equipped with admissible norms (cf. Definition 2.1). Let
$v_{1},\ldots,v_{d}\in V$ be a unit $V$-norm basis of $V$. For each integer
$n\in{\mathbb{Z}}_{\geq 1}$ define (cf. (5.3))

${\cal V}_{n}:=\left\\{v_{l_{1}}\otimes\ldots\otimes
v_{l_{n}}:(l_{1},\ldots,l_{n})\in\\{1,\ldots,d\\}^{n}\right\\}\subset
V^{\otimes n}$ (5.41)

and (cf. (5.4))

${\cal V}_{n}^{\operatorname{ord}}:=\left\\{v_{l_{1}}\otimes\ldots\otimes
v_{l_{n}}:(l_{1},\ldots,l_{n})\in\\{1,\ldots,d\\}^{n}\text{ such that
}l_{1}\leq\ldots\leq l_{n}\right\\}\subset{\cal V}_{n}\subset V^{\otimes n}.$
(5.42)

Further, let $w_{1},\ldots,w_{c}\in W$ be a unit $W$-norm basis of $W$, and
let $w_{1}^{\ast},\ldots,w_{c}^{\ast}\in W^{\ast}$ be the corresponding dual
basis of $W^{\ast}$.

Let $\gamma>0$ with $k\in{\mathbb{Z}}_{\geq 0}$ such that $\gamma\in(k,k+1]$.
For a given $j\in\\{0,\ldots,k\\}$, define ${\cal
M}_{p,j}\subset{\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$ by

${\cal
M}_{p,j}:=\left\\{\begin{array}[]{ll}\left\\{\delta_{p,0,s}:s\in\\{1,\ldots,c\\}\right\\}&\mbox{if
}j=0\\\ \left\\{\delta_{p,j,v,s}:v\in{\cal V}_{j}^{\operatorname{ord}}\text{
and }s\in\\{1,\ldots,c\\}\right\\}&\mbox{if }j\geq 1.\end{array}\right.$
(5.43)

For every $s\in\\{1,\ldots,c\\}$, the linear functional
$\delta_{p,0,s}\in{\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$ is defined, for
$F=\left(F^{(0)},\ldots,F^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal M},W)$,
by $\delta_{p,0,s}(F):=w_{s}^{\ast}\left(F^{(0)}(p)\right)$ (cf. (5.15)). For
every $s\in\\{1,\ldots,c\\}$, $j\in\\{1,\ldots,k\\}$, and $v\in{\cal
V}_{j}^{\operatorname{ord}}$, the linear functional
$\delta_{p,j,v,s}\in{\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$ is defined, for
$F=\left(F^{(0)},\ldots,F^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal M},W)$,
by $\delta_{p,j,v,s}(F):=w_{s}^{\ast}\left(F^{(j)}(p)[v]\right)$ (cf. (5.16)).

Suppose that $A\geq 0$ and
$\phi=\left(\phi^{(0)},\ldots,\phi^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal
M},W)$. Then for any $j\in\\{0,\ldots,k\\}$ we have that the following
implications are valid. Firstly,

$\left|\left|\phi^{(j)}(p)\right|\right|_{{\cal L}(V^{\otimes j};W)}\leq
A\implies\max\left\\{|\sigma(\phi)|:\sigma\in{\cal M}_{p,j}\right\\}\leq A.$
(5.44)

Secondly,

$\max\left\\{|\sigma(\phi)|:\sigma\in{\cal M}_{p,j}\right\\}\leq
A\implies\left|\left|\phi^{(j)}(p)\right|\right|_{{\cal L}(V^{\otimes
j};W)}\leq cd^{j}A.$ (5.45)

Consequently, in the case that $A=0$, the combination of (5.44) and (5.45)
yields that

$\phi^{(j)}(p)\equiv 0\text{ in }{\cal L}(V^{\otimes
j};W)\qquad\iff\qquad\max\left\\{|\sigma(\phi)|:\sigma\in{\cal
M}_{p,j}\right\\}=0.$ (5.46)

###### Proof of Lemma 5.4.

Let $c,d\in{\mathbb{Z}}_{\geq 1}$ and assume that $V$ and $W$ are real Banach
spaces of dimensions $d$ and $c$ respectively. Let ${\cal M}\subset V$ be
closed with $p\in{\cal M}$ and assume that the tensor powers of $V$ are all
equipped with admissible norms (cf. Definition 2.1). Let
$v_{1},\ldots,v_{d}\in V$ be a unit $V$-norm basis of $V$. For each integer
$n\in{\mathbb{Z}}_{\geq 1}$ define (cf. (5.41))

${\cal V}_{n}:=\left\\{v_{l_{1}}\otimes\ldots\otimes
v_{l_{n}}:(l_{1},\ldots,l_{n})\in\\{1,\ldots,d\\}^{n}\right\\}\subset
V^{\otimes n}$ (5.47)

and (cf. (5.42))

${\cal V}_{n}^{\operatorname{ord}}:=\left\\{v_{l_{1}}\otimes\ldots\otimes
v_{l_{n}}:(l_{1},\ldots,l_{n})\in\\{1,\ldots,d\\}^{n}\text{ such that
}l_{1}\leq\ldots\leq l_{n}\right\\}\subset{\cal V}_{n}\subset V^{\otimes n}.$
(5.48)

A consequence of the tensor powers of $V$ being equipped with admissible norms
in the sense of Definition 2.1 is that ${\cal V}_{n}\subset V^{\otimes}$ is a
unit $V^{\otimes n}$-norm basis of $V^{\otimes n}$. Further, let
$w_{1},\ldots,w_{c}\in W$ be a unit $W$-norm basis of $W$, and let
$w_{1}^{\ast},\ldots,w_{c}^{\ast}\in W^{\ast}$ be the corresponding dual basis
of $W^{\ast}$.

Let $\gamma>0$ with $k\in{\mathbb{Z}}_{\geq 0}$ such that $\gamma\in(k,k+1]$.
For a given $j\in\\{0,\ldots,k\\}$, define ${\cal
M}_{p,j}\subset{\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$ by (cf. (5.43))

${\cal
M}_{p,j}:=\left\\{\begin{array}[]{ll}\left\\{\delta_{p,0,s}:s\in\\{1,\ldots,c\\}\right\\}&\mbox{if
}j=0\\\ \left\\{\delta_{p,j,v,s}:v\in{\cal V}_{j}^{\operatorname{ord}}\text{
and }s\in\\{1,\ldots,c\\}\right\\}&\mbox{if }j\geq 1.\end{array}\right.$
(5.49)

For every $s\in\\{1,\ldots,c\\}$, the linear functional
$\delta_{p,0,s}\in{\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$ is defined, for
$F=\left(F^{(0)},\ldots,F^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal M},W)$,
by $\delta_{p,0,s}(F):=w_{s}^{\ast}\left(F^{(0)}(p)\right)$ (cf. (5.15)). For
every $s\in\\{1,\ldots,c\\}$, $j\in\\{1,\ldots,k\\}$, and $v\in V^{\otimes
j}$, the linear functional $\delta_{p,j,v,s}\in{\mathrm{Lip}}(\gamma,{\cal
M},W)^{\ast}$ is defined, for
$F=\left(F^{(0)},\ldots,F^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal M},W)$,
by $\delta_{p,j,v,s}(F):=w_{s}^{\ast}\left(F^{(j)}(p)[v]\right)$ (cf. (5.16)).

Suppose that
$\phi=\left(\phi^{(0)},\ldots,\phi^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal
M},W)$. Observe that if (5.44) and (5.45) are both valid for any $A\geq 0$,
then the equivalence claimed in (5.46) is an immediate consequence of invoking
both for the particular choice of $A:=0$. Thus we need only verify that both
the implications (5.44) and (5.45) are valid for any $A\geq 0$. Thus, for the
remainder of the proof, we fix an arbitrary choice of $A\geq 0$.

We begin with the case that $j=0$ so that (cf. (5.49)) ${\cal
M}_{p,0}=\left\\{\delta_{p,0,s}:s\in\\{1,\ldots,c\\}\right\\}\subset{\mathrm{Lip}}(\gamma,{\cal
M},W)^{\ast}$. By appealing to Lemma 5.2 we may conclude that, for each
$s\in\\{1,\ldots,c\\}$, we have (cf. (5.24))

$\left|\delta_{p,0,s}(\phi)\right|\leq\left|\left|\phi^{(0)}(p)\right|\right|_{W}\leq\sum_{a=1}^{c}\left|\delta_{p,0,s}(\phi)\right|.$
(5.50)

If $\left|\left|\phi^{(0)}(p)\right|\right|_{W}\leq A$ then, for any
$s\in\\{1,\ldots,c\\}$, a consequence of (5.50) is that
$|\delta_{p,0,s}(\phi)|\leq A$. Therefore, since ${\cal
M}_{p,0}=\left\\{\delta_{p,0,s}:s\in\\{1,\ldots,c\\}\right\\}$, we deduce that
$\max\left\\{|\sigma(\phi)|:\sigma\in{\cal M}_{p,0}\right\\}\leq A$. Thus,
recalling that ${\cal L}(V^{\otimes 0};W)=W$ and we choose to equip this space
with the norm $||\cdot||_{W}$ on $W$ (cf. Remark 2.3), the implication claimed
in (5.44) is valid when $j=0$.

If $\max\left\\{|\sigma(\phi)|:\sigma\in{\cal M}_{p,0}\right\\}\leq A$, then
since ${\cal M}_{p,0}=\left\\{\delta_{p,0,s}:s\in\\{1,\ldots,c\\}\right\\}$ we
have, for every $s\in\\{1,\ldots,c\\}$, that
$\left|\delta_{p,0,s}(\phi)\right|\leq A$. Therefore, via an application of
(5.50), it follows that $\left|\left|\phi^{(0)}(p)\right|\right|_{W}\leq cA$.
Thus, recalling that ${\cal L}(V^{\otimes 0};W)=W$ and we choose to equip this
space with the norm $||\cdot||_{W}$ on $W$ (cf. Remark 2.3), the implication
claimed in (5.45) is valid when $j=0$.

Hence we have established that the lemma is true when $j=0$.

We next establish that the lemma is true when $j=1$. In this case, since
${\cal V}_{1}^{\operatorname{ord}}={\cal V}_{1}$, we have ${\cal
M}_{p,1}=\left\\{\delta_{p,1,v,s}:v\in{\cal V}_{1}\text{ and
}s\in\\{1,\ldots,c\\}\right\\}\subset{\mathrm{Lip}}(\gamma,{\cal
M},W)^{\ast}$. Given $v\in{\cal V}_{1}$ and $s\in\\{1,\ldots,c\\}$, we can
appeal to Lemma 5.2 to conclude that (cf. (5.25))

$\left|\delta_{p,1,v,s}(\phi)\right|\leq\left|\left|\phi^{(1)}(p)[v]\right|\right|_{W}\leq\sum_{a=1}^{c}\left|\delta_{p,1,v,a}(\phi)\right|.$
(5.51)

If $\left|\left|\phi^{(1)}(p)\right|\right|_{{\cal L}(V;W)}\leq A$ then, since
$v\in{\cal V}_{1}$ means $||v||_{V}=1$, it follows from (5.51) that
$\left|\delta_{p,1,v,s}(\phi)\right|\leq A$. The arbitrariness of $v\in{\cal
V}_{1}$ and $s\in\\{1,\ldots,c\\}$ means we can deduce that
$\max\left\\{\left|\sigma(\phi)\right|:\sigma\in{\cal M}_{p,1}\right\\}\leq
A$. Thus the implication (5.44) is valid when $j=1$.

If $\max\left\\{\left|\sigma(\phi)\right|:\sigma\in{\cal M}_{p,1}\right\\}\leq
A$ then, for every $v\in{\cal V}_{1}$ and $s\in\\{1,\ldots,c\\}$, we have that
$\left|\delta_{p,1,v,s}(\phi)\right|\leq A$. Now suppose that $v\in V$ with
$||v||_{V}=1$. Then, since ${\cal V}_{1}$ is a basis of $V$, there are
coefficients $b_{1},\ldots,b_{d}\in{\mathbb{R}}$ such that
$v=\sum_{m=1}^{d}b_{m}v_{m}$. Moreover, by appealing to Lemma 5.1, we have
(cf. (5.7) for $m=1$) that $\sum_{j=m}^{d}|b_{m}|\leq d$. Therefore, via an
application of (5.51), we have

$\left|\left|\phi^{(1)}(p)[v]\right|\right|_{W}\leq\sum_{m=1}^{d}|b_{m}|\left|\left|\phi^{(1)}(p)[v_{m}]\right|\right|_{W}\stackrel{{\scriptstyle{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}({\ref{eq:de_1_ests_B}})}}}{{\leq}}\sum_{m=1}^{d}|b_{m}|\sum_{a=1}^{c}\left|\delta_{p,1,v_{m},a}(\phi)\right|\leq\sum_{m=1}^{d}|b_{m}|\sum_{a=1}^{c}A\leq
cdA.$ (5.52)

By taking the supremum over $v\in V$ with $||v||_{V}=1$ in (5.52), we obtain
that $\left|\left|\phi^{(1)}(p)\right|\right|_{{\cal L}(V;W)}\leq cdA$. Thus
the implication (5.45) is valid when $j=1$.

Hence we have established that the lemma is true when $j=1$.

We complete the proof by establishing that, when $k\geq 2$, the lemma is true
for an arbitrary fixed $j\in{\mathbb{Z}}_{\geq 2}$. In this case, we have
${\cal M}_{p,j}=\left\\{\delta_{p,j,v,s}:v\in{\cal
V}^{\operatorname{ord}}_{j}\text{ and
}s\in\\{1,\ldots,c\\}\right\\}\subset{\mathrm{Lip}}(\gamma,{\cal
M},W)^{\ast}$. Given $v\in{\cal V}^{\operatorname{ord}}_{j}$ and
$s\in\\{1,\ldots,c\\}$, we can appeal to Lemma 5.2 to conclude that (cf.
(5.25))

$\left|\delta_{p,j,v,s}(\phi)\right|\leq\left|\left|\phi^{(j)}(p)[v]\right|\right|_{W}\leq\sum_{a=1}^{c}\left|\delta_{p,j,v,a}(\phi)\right|.$
(5.53)

If $\left|\left|\phi^{(j)}(p)\right|\right|_{{\cal L}(V^{\otimes j};W)}\leq
A$, since $v\in{\cal V}_{j}^{\operatorname{ord}}$ means $||v||_{V^{\otimes
j}}=1$, it follows from (5.53) that $\left|\delta_{p,j,v,s}(\phi)\right|\leq
A$. The arbitrariness of both $v\in{\cal V}_{j}^{\operatorname{ord}}$ and
$s\in\\{1,\ldots,c\\}$ means we can deduce that
$\max\left\\{|\sigma(\phi)|:\sigma\in{\cal M}_{p,j}\right\\}\leq A$. Thus the
implication (5.44) is valid for arbitrary $j\in{\mathbb{Z}}_{\geq 2}$.

Now suppose that $\max\left\\{|\sigma(\phi)|:\sigma\in{\cal
M}_{p,j}\right\\}\leq A$. We first claim that this means, given any $v\in{\cal
V}_{j}$ and any $s\in\\{1,\ldots,c\\}$, that
$\left|\delta_{p,j,v,s}(\phi)\right|\leq A$. Indeed, if $v\in{\cal
V}_{j}^{\operatorname{ord}}\subset{\cal V}_{j}$ then this is an immediate
consequence of the definition of ${\cal M}_{p,j}$. And it follows for general
$v\in{\cal V}_{j}$ as follows. Fix $v\in{\cal V}_{j}$ and
$s\in\\{1,\ldots,c\\}$. Then there exists a permutation $\rho\in S_{j}$ such
that $\rho(v)\in{\cal V}_{j}^{\operatorname{ord}}$; see Definition 2.1 for the
details of how the permutation group $S_{j}$ acts on the tensor product
$V^{\otimes j}$. But $\phi^{(j)}(p)\in{\cal L}(V^{\otimes j};W)$ is a
$j$-symmetric linear form from $V$ to $W$; so, in particular,
$\phi^{(j)}(p)[\rho(v)]=\phi^{(j)}(p)[v]$. Hence
$\delta_{p,j,v,s}(\phi)=\delta_{p,j,\rho(v),s}(\phi)$ from which it is
immediate that $\left|\delta_{p,j,v,s}(\phi)\right|\leq A$ as claimed.

Let $v\in V^{\otimes j}$ with $||v||_{V^{\otimes j}}=1$. Then, by appealing to
Lemma 5.1, we have that there are coefficients $\left\\{C_{l_{1}\dots
l_{j}}:(l_{1},\ldots,l_{j})\in\\{1,\ldots,d\\}^{j}\right\\}$ for which (cf.
(5.6))

$v=\sum_{l_{1}=1}^{d}\ldots\sum_{l_{j}=1}^{d}C_{l_{1}\dots
l_{j}}v_{l_{1}}\otimes\ldots\otimes v_{l_{j}},$ (5.54)

and such that (cf. (5.7) for $A$ there as $1$)

$\sum_{l_{1}=1}^{d}\dots\sum_{l_{j}=1}^{d}\left|C_{l_{1}\dots
l_{j}}\right|\leq d^{j}.$ (5.55)

Consequently, via an application of (5.53), we have

$\left|\left|\phi^{(j)}(p)[v]\right|\right|_{W}\leq\sum_{l_{1}}^{d}\dots\sum_{l_{j}=1}^{d}\left|C_{l_{1}\dots
l_{j}}\right|\left|\left|\phi^{(j)}(p)\left[v_{l_{1}}\otimes\ldots\otimes
v_{l_{j}}\right]\right|\right|_{W}\\\
\stackrel{{\scriptstyle{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}({\ref{eq:de_j_ests_B}})}}}{{\leq}}\sum_{l_{1}}^{d}\dots\sum_{l_{j}=1}^{d}\left|C_{l_{1}\dots
l_{j}}\right|\sum_{a=1}^{c}\left|\delta_{p,j,v_{l_{1}}\otimes\ldots\otimes
v_{l_{j}},a}(\phi)\right|\leq
cA\sum_{l_{1}}^{d}\dots\sum_{l_{j}=1}^{d}\left|C_{l_{1}\dots
l_{j}}\right|\stackrel{{\scriptstyle{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}({\ref{coeff_sum_bound_level_j}})}}}{{\leq}}cd^{j}A.$
(5.56)

By taking the supremum over $v\in V^{\otimes j}$ with $||v||_{V^{\otimes
j}}=1$ in (5.56), we obtain that
$\left|\left|\phi^{(j)}(p)\right|\right|_{{\cal L}(V^{\otimes j};W)}\leq
cd^{j}A$. Thus the implication (5.45) is valid for arbitrary
$j\in{\mathbb{Z}}_{\geq 2}$. This completes the proof of Lemma 5.4. ∎

We conclude this section by using Lemma 5.4 to establish that the value of a
${\mathrm{Lip}}(\gamma)$ function $\phi\in{\mathrm{Lip}}(\gamma,{\cal M},W)$
at a point $p\in{\cal M}$ is determined, in a quantified sense, by the set of
real numbers $\left\\{\sigma(\phi):\sigma\in{\cal
T}_{p,k}\right\\}\subset{\mathbb{R}}$ where ${\cal T}_{p,k}$ is defined in
(5.19). The precise result is stated in the following lemma.

######  Lemma 5.5 (Determining Lipschitz Functions at Points).

Let $c,d\in{\mathbb{Z}}_{\geq 1}$ and $V$ and $W$ be real Banach spaces of
dimensions $d$ and $c$ respectively. Let ${\cal M}\subset V$ be a closed
subset, and assume that the tensor powers of $V$ are all equipped with
admissible norms (cf. Definition 2.1). Let $v_{1},\ldots,v_{d}\in V$ be a unit
$V$-norm basis of $V$. For each integer $n\in{\mathbb{Z}}_{\geq 1}$ define
(cf. (5.3))

${\cal V}_{n}:=\left\\{v_{l_{1}}\otimes\ldots\otimes
v_{l_{n}}:(l_{1},\ldots,l_{n})\in\\{1,\ldots,d\\}^{n}\right\\}\subset
V^{\otimes n}$ (5.57)

and (cf. (5.4))

${\cal V}_{n}^{\operatorname{ord}}:=\left\\{v_{l_{1}}\otimes\ldots\otimes
v_{l_{n}}:(l_{1},\ldots,l_{n})\in\\{1,\ldots,d\\}^{n}\text{ such that
}l_{1}\leq\ldots\leq l_{n}\right\\}\subset{\cal V}_{n}\subset V^{\otimes n}.$
(5.58)

Further, let $w_{1},\ldots,w_{c}\in W$ be a unit $W$-norm basis of $W$, and
let $w_{1}^{\ast},\ldots,w_{c}^{\ast}\in W^{\ast}$ be the corresponding dual
basis of $W^{\ast}$.

Let $\gamma>0$ with $k\in{\mathbb{Z}}_{\geq 0}$ such that $\gamma\in(k,k+1]$,
and let
$\phi=\left(\phi^{(0)},\ldots,\phi^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal
M},W)$. For each point $p\in{\cal M}$ and each $j\in\\{0,\ldots,k\\}$ define
${\cal M}_{p,j}\subset{\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$ by

${\cal
M}_{p,j}:=\left\\{\begin{array}[]{ll}\left\\{\delta_{p,0,s}:s\in\\{1,\ldots,c\\}\right\\}&\mbox{if
}j=0\\\ \left\\{\delta_{p,j,v,s}:v\in{\cal V}_{j}^{\operatorname{ord}}\text{
and }s\in\\{1,\ldots,c\\}\right\\}&\mbox{if }j\geq 1.\end{array}\right.$
(5.59)

For every $s\in\\{1,\ldots,c\\}$, the linear functional
$\delta_{p,0,s}\in{\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$ is defined, for
$F=\left(F^{(0)},\ldots,F^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal M},W)$,
by $\delta_{p,0,s}(F):=w_{s}^{\ast}\left(F^{(0)}(p)\right)$ (cf. (5.15)). For
every $s\in\\{1,\ldots,c\\}$, $j\in\\{1,\ldots,k\\}$, and $v\in{\cal
V}_{j}^{\operatorname{ord}}$, the linear functional
$\delta_{p,j,v,s}\in{\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$ is defined, for
$F=\left(F^{(0)},\ldots,F^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal M},W)$,
by $\delta_{p,j,v,s}(F):=w_{s}^{\ast}\left(F^{(j)}(p)[v]\right)$ (cf. (5.16)).
Further, for a given $l\in\\{0,\ldots,k\\}$, define ${\cal
T}_{p,l}\subset{\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$ by

${\cal T}_{p,l}:=\bigcup_{j=0}^{l}{\cal M}_{p,j}.$ (5.60)

Recall the notation introduced in Remark 2.8 that, for each point $x\in{\cal
M}$ and each $j\in\\{0,\ldots,k\\}$, we set

$\Lambda_{\phi}^{j}(x):=\max_{s\in\\{0,\ldots,j\\}}\left\\{\left|\left|\phi^{(s)}(x)\right|\right|_{{\cal
L}(V^{\otimes s};W)}\right\\}.$ (5.61)

Then, given $A\geq 0$ and $l\in\\{0,\ldots,k\\}$, the following implications
are valid. Firstly,

$\Lambda_{\phi}^{l}(p)\leq A\implies\max\left\\{|\sigma(\phi)|:\sigma\in{\cal
T}_{p,l}\right\\}\leq A.$ (5.62)

Secondly,

$\max\left\\{|\sigma(\phi)|:\sigma\in{\cal T}_{p,l}\right\\}\leq
A\implies\Lambda_{\phi}^{l}(p)\leq cd^{l}A.$ (5.63)

Consequently, in the case that $A=0$, the combination of (5.62) and (5.63)
yields that

$\Lambda_{\phi}^{l}(p)=0\iff\max\left\\{|\sigma(\phi)|:\sigma\in{\cal
T}_{p,l}\right\\}=0.$ (5.64)

Therefore the condition that
$\phi(p)=\left(\phi^{(0)}(p),\ldots,\phi^{(k)}(p)\right)$ vanishes at
$p\in{\cal M}$ is equivalent to the system of equations generated by
requiring, for every $\sigma\in{\cal T}_{p,k}$, that $\sigma(\phi)=0$; that
is, to a system of

$\\#\left({\cal T}_{p,k}\right)=c\sum_{j=0}^{k}\beta(d,j)$ (5.65)

real valued equations. Here, for integers $a,b\in{\mathbb{Z}}_{\geq 0}$,
$\beta(a,b)$ is defined by (cf. (5.1))

$\beta(a,b):=\left(\begin{array}[]{c}a+b-1\\\
b\end{array}\right)=\frac{(a+b-1)!}{(a-1)!b!}=\left\\{\begin{array}[]{ll}1&\mbox{if
}b=0\\\ \frac{1}{b!}\prod_{s=0}^{b-1}(a+s)&\mbox{if }b\geq
1.\end{array}\right.$ (5.66)

###### Proof of Lemma 5.5.

Let $c,d\in{\mathbb{Z}}_{\geq 1}$ and $V$ and $W$ be real Banach spaces of
dimensions $d$ and $c$ respectively. Let ${\cal M}\subset V$ be a closed
subset, and assume that the tensor powers of $V$ are all equipped with
admissible norms (cf. Definition 2.1). Let $v_{1},\ldots,v_{d}\in V$ be a unit
$V$-norm basis of $V$. For each integer $n\in{\mathbb{Z}}_{\geq 1}$ define
(cf. (5.57))

${\cal V}_{n}:=\left\\{v_{l_{1}}\otimes\ldots\otimes
v_{l_{n}}:(l_{1},\ldots,l_{n})\in\\{1,\ldots,d\\}^{n}\right\\}\subset
V^{\otimes n}$ (5.67)

and (cf. (5.58))

${\cal V}_{n}^{\operatorname{ord}}:=\left\\{v_{l_{1}}\otimes\ldots\otimes
v_{l_{n}}:(l_{1},\ldots,l_{n})\in\\{1,\ldots,d\\}^{n}\text{ such that
}l_{1}\leq\ldots\leq l_{n}\right\\}\subset{\cal V}_{n}\subset V^{\otimes n}.$
(5.68)

Further, let $w_{1},\ldots,w_{c}\in W$ be a unit $W$-norm basis of $W$, and
let $w_{1}^{\ast},\ldots,w_{c}^{\ast}\in W^{\ast}$ be the corresponding dual
basis of $W^{\ast}$.

Let $\gamma>0$ with $k\in{\mathbb{Z}}_{\geq 0}$ such that $\gamma\in(k,k+1]$,
and let
$\phi=\left(\phi^{(0)},\ldots,\phi^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal
M},W)$. For each point $p\in{\cal M}$ and each $j\in\\{0,\ldots,k\\}$ define
${\cal M}_{p,j}\subset{\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$ by (cf.
(5.59))

${\cal
M}_{p,j}:=\left\\{\begin{array}[]{ll}\left\\{\delta_{p,0,s}:s\in\\{1,\ldots,c\\}\right\\}&\mbox{if
}j=0\\\ \left\\{\delta_{p,j,v,s}:v\in{\cal V}_{j}^{\operatorname{ord}}\text{
and }s\in\\{1,\ldots,c\\}\right\\}&\mbox{if }j\geq 1.\end{array}\right.$
(5.69)

For every $s\in\\{1,\ldots,c\\}$, the linear functional
$\delta_{p,0,s}\in{\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$ is defined, for
$F=\left(F^{(0)},\ldots,F^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal M},W)$,
by $\delta_{p,0,s}(F):=w_{s}^{\ast}\left(F^{(0)}(p)\right)$ (cf. (5.15)). For
every $s\in\\{1,\ldots,c\\}$, $j\in\\{1,\ldots,k\\}$, and $v\in{\cal
V}_{j}^{\operatorname{ord}}$, the linear functional
$\delta_{p,j,v,s}\in{\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$ is defined, for
$F=\left(F^{(0)},\ldots,F^{(k)}\right)\in{\mathrm{Lip}}(\gamma,{\cal M},W)$,
by $\delta_{p,j,v,s}(F):=w_{s}^{\ast}\left(F^{(j)}(p)[v]\right)$ (cf. (5.16)).
Further, for a given $l\in\\{0,\ldots,k\\}$, define ${\cal
T}_{p,l}\subset{\mathrm{Lip}}(\gamma,{\cal M},W)^{\ast}$ by (cf. (5.60))

${\cal T}_{p,l}:=\bigcup_{j=0}^{l}{\cal M}_{p,j}.$ (5.70)

Recall the notation introduced in Remark 2.8 that, for each point $x\in{\cal
M}$ and each $j\in\\{0,\ldots,k\\}$, we set (cf. (5.61))

$\Lambda_{\phi}^{j}(x):=\max_{s\in\\{0,\ldots,j\\}}\left\\{\left|\left|\phi^{(s)}(x)\right|\right|_{{\cal
L}(V^{\otimes s};W)}\right\\}.$ (5.71)

We now turn our attention to verifying that both the implications (5.62) and
(5.63) are valid. For this purpose let $A\geq 0$ and fix
$l\in\\{0,\ldots,k\\}$.

First assume that $\Lambda_{\phi}^{l}(p)\leq A$. A consequence of (5.71) is
that, for every $j\in\\{0,\ldots,l\\}$, we have the bound
$\left|\left|\phi^{(j)}(p)\right|\right|_{{\cal L}(V^{\otimes j};W)}\leq A$.
In turn, by appealing to Lemma 5.4, we deduce, for every
$j\in\\{0,\ldots,l\\}$, that (cf. (5.44))
$\max\left\\{|\sigma(\phi)|:\sigma\in{\cal M}_{p,j}\right\\}\leq A$. It now
follows from (5.70) that $\max\left\\{|\sigma(\phi)|:\sigma\in{\cal
T}_{p,l}\right\\}\leq A$. Thus the implication (5.62) is valid as claimed. We
could alternatively have established (5.62) via use of the inequality (5.33)
established in Lemma 5.3.

Now assume that $\max\left\\{|\sigma(\phi)|:\sigma\in{\cal
T}_{p,l}\right\\}\leq A$. A consequence of (5.70) is that, for every
$j\in\\{0,\ldots,l\\}$, we have $\max\left\\{|\sigma(\phi)|:\sigma\in{\cal
M}_{p,j}\right\\}\leq A$. In turn, by appealing to Lemma 5.4, we deduce, for
every $j\in\\{0,\ldots,l\\}$, that (cf. (5.45))
$\left|\left|\phi^{(j)}(p)\right|\right|_{{\cal L}(V^{\otimes j};W)}\leq
cd^{j}A$. It now follows from (5.71) that $\Lambda_{\phi}^{l}(p)\leq cd^{l}A$.
Thus the implication (5.63) is valid as claimed.

The combination of the implication (5.62) for $A:=0$ and the implication
(5.63) for $A:=0$ yield that $\Lambda_{\phi}^{l}(p)=0$ if and only if
$\max\left\\{|\sigma(\phi)|:\sigma\in{\cal T}_{p,l}\right\\}=0$ as claimed in
(5.64).

To complete the proof, we consider imposing the condition that $\phi$ vanishes
at the point $p$. In particular, this is equivalent to having, for every
$j\in\\{0,\ldots,k\\}$, that $\left|\left|\phi^{(j)}(p)\right|\right|_{{\cal
L}(V^{\otimes j};W)}=0$. Consequently, by appealing to (5.64), this is
equivalent to having, for every $\sigma\in{\cal T}_{p,k}$, that
$\sigma(\phi)=0$. This is a system of $\\#\left({\cal T}_{p,k}\right)$ real-
valued equations. The proof will be complete if we can establish that
$\\#\left({\cal T}_{p,k}\right)=c\sum_{j=0}^{k}\beta(d,j)$ as claimed in
(5.65) where, for integers $a,b\in{\mathbb{Z}}_{\geq 0}$, $\beta(a,b)$ is
given by (cf. (5.66))

$\beta(a,b):=\left(\begin{array}[]{c}a+b-1\\\
b\end{array}\right)=\frac{(a+b-1)!}{(a-1)!b!}=\left\\{\begin{array}[]{ll}1&\mbox{if
}b=0\\\ \frac{1}{b!}\prod_{s=0}^{b-1}(a+s)&\mbox{if }b\geq
1.\end{array}\right.$ (5.72)

We first note via (5.70) that $\\#\left({\cal
T}_{p,k}\right)=\sum_{j=0}^{k}\\#\left({\cal M}_{p,j}\right)$. Moreover, for
each $j\in\\{0,\ldots,k\\}$, it follows from (5.69) that

$\\#\left({\cal M}_{p,j}\right):=\left\\{\begin{array}[]{ll}c&\mbox{if }j=0\\\
c\\#\left({\cal V}_{j}^{\operatorname{ord}}\right)&\mbox{if }j\geq
1\end{array}\right.\stackrel{{\scriptstyle{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}({\ref{eq:beta_ab_def_pf}})}}}{{=}}c\beta(d,j).$
(5.73)

Hence $\\#\left({\cal T}_{p,k}\right)=c\sum_{j=0}^{k}\beta(d,j)$ as claimed in
(5.65). This completes the proof of Lemma 5.5. ∎

##  6 The HOLGRIM Algorithm

The following HOLGRIM Extension Step is used to dynamically grow the
collection of points $P\subset\Sigma$ at which we require our next
approximation of $\varphi$ to agree with $\varphi$. HOLGRIM Extension Step

Assume $P^{\prime}\subset\Sigma$. Let $u\in\operatorname{Span}({\cal F})$. Let
$q\in\\{0,\ldots,k\\}$ and $m\in{\mathbb{Z}}_{\geq 1}$ such that
$\\#(P^{\prime})+m\leq\Lambda:=\\#(\Sigma)$.

$\Sigma_{q}^{\ast}:=\bigcup_{z\in\Sigma}{\cal
T}_{z,q}\subset{\mathrm{Lip}}(\gamma,\Sigma,W)^{\ast}.$ (6.1)

First take

$\sigma_{1}:=\operatorname{argmax}\left\\{\left|\sigma(\varphi-u)\right|:\sigma\in\Sigma_{q}^{\ast}\right\\},$
(6.2)

and then take $z_{1}\in\Sigma$ to be the point for which $\sigma_{1}\in{\cal
T}_{z_{1},q}$.

Inductively for $j=2,3,\ldots,m$ take

$\sigma_{j}:=\operatorname{argmax}\left\\{\left|\sigma(\varphi-u)\right|:\sigma\in\Sigma_{q}^{\ast}\setminus\bigcup_{s=1}^{j-1}{\cal
T}_{z_{s},q}\right\\}$ (6.3)

and then take $z_{j}\in\Sigma$ to be the point for which $\sigma_{j}\in{\cal
T}_{z_{j},q}$.

Once $z_{1},\ldots,z_{m}\in\Sigma$ have been defined, we extend $P^{\prime}$
to $P:=P^{\prime}\cup\left\\{z_{1},\ldots,z_{m}\right\\}$. The following
HOLGRIM Recombination Step details how, for a given subset $P\subset\Sigma$
and a given $\varepsilon_{0}\geq 0$, we use recombination to find a function
$u\in\operatorname{Span}({\cal F})$ satisfying, for every point $z\in P$, that
$\Lambda^{k}_{\varphi-u}(z)\leq\varepsilon_{0}$. HOLGRIM Recombination Step

Assume $P\subset\Sigma$ with $m\in{\mathbb{Z}}_{\geq 1}$ such that
$m=\\#\left(P\right)$. For integers $a,b\in{\mathbb{Z}}_{\geq 1}$, let
$\beta(a,b)$ be as defined in (5.1). That is,

$\beta(a,b):=\left(\begin{array}[]{c}a+b-1\\\
b\end{array}\right)=\frac{(a+b-1)!}{(a-1)!b!}=\left\\{\begin{array}[]{ll}1&\mbox{if
}b=0\\\ \frac{1}{b!}\prod_{s=0}^{b-1}(a+s)&\mbox{if }b\geq
1.\end{array}\right.$ (6.4)

Let $Q=Q(m,c,d,k)\in{\mathbb{Z}}_{\geq 1}$ be as defined in (5.2). That is,

$Q:=1+mc\sum_{r=0}^{k}\beta(d,r).$ (6.5)

Let $s\in{\mathbb{Z}}_{\geq 1}$, $q\in\\{0,\ldots,k\\}$ and define
$\Sigma_{q}^{\ast}:=\cup_{z\in\Sigma}{\cal T}_{p,q}$. For each
$j\in\\{1,\ldots,s\\}$ we do the following.

  1. (A)

Define $L(k)\subset{\mathrm{Lip}}(\gamma,\Sigma,W)^{\ast}$ by

$L(k):=\bigcup_{z\in P}{\cal
T}_{z,k}\subset{\mathrm{Lip}}(\gamma,\Sigma,W)^{\ast}.$ (6.6)

By appealing to Lemma 5.5 we see that, the cardinality of $L(k)$ is (cf.
(5.65))

$\\#\left(L(k)\right)=\sum_{z\in P}\\#\left({\cal
T}_{z,k}\right)=mc\sum_{j=0}^{k}\beta(d,j)\stackrel{{\scriptstyle{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}({\ref{lip_k_recomb_eqn_num_recomb_step}})}}}{{=}}Q-1.$
(6.7)

  2. (B)

Let $L_{j}(k)\subset{\mathrm{Lip}}(\gamma,\Sigma,W)^{\ast}$ be the subset
resulting from applying a random permutation to the ordering of the linear
functionals in $L(k)$.

  3. (C)

Apply recombination via Lemma 3.1 in [LM22-I], with the Banach space $X$, the
integers ${\cal N},m\in{\mathbb{Z}}_{\geq 1}$, the subset $L\subset X^{\ast}$,
the finite subset ${\cal F}\subset X$, and the target
$\varphi\in\operatorname{Span}({\cal F})\subset X$ in that result as
${\mathrm{Lip}}(\gamma,\Sigma,W)$, ${\cal N},Q-1\in{\mathbb{Z}}_{\geq 1}$,
$L_{j}(k)$, and $\varphi\in\operatorname{Span}({\cal
F})\subset{\mathrm{Lip}}(\gamma,\Sigma,W)$ here respectively, to find
$u_{j}\in\operatorname{Span}({\cal F})$ satisfying

$\max\left\\{\left|\sigma(\varphi-u_{j})\right|:\sigma\in
L_{j}(k)\right\\}\leq\frac{\varepsilon_{0}}{cd^{k}}.$ (6.8)

Since $L_{j}(k)$ is a re-ordering of $L(k)$, the combination of (6.6) and
Lemma 5.5 for the subset ${\cal M}$ there as $P$ here (specifically
implication (5.63)) yields, for each point $z\in P$, that
$\Lambda^{k}_{\varphi-u_{j}}(z)\leq\varepsilon_{0}$.

  4. (D)

Compute

$E[u_{j}]:=\max\left\\{\left|\sigma(\varphi-
u_{j})\right|:\sigma\in\Sigma_{q}^{\ast}\right\\}.$ (6.9)

After obtaining the functions $u_{1},\ldots,u_{s}\in\operatorname{Span}({\cal
F})$ we define $u\in\operatorname{Span}({\cal F})$ by

$u:=\operatorname{argmin}\left\\{E[u_{j}]:j\in\\{1,\ldots,s\\}\right\\}.$
(6.10)

Then $u\in\operatorname{Span}({\cal F})$ is returned as our approximation of
$\varphi$ that satisfies, for every $z\in P$, that
$\Lambda^{k}_{\varphi-u}(z)\leq\varepsilon_{0}$. Theoretically, there is no
problem choosing $\varepsilon_{0}:=0$ in the HOLGRIM Recombination Step. The
use of recombination in Lemma 3.1 in [LM22-I] does theoretically find an
approximation $u$ of $\varphi$ such that, for every $\sigma\in L_{j}(k)$, we
have $\sigma(\varphi-u)=0$. Hence, via Lemma 5.5 (cf. (5.64) for $l$ there are
$k$ here), we may theoretically conclude that $\Lambda^{k}_{\varphi-u}(z)=0$
for all points $z\in P$ for the given subset $P\subset\Sigma$. However,
implementations of recombination inevitably result in numerical errors. That
is, the returned coefficients will only solve the equations modulo some
(ideally) small error term. Similarly to [LM22-I], we account for this in our
analysis by only assuming in (6.8) that the resulting approximation
$u_{j}\in\operatorname{Span}({\cal F})$ only satisfies, for every $\sigma\in
L_{j}(k)$, that $|\sigma(\varphi-u_{j})|\leq\varepsilon_{0}/cd^{k}$ for some
(small) constant $\varepsilon_{0}\geq 0$. The inclusion of the $cd^{k}$ factor
on the denominator is to ensure that, via an application of implication (5.63)
in Lemma 5.5 for the subset ${\cal M}$ there as $P$ here, for every point
$z\in P$ we have that $\Lambda^{k}_{\varphi-u}(z)\leq\varepsilon_{0}$.

We exploit the potential advantage offered by shuffling the order of the
inputs for recombination that is utilised in [LM22-I]. That is, if
recombination is applied to a linear system of equations corresponding to a
matrix $A$, then a Singular Value Decomposition (SVD) of the matrix $A$ is
used to find a basis of the kernel $\ker(A)$ (see Section 3 in [LM22-I], for
example). Consequently, re-ordering the rows of the matrix (i.e. changing the
order in which the equations are considered) can potentially result in a
different basis for $\ker(A)$ being selected. Hence shuffling the order of the
equations can affect the approximation returned by recombination via Lemma 3.1
in [LM22-I]. As done in [LM22-I], we exploit this by optimising the
approximation returned by recombination over a chosen number of shuffles of
the equations forming the linear system.

We now detail our proposed HOLGRIM algorithm to find an approximation
$u\in\operatorname{Span}({\cal F})$ of $\varphi\in\operatorname{Span}({\cal
F})$ that is close to $\varphi$ throughout $\Sigma$ in the sense that, for a
given $q\in\\{0,\ldots,k\\}$, we have
$\Lambda^{q}_{\varphi-u}(z)\leq\varepsilon$ for every point $z\in\Sigma$.

HOLGRIM

  1. (A)

Fix $\varepsilon>0$ as the _target accuracy threshold_ ,
$\varepsilon_{0}\in[0,\varepsilon)$ as the _acceptable recombination error_ ,
$M\in{\mathbb{Z}}_{\geq 1}$ as the _maximum number of steps_ , and
$q\in\\{0,\ldots,k\\}$ as the _order level_. Choose integers
$s_{1},\ldots,s_{M}\in{\mathbb{Z}}_{\geq 1}$ as the _shuffle numbers_ , and
integers $k_{1},\ldots,k_{M}\in{\mathbb{Z}}_{\geq 1}$ with

$\kappa:=k_{1}+\ldots+k_{M}\leq\min\left\\{\frac{{\cal
N}-1}{cD(d,k)},\Lambda\right\\}.$ (6.11)

Choose _scaling factors_ $A_{1},\ldots,A_{{\cal N}}\in{\mathbb{R}}$ such that,
for every $i\in\\{1,\ldots,{\cal N}\\}$, we have
$||f_{i}||_{{\mathrm{Lip}}(\gamma,\Sigma,W)}\leq A_{i}$.

  2. (B)

For each $i\in\\{1,\ldots,{\cal N}\\}$, if $a_{i}<0$ then replace $a_{i}$ and
$f_{i}$ by $-a_{i}$ and $-f_{i}$ respectively. This ensures that
$a_{1},\ldots,a_{{\cal N}}>0$ whilst leaving the expansion
$\varphi=\sum_{i=1}^{{\cal N}}a_{i}f_{i}$ unaltered. Additionally, for each
$i\in\\{1,\ldots,{\cal N}\\}$ replace $f_{i}$ by $h_{i}:=f_{i}/A_{i}$ so that
$h_{i}\in{\mathrm{Lip}}(\gamma,\Sigma,W)$ with
$||h_{i}||_{{\mathrm{Lip}}(\gamma,\Sigma,W)}\leq 1$, and that
$\varphi=\sum_{i=1}^{{\cal N}}\alpha_{i}h_{i}$ where $\alpha_{i}:=a_{i}A_{i}$.

  3. (C)

Apply the HOLGRIM Extension Step, with $P^{\prime}:=\varnothing$, $u\equiv 0$
and $m:=k_{1}$, to obtain a subset
$\Sigma_{1}=\left\\{z_{1,1},\ldots,z_{1,k_{1}}\right\\}\subset\Sigma$. Apply
the HOLGRIM Recombination Step, with $P:=\Sigma_{1}$ and $s:=s_{1}$, to find a
function $u_{1}\in\operatorname{Span}({\cal F})$ satisfying, for every point
$z\in\Sigma_{1}$, that $\Lambda^{k}_{\varphi-u_{1}}(z)\leq\varepsilon_{0}$.

If $M=1$ then the algorithm terminates here and returns $u_{1}$ as the final
approximation of $\varphi$.

  4. (D)

If $M\geq 2$ then we proceed inductively for $t\geq 2$ as follows. If
$|\sigma(\varphi-u_{t-1})|\leq\frac{\varepsilon}{cd^{q}}$ for every linear
functional $\sigma\in\Sigma^{\ast}_{q}$ then we stop and return $u_{t-1}$ as
the final approximation of $\varphi$. Otherwise, we apply the HOLGRIM
Extension Step with $P^{\prime}:=\Sigma_{t-1}$, $u:=u_{t-1}$ and $m:=k_{t}$,
to obtain a subset
$\Sigma_{t}=\Sigma_{t-1}\cup\left\\{z_{t,1},\ldots,z_{t,k_{t}}\right\\}\subset\Sigma$.
Apply the HOLGRIM Recombination Step, with $P:=\Sigma_{t}$ and $s:=s_{t}$, to
find a function $u_{t}\in\operatorname{Span}({\cal F})$ satisfying, for every
point $z\in\Sigma_{t}$, that $\Lambda^{k}_{\varphi-
u_{t}}(z)\leq\varepsilon_{0}$.

The algorithm ends either by returning $u_{t-1}$ for $t\in\\{2,\ldots,M\\}$
for which the stopping criterion was triggered as the final approximation of
$\varphi$, or by returning $u_{M}$ as the final approximation of $\varphi$ if
the stopping criterion is never triggered.

We claim that if $M\geq 2$ and the HOLGRIM algorithm terminates _before_ the
final $M^{\text{th}}$ step is completed, then the resulting approximation
$u\in\operatorname{Span}({\cal F})$ of $\varphi$ satisfies, for every
$z\in\Sigma$, that $\Lambda^{q}_{\varphi-u}(z)\leq\varepsilon$. To see this,
let $m\in\\{2,\ldots,M\\}$ and suppose that the HOLGRIM algorithm terminates
during the $m^{\text{th}}$ step, i.e. that the $m^{\text{th}}$ step is not
completed. Then $u_{m-1}\in\operatorname{Span}({\cal F})$ is the approximation
of $\varphi$ returned by the HOLGRIM algorithm.

It follows from Step (D) in the HOLGRIM algorithm that this requires that
$|\sigma(\varphi-u_{m-1})|\leq\varepsilon/cd^{q}$ for every
$\sigma\in\Sigma^{\ast}_{q}$. Recall that
$\Sigma^{\ast}_{q}:=\cup_{z\in\Sigma}{\cal T}_{z,q}$. Thus, for any
$z\in\Sigma$, we must have that $|\sigma(\varphi-
u_{m-1})|\leq\varepsilon/cd^{q}$ for every $\sigma\in{\cal T}_{z,q}$.
Consequently, by appealing to Lemma 5.5 (specifically to the implication
(5.63)), we conclude that $\Lambda^{q}_{\varphi-u_{m-1}}(z)\leq\varepsilon$.
Since $z\in\Sigma$ was arbitrary we have established that
$\max_{z\in\Sigma}\left\\{\Lambda^{q}_{\varphi-
u_{m-1}}(z)\right\\}\leq\varepsilon$ as claimed.

##  7 Complexity Cost

In this section we establish an estimate for the complexity cost of the
HOLGRIM algorithm detailed in Section 6. We first record the complexity cost
of the HOLGRIM Extension Step.

######  Lemma 7.1 (HOLGRIM Extension Step Complexity Cost).

Let ${\cal N},\Lambda,m,t,c,d\in{\mathbb{Z}}_{\geq 1}$. Let $V$ and $W$ be
real Banach spaces of dimensions $d$ and $c$ respectively. Assume the tensor
powers of $V$ are all equipped with admissible norms (cf. Definition 2.1). Let
$\Sigma\subset V$ be a finite subset with cardinality $\Lambda$. Let
$\gamma>0$ with $k\in{\mathbb{Z}}_{\geq 0}$ such that $\gamma\in(k,k+1]$, and
let $q\in\\{0,\ldots,k\\}$. Define $\Sigma^{\ast}_{q}:=\cup_{z\in\Sigma}{\cal
T}_{z,q}$. Let ${\cal F}=\\{f_{1},\ldots,f_{{\cal
N}}\\}\subset{\mathrm{Lip}}(\gamma,\Sigma,W)\setminus\\{0\\}$. Let
$a_{1},\ldots,a_{{\cal N}}\in{\mathbb{R}}\setminus\\{0\\}$ and define
$\varphi:=\sum_{i=1}^{{\cal N}}a_{i}f_{i}$. Assume that the subset
$\left\\{\sigma(\varphi):\sigma\in\Sigma_{q}^{\ast}\right\\}\subset{\mathbb{R}}$
and, for every $i\in\\{1,\ldots,{\cal N}\\}$, the subset
$\left\\{\sigma(f_{i}):\sigma\in\Sigma^{\ast}_{q}\right\\}\subset{\mathbb{R}}$
have already been computed. Then for any subset $P^{\prime}\subset\Sigma$ with
$\\#\left(P^{\prime}\right)+m\leq\Lambda$ and any
$u\in\operatorname{Span}({\cal F})$ with $\\#{\rm support}(u)=t$, the
complexity cost of applying the HOLGRIM Extension Step, with the $P^{\prime}$,
$u$, and $m$ there as the $P^{\prime}$, $u$, and $m$ here respectively, is
${\cal O}\left(c(m+t)\Lambda D(d,q)\right)$.

###### Proof of Lemma 7.1.

Let ${\cal N},\Lambda,m,t,c,d\in{\mathbb{Z}}_{\geq 1}$. Let $V$ and $W$ be
real Banach spaces of dimensions $d$ and $c$ respectively. Assume the tensor
powers of $V$ are all equipped with admissible norms (cf. Definition 2.1). Let
$\Sigma\subset V$ be a finite subset with cardinality $\Lambda$. Let
$\gamma>0$ with $k\in{\mathbb{Z}}_{\geq 0}$ such that $\gamma\in(k,k+1]$, and
let $q\in\\{0,\ldots,k\\}$. Define $\Sigma^{\ast}_{q}:=\cup_{z\in\Sigma}{\cal
T}_{z,q}$. Let ${\cal F}=\\{f_{1},\ldots,f_{{\cal
N}}\\}\subset{\mathrm{Lip}}(\gamma,\Sigma,W)\setminus\\{0\\}$. Let
$a_{1},\ldots,a_{{\cal N}}\in{\mathbb{R}}\setminus\\{0\\}$ and define
$\varphi:=\sum_{i=1}^{{\cal N}}a_{i}f_{i}$. Assume that the subset
$\left\\{\sigma(\varphi):\sigma\in\Sigma_{q}^{\ast}\right\\}\subset{\mathbb{R}}$
and, for every $i\in\\{1,\ldots,{\cal N}\\}$, the subset
$\left\\{\sigma(f_{i}):\sigma\in\Sigma^{\ast}_{q}\right\\}\subset{\mathbb{R}}$
have already been computed. Suppose that $P^{\prime}\subset\Sigma$ with
$\\#\left(P^{\prime}\right)+m\leq\Lambda$ and $u\in\operatorname{Span}({\cal
F})$ with $\\#{\rm support}(u)=t$. Recall our convention that ${\rm
support}(u)$ is the set of the functions $f_{i}$ that correspond to a non-zero
coefficient in the expansion of $u$ in terms of the $f_{i}$. That is,
$u=\sum_{i=1}^{{\cal N}}u_{i}f_{i}$ for real numbers $u_{1},\ldots,u_{{\cal
N}}\in{\mathbb{R}}$ and

${\rm support}(u):=\left\\{f_{j}:j\in\\{1,\ldots,{\cal N}\\}\text{ and
}u_{j}\neq 0\right\\}.$ (7.1)

Consider carrying out the HOLGRIM Extension Step with the $P^{\prime}$, $u$,
and $m$ there are $P^{\prime}$, $u$, and $m$ here respectively. Since we have
access to $\left\\{\sigma(\varphi):\sigma\in\Sigma_{q}^{\ast}\right\\}$ and
$\left\\{\sigma(f_{i}):\sigma\in\Sigma_{q}^{\ast}\right\\}$ for every
$i\in\\{1,\dots,{\cal N}\\}$ without additional computation, and since
$\\#{\rm support}(u)=t$, the complexity cost of computing the set
$\left\\{\left|\sigma(\varphi-u)\right|:\sigma\in\Sigma_{q}^{\ast}\right\\}$
is no worse than ${\cal
O}\left(t\\#\left(\Sigma^{\ast}_{q}\right)\right)={\cal O}\left(ct\Lambda
D(d,q)\right)$. Each of the $m$ argmax values are found from a list of no
greater than $\\#\left(\Sigma_{q}^{\ast}\right)=c\Lambda D(d,q)$ real numbers,
and so the complexity cost of extracting these $m$ argmax values is no worse
than ${\cal O}\left(cm\Lambda D(d,q)\right)$. Moreover, for
$j\in\\{2,\ldots,m\\}$, the list from which we extract the next the
$j^{\text{th}}$ argmax value is obtained by removing $cD(d,q)$ values from the
previous list, i.e. for every linear functional $\sigma\in{\cal
T}_{z_{j-1},q}$ we remove the value $\sigma(\varphi-u)$, which results in
removing $cD(d,q)$ values in total since this is the cardinality of ${\cal
T}_{z_{j-1},q}$ (cf. (5.20)). Thus the complexity cost of the discarding is,
in total, no worse than ${\cal O}\left(cmD(d,q)\right)$ The complexity cost of
appending the resulting $m$ points $z_{1},\ldots,z_{m}\in\Sigma$ to the
collection $P^{\prime}$ is ${\cal O}(m)$. Therefore the entire HOLGRIM
Extension Step has a complexity cost no worse than ${\cal
O}\left(c(m+t)\Lambda D(d,q)\right)$ as claimed. This completes the proof of
Lemma 7.1. ∎

We next record the complexity cost of the HOLGRIM Recombination Step.

######  Lemma 7.2 (HOLGRIM Recombination Step Complexity Cost).