# Geometry of tree-based tensor formats in tensor Banach spaces

Antonio Falcó111Corresponding author${}^{\,\,1},$ Wolfgang Hackbusch2 and
Anthony Nouy3
1 ESI International Chair@CEU-UCH,
Departamento de Matemáticas, Física y Ciencias Tecnológicas,
Universidad Cardenal Herrera-CEU, CEU Universities
San Bartolomé 55, 46115 Alfara del Patriarca (Valencia), Spain
e-mail<EMAIL_ADDRESS>
2 Max-Planck-Institut _Mathematik in den Naturwissenschaften_
Inselstr. 22, D-04103 Leipzig, Germany
e-mail<EMAIL_ADDRESS>
3 Centrale Nantes,
LMJL UMR CNRS 6629
1 rue de la Noë, 44321 Nantes Cedex 3, France.
e-mail<EMAIL_ADDRESS>
###### Abstract

In the paper _‘On the Dirac-Frenkel Variational Principle on Tensor Banach
Spaces’_ , we provided a geometrical description of manifolds of tensors in
Tucker format with fixed multilinear (or Tucker) rank in tensor Banach spaces,
that allowed to extend the Dirac-Frenkel variational principle in the
framework of topological tensor spaces. The purpose of this note is to extend
these results to more general tensor formats. More precisely, we provide a new
geometrical description of manifolds of tensors in tree-based (or
hierarchical) format, also known as tree tensor networks, which are
intersections of manifolds of tensors in Tucker format associated with
different partitions of the set of dimensions. The proposed geometrical
description of tensors in tree-based format is compatible with the one of
manifolds of tensors in Tucker format.

_2010 AMS Subject Classifications:_ 15A69, 46B28, 46A32.

_Key words:_ Tensor spaces, Banach manifolds, Tensor formats, Tree-based
tensor tensors, Tree tensor networks, Geometry.

##  1 Introduction

Tensor methods are prominent tools in a wide range of applications involving
high-dimensional data or functions. The exploitation of low-rank structures of
tensors is the basis of many approximation or dimension reduction methods, see
the surveys [15, 2, 17, 18, 4, 5] and monograph [11]. Providing a geometrical
description of sets of low-rank tensors has many interests. In particular, it
allows to devise robust algorithms for optimization [1, 23] or construct
reduced order models for dynamical systems [14].

A basic low-rank tensor format is the Tucker format. Given a collection of $d$
vector spaces $V_{\nu}$, $\nu\in D:=\\{1,\ldots,d\\}$, and the corresponding
algebraic tensor space $\mathbf{V}_{D}=V_{1}\otimes\ldots\otimes V_{d},$ the
set of tensors $\mathfrak{M}_{\mathfrak{r}}(\mathbf{V}_{D})$ of tensors in
Tucker format with rank $\mathfrak{r}=(r_{1},\ldots,r_{d})$ is the set of
tensors $\mathbf{v}$ in $\mathbf{V}_{D}$ such that $\mathbf{v}\in
U_{1}\otimes\ldots\otimes U_{d}$ for some subspaces $U_{\nu}$ in the Grassmann
manifold $\mathbb{G}_{r_{\nu}}(V_{\nu})$ of $r_{\nu}$-dimensional spaces in
$V_{\nu}.$ A geometrical description of
$\mathfrak{M}_{\mathfrak{r}}(\mathbf{V}_{D})$ has been introduced in [9],
providing this set the structure of a $C^{\infty}$-Banach manifold.

Tree-based tensor formats [8], also known as tree tensor networks in physics
or data science [19, 21, 10, 16], are more general low-rank tensor formats,
also based on subspaces. They include the hierarchical format [12] or the
tensor-train format [20]. Sets of tensors in tree-based tensor format are the
intersection of a collection of sets of tensors in Tucker format associated
with a hierarchy of partitions given by a tree. More precisely, given a
dimension partition tree $T_{D}$ over $D$, we can define a sequence of
partitions $\mathcal{P}_{1},\ldots,\mathcal{P}_{L}$ of $D$, with $L$ the depth
of the tree, such that each element in $\mathcal{P}_{k}$ is a subset of an
element of $\mathcal{P}_{k-1}$ (see example in Figure 1.1). For each partition
${\mathcal{P}_{k}}$, a tensor in $\mathbf{V}_{D}$ can be identified with a
tensor in
$\mathbf{V}_{\mathcal{P}_{k}}:=\bigotimes_{\alpha\in\mathcal{P}_{k}}\mathbf{V}_{\alpha}$,
that allows to define manifolds of tensors in Tucker format
$\mathfrak{M}_{\mathfrak{r}_{k}}(\mathbf{V}_{\mathcal{P}_{k}})$ with
$\mathfrak{r}_{k}\in\mathbb{N}^{\\#\mathcal{P}_{k}}$. The set
$\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D})$ of tensors in $\mathbf{V}_{D}$
with tree-based rank $\mathfrak{r}=(r_{\alpha})_{\alpha\in
T_{D}}\in\mathbb{N}^{\\#T_{D}}$ is then given by

$\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D})=\bigcap_{k=1}^{L}\mathfrak{M}_{\mathfrak{r}_{k}}(\mathbf{V}_{\mathcal{P}_{k}})$

where $\mathfrak{r}_{k}=(r_{\alpha})_{\alpha\in\mathcal{P}_{k}}$.

[$\\{1,2,3,4\\}$[$\\{1,2,3\\}$[$\\{1\\}$][$\\{2,3\\}$[$\\{2\\}$][$\\{3\\}$]]]
[$\\{4\\}$]]

Figure 1.1: A dimension partition tree over $D=\\{1,2,3,4\\}$, with depth
$L=3$, and the associated partitions of $D$:
$\mathcal{P}_{3}=\\{\\{1\\},\\{2\\},\\{3\\},\\{4\\}\\}$,
$\mathcal{P}_{2}=\\{\\{1\\},\\{2,3\\},\\{4\\}\\}$,
$\mathcal{P}_{1}=\\{\\{1,2,3\\},\\{4\\}\\}$.

In this paper, we provide a new geometrical description of the sets
$\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D})$ of tensors with fixed tree-based
rank in tensor Banach spaces. This description is compatible with the one of
manifolds $\mathfrak{M}_{\mathfrak{r}_{k}}(\mathbf{V}_{\mathcal{P}_{k}})$
introduced in [9]. It is different from the ones from [22] and [13],
respectively introduced for hierarchical and tensor train formats in finite-
dimensional tensor spaces. It is also different from the one introduced by the
authors in [7], that provided a different chart system. The present
geometrical description is more natural and we believe that it is more
amenable for applications. With the present description, and under similar
assumptions on the norms of tensor spaces, Theorem 5.2 and Theorem 5.4 in [9]
also hold for tree-based tensor formats, that allows to extend the Dirac-
Frenkel variational principle for tree-based tensor formats in tensor Banach
spaces.

The outline of this note is as follows. We start in section 2 by recalling
results from [9], that is a geometrical description of manifolds
$\mathfrak{M}_{\mathfrak{r}}(\mathbf{V}_{D})$ of tensors in Tucker format.
Then in section 3 we introduce a description of tree-based tensor formats
$\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D})$ as an intersection of Tucker
formats. Finally in Section 4, we introduce the new geometrical description of
the manifold $\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D})$ of tensors in tree-
based tensor format with fixed tree-based rank.

##  2 Preliminary results

Let $D:=\\{1,\ldots,d\\}$ be a finite index set and consider an algebraic
tensor space $\mathbf{V}_{D}=_{a}\bigotimes_{\alpha\in D}V_{\alpha}$ generated
from vector spaces $V_{\alpha}$, $\alpha\in D$ (the suffix ‘$a$’ in
${}_{a}\bigotimes_{\alpha\in D}V_{\alpha}$ refers to the ‘algebraic’ nature).
For any partition $\mathcal{P}_{D}$ of $D$, the algebraic tensor space
$\mathbf{V}_{D}$ can be identified with an algebraic tensor space generated
from vector spaces $\mathbf{V}_{\alpha}$, $\alpha\in\mathcal{P}_{D}$. Indeed,
for any partition $\mathcal{P}_{D}$ of $D,$ the equality

$\mathbf{V}_{D}=\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{D}}\mathbf{V}_{\alpha}\right.$

holds, with
$\mathbf{V}_{\alpha}:=\left.{}_{a}\bigotimes_{j\in\alpha}V_{j}\right.$ if
$\alpha\neq\\{j\\},$ for some $j\in D,$ or $\mathbf{V}_{\alpha}=V_{j}$ if
$\alpha=\\{j\\}$ for some $j\in D.$ Next we identify $D$ with the trivial
partition $\\{\\{1\\},\\{2\\},\ldots,\\{d\\}\\}.$

###### Remark 2.1

In [9], we considered the tensor space
$\mathbf{V}_{D}=_{a}\bigotimes_{\alpha\in D}V_{\alpha}$ for a given $D$. It is
not difficult to check that the results from [9] remain true when substituting
$D$ by any partition $\mathcal{P}_{D}$, that includes the initial case by
identifying $D$ with the trivial partition
$\\{\\{1\\},\\{2\\},\ldots,\\{d\\}\\}.$ More precisely, we can substitute with
minor changes along the paper “$\alpha\in D$” by “$\alpha\in\mathcal{P}_{D}$”.

Before restating Theorem 3.17 of [9] in the present framework, we recall some
definitions from [9].

Let $X$ be a Banach space. We denote by $\mathbb{G}(X)$ the Grassmann manifold
of closed subspaces in $X$ (see Section 2 in [9]). More precisely, we say that
$U\in\mathbb{G}(X)$ holds if and only if $U$ is a closed subspace in $X$ and
there exists a closed subspace $W$ in $X$ such that $X=U\oplus W.$ Every
finite-dimensional subspace belongs to $\mathbb{G}(X),$ and we denote by
$\mathbb{G}_{n}(X)$ the space of all $n$-dimensional subspaces of $X$ $(n\geq
0).$

Assume that $\mathcal{P}_{D}$ is a partition of $D.$ Given
$\mathfrak{r}=(r_{\alpha})_{\alpha\in\mathcal{P}_{D}}\in\mathbb{N}^{\\#\mathcal{P}_{D}},$
we denote by $\mathfrak{M}_{\mathfrak{r}}(\mathbf{V}_{D})$ the set of tensors
in $\mathbf{V}_{D}$ represented in Tucker format with a fixed rank
$\mathfrak{r}.$ In particular,
$\mathbf{v}\in\mathfrak{M}_{\mathfrak{r}}(\mathbf{V}_{D})$ if and only if for
each $\alpha\in\mathcal{P}_{D}$ there exists a minimal subspace
$\mathbf{U}_{\alpha}:=\mathbf{U}_{\alpha}(\mathbf{v})\in\mathbb{G}_{r_{\alpha}}(\mathbf{V}_{\alpha})$
such that
$\mathbf{v}\in\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{D}}\mathbf{U}_{\alpha}\right..$
Recall that the finite dimensional vector space
$\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{D}}\mathbf{U}_{\alpha}\right.$
is linearly isomorphic to the vector space
$\mathbb{R}^{\mathop{\mathchoice{\raise-1.54001pt\hbox{\huge$\times$}}{\raise-0.35002pt\hbox{\Large$\times$}}{\hbox{\large$\times$}}{\times}}_{\alpha\in\mathcal{P}_{D}}r_{\alpha}}.$
This fact allows to identify the set of full rank tensors in
$\mathbb{R}^{\mathop{\mathchoice{\raise-1.54001pt\hbox{\huge$\times$}}{\raise-0.35002pt\hbox{\Large$\times$}}{\hbox{\large$\times$}}{\times}}_{\alpha\in\mathcal{P}_{D}}r_{\alpha}},$
denoted by
$\mathbb{R}_{*}^{\mathop{\mathchoice{\raise-1.54001pt\hbox{\huge$\times$}}{\raise-0.35002pt\hbox{\Large$\times$}}{\hbox{\large$\times$}}{\times}}_{\alpha\in\mathcal{P}_{D}}r_{\alpha}},$
with
$\mathfrak{M}_{\mathfrak{r}}\left(\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{D}}\mathbf{U}_{\alpha}\right.\right).$

Then we have the following result.

###### Theorem 2.2

Assume that $\mathcal{P}_{D}$ is a partition of $D,$
$(\mathbf{V}_{\alpha},\|\cdot\|_{\alpha})$ is a normed space for each
$\alpha\in\mathcal{P}_{D}$ and that $\|\cdot\|_{D}$ is a norm on the tensor
space
$\mathbf{V}_{D}=\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{D}}\mathbf{V}_{\alpha}\right.$
such that the tensor product map

$\bigotimes_{\alpha\in\mathcal{P}_{D}}:\left(\mathop{\mathchoice{\raise-2.20001pt\hbox{\huge$\times$}}{\raise-0.50003pt\hbox{\Large$\times$}}{\hbox{\large$\times$}}{\times}}_{\alpha\in\mathcal{P}_{D}}\mathbf{V}_{\alpha},\left\|\cdot\right\|_{\times}\right)\longrightarrow\bigg{(}\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{D}}\mathbf{V}_{\alpha}\right.,\left\|\cdot\right\|_{D}\bigg{)},$
(2.1)

is continuous. Then there exists a $\mathcal{C}^{\infty}$-atlas
$\\{\mathcal{U}(\mathbf{v}),\xi_{\mathbf{v}}\\}_{\mathbf{v}\in\mathfrak{M}_{\mathfrak{r}}(\mathbf{V}_{D})}$
for $\mathfrak{M}_{\mathfrak{r}}(\mathbf{V}_{D})$ and hence
$\mathfrak{M}_{\mathfrak{r}}(\mathbf{V}_{D})$ is a
$\mathcal{C}^{\infty}$-Banach manifold modelled on a Banach space

$\left(\mathop{\mathchoice{\raise-2.20001pt\hbox{\huge$\times$}}{\raise-0.50003pt\hbox{\Large$\times$}}{\hbox{\large$\times$}}{\times}}_{\alpha\in\mathcal{P}_{D}}\mathcal{L}(\mathbf{U}_{\alpha},\mathbf{W}_{\alpha})\right)\times\mathbb{R}^{\mathop{\mathchoice{\raise-1.54001pt\hbox{\huge$\times$}}{\raise-0.35002pt\hbox{\Large$\times$}}{\hbox{\large$\times$}}{\times}}_{\alpha\in\mathcal{P}_{D}}r_{\alpha}}.$

Here $\mathbf{U}_{\alpha}\in\mathbb{G}_{r_{\alpha}}(\mathbf{V}_{\alpha})$ and
$\mathbf{V}_{\alpha_{\|\cdot\|_{\alpha}}}=\mathbf{U}_{\alpha}\oplus\mathbf{W}_{\alpha},$
where $\mathbf{V}_{{\alpha}_{\|\cdot\|_{\alpha}}}$ is the completion of
$\mathbf{V}_{\alpha}$ for $\alpha\in\mathcal{P}_{D}.$ Moreover,

$\left(\mathfrak{M}_{\mathfrak{r}}(\mathbf{V}_{D}),\mathop{\mathchoice{\raise-2.20001pt\hbox{\huge$\times$}}{\raise-0.50003pt\hbox{\Large$\times$}}{\hbox{\large$\times$}}{\times}}_{\alpha\in\mathcal{P}_{D}}\mathbb{G}_{r_{\alpha}}(\mathbf{V}_{\alpha}),\varrho_{\mathfrak{r}}\right)$

is a $\mathcal{C}^{\infty}$-fibre bundle with typical fibre
$\mathbb{R}_{*}^{\mathop{\mathchoice{\raise-1.54001pt\hbox{\huge$\times$}}{\raise-0.35002pt\hbox{\Large$\times$}}{\hbox{\large$\times$}}{\times}}_{\alpha\in\mathcal{P}_{D}}r_{\alpha}},$
with $\varrho_{\mathfrak{r}}$ being the map which associates to a tensor
$\mathbf{v}$ in $\mathfrak{M}_{\mathfrak{r}}(\mathbf{V}_{D})$ its minimal
subspaces $\mathbf{U}_{\alpha},$ $\alpha\in\mathcal{P}_{D}$.

In (2.1) the product space
$\mathop{\mathchoice{\raise-2.20001pt\hbox{\huge$\times$}}{\raise-0.50003pt\hbox{\Large$\times$}}{\hbox{\large$\times$}}{\times}}_{\alpha\in\mathcal{P}_{D}}\mathbf{V}_{\alpha}$
is equipped with the product topology induced by the maximum norm
$\|(\mathbf{v}_{\alpha})_{\alpha\in\mathcal{P}_{D}})\|_{\times}=\max_{\alpha\in\mathcal{P}_{D}}\|\mathbf{v}_{\alpha}\|_{\alpha}.$

We recall that
$\overline{\mathbf{V}_{D}}^{\|\cdot\|_{D}}=\mathbf{V}_{D_{\|\cdot\|_{D}}}$
denotes the tensor Banach space obtained as the completion of the algebraic
one

$\mathbf{V}_{D}=\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{D}}\mathbf{V}_{\alpha}\right.$

under the norm $\|\cdot\|_{D}.$ Our next step is, given a fixed partition
$\mathcal{P}_{D}$ of $D,$ to identify the Banach space
$\bigtimes_{\alpha\in\mathcal{P}_{D}}\mathcal{L}(\mathbf{U}_{\alpha},\mathbf{W}_{\alpha})$
with a closed subspace of the Banach algebra
$\mathcal{L}(\mathbf{V}_{D_{\|\cdot\|_{D}}},\mathbf{V}_{D_{\|\cdot\|_{D}}}).$
To this end, we need to proceed in the framework of Section 4 in [9]. First,
we recall the definition of injective norm (Definition 4.9 in [9]) stated in
the actual framework.

###### Definition 2.3

Let $\mathbf{V}_{\alpha}$ be a Banach space with norm
$\left\|\cdot\right\|_{\alpha}$ for $\alpha\in\mathcal{P}_{D}.$ Then for
$\mathbf{v}\in\mathbf{V}=\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{D}}\mathbf{V}_{\alpha}\right.$
define
$\left\|\cdot\right\|_{\vee((\mathbf{V}_{\alpha})_{\alpha\in\mathcal{P}_{D}})}$
by

$\left\|\mathbf{v}\right\|_{\vee((\mathbf{V}_{\alpha})_{\alpha\in\mathcal{P}_{D}})}:=\sup\left\\{\frac{\left|\left(\bigotimes_{\alpha\in\mathcal{P}_{D}}\varphi_{\alpha}\right)(\mathbf{v})\right|}{\prod_{\alpha\in\mathcal{P}_{D}}\|\varphi_{\alpha}\|_{\alpha}^{\ast}}:0\neq\varphi_{\alpha}\in\mathbf{V}_{\alpha}^{\ast},\alpha\in\mathcal{P}_{D}\right\\},$
(2.2)

where $\mathbf{V}_{\alpha}^{\ast}$ is the continuous dual of
$\mathbf{V}_{\alpha}$.

Let $W$ and $U$ be closed subspaces of a Banach space $X$ such that $X=U\oplus
W.$ From now on, we will denote by $P_{{}_{U\oplus W}}$ the projection onto
$U$ along $W.$ Then we have $P_{{}_{W\oplus U}}=id_{X}-P_{{}_{U\oplus W}}.$
The proof of the next result uses Proposition 2.8, Lemma 4.13 and Lemma 4.14
in [9].

###### Lemma 2.4

Assume that $(\mathbf{V}_{\alpha},\|\cdot\|_{\alpha})$ is a normed space for
each $\alpha\in\mathcal{P}_{D}$ and let $\|\cdot\|_{D}$ be a norm on the
tensor space
$\mathbf{V}_{D}=\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{D}}\mathbf{V}_{\alpha}\right.$
such that

$\displaystyle\left\|\cdot\right\|_{\vee((\mathbf{V}_{\alpha})_{\alpha\in\mathcal{P}_{D}})}\lesssim\left\|\cdot\right\|_{D},$
(2.3)

holds. Let
$\mathbf{U}_{\alpha}\in\mathbb{G}_{r_{\alpha}}(\mathbf{V}_{\alpha})$ and
$\mathbf{V}_{\alpha_{\|\cdot\|_{\alpha}}}=\mathbf{U}_{\alpha}\oplus\mathbf{W}_{\alpha},$
where $\mathbf{V}_{{\alpha}_{\|\cdot\|_{\alpha}}}$ is the completion of
$\mathbf{V}_{\alpha}$ for $\alpha\in\mathcal{P}_{D}.$ Then for each
$\alpha\in\mathcal{P}_{D}$ we have

$\mathcal{L}\left(\mathbf{U}_{\alpha},\mathbf{W}_{\alpha}\right)\otimes_{a}\mathrm{span}\\{\mathbf{id}_{[\alpha]}\\}\in\mathbb{G}\left(\mathcal{L}(\mathbf{V}_{D_{\|\cdot\|_{D}}},\mathbf{V}_{D_{\|\cdot\|_{D}}})\right)$

where
$\mathbf{id}_{[\alpha]}:=\bigotimes_{\beta\in\mathcal{P}_{D}\setminus\\{\alpha\\}}id_{\mathbf{V}_{\beta}}.$
Furthermore,

$\bigoplus_{\alpha\in\mathcal{P}_{D}}\mathcal{L}\left(\mathbf{U}_{\alpha},\mathbf{W}_{\alpha}\right)\otimes_{a}\mathrm{span}\\{\mathbf{id}_{[\alpha]}\\}\in\mathbb{G}\left(\mathcal{L}(\mathbf{V}_{D_{\|\cdot\|_{D}}},\mathbf{V}_{D_{\|\cdot\|_{D}}})\right).$

_Proof._ To prove the lemma, for a fixed $\alpha\in\mathcal{P}_{D},$ note that
$id_{\mathbf{V}_{\alpha}}=P_{{}_{\mathbf{U}_{\alpha}\oplus\mathbf{W}_{\alpha}}}+P_{{}_{\mathbf{W}_{\alpha}\oplus\mathbf{U}_{\alpha}}}$
and write

$id_{\mathbf{V}_{D_{\|\cdot\|_{D}}}}=id_{\mathbf{V}_{\alpha}}\otimes\mathbf{id}_{[\alpha]}.$

Clearly,
$P_{{}_{\mathbf{U}_{\alpha}\oplus\mathbf{W}_{\alpha}}}\otimes\mathbf{id}_{[\alpha]}\in\mathcal{L}(\mathbf{V}_{D_{\|\cdot\|_{D}}},\mathbf{V}_{D_{\|\cdot\|_{D}}}).$
Then by proceeding as in Lemma 4.13 in [9] we obtain that

$P_{{}_{\mathbf{W}_{\alpha}\oplus\mathbf{U}_{\alpha}}}\otimes\mathbf{id}_{[\alpha]}\in\mathcal{L}(\mathbf{V}_{D_{\|\cdot\|_{D}}},\mathbf{V}_{D_{\|\cdot\|_{D}}}).$

Now, define the linear and bounded map

$\mathcal{P}_{\alpha}:\mathcal{L}(\mathbf{V}_{D_{\|\cdot\|_{D}}},\mathbf{V}_{D_{\|\cdot\|_{D}}})\longrightarrow\mathcal{L}(\mathbf{V}_{D_{\|\cdot\|_{D}}},\mathbf{V}_{D_{\|\cdot\|_{D}}})$

as
$\mathcal{P}_{\alpha}(L)=(P_{{}_{\mathbf{W}_{\alpha}\oplus\mathbf{U}_{\alpha}}}\otimes\mathbf{id}_{[\alpha]})\circ
L\circ(P_{{}_{\mathbf{U}_{\alpha}\oplus\mathbf{W}_{\alpha}}}\otimes\mathbf{id}_{[\alpha]}).$
It satisfies
$\mathcal{P}_{\alpha}\circ\mathcal{P}_{\alpha}=\mathcal{P}_{\alpha}$ and

$\mathcal{P}_{\alpha}(\mathcal{L}(\mathbf{V}_{D_{\|\cdot\|_{D}}},\mathbf{V}_{D_{\|\cdot\|_{D}}}))=\mathcal{L}\left(\mathbf{U}_{\alpha},\mathbf{W}_{\alpha}\right)\otimes_{a}\mathrm{span}\\{\mathbf{id}_{[\alpha]}\\}.$

Proposition 2.8(b) in [9] implies that
$\mathcal{L}\left(\mathbf{U}_{\alpha},\mathbf{W}_{\alpha}\right)\otimes_{a}\mathrm{span}\\{\mathbf{id}_{[\alpha]}\\}\in\mathbb{G}\left(\mathcal{L}(\mathbf{V}_{D_{\|\cdot\|_{D}}},\mathbf{V}_{D_{\|\cdot\|_{D}}})\right).$
Observe that for $\alpha,\beta\in\mathcal{P}_{D}$ with $\alpha\neq\beta$ we
have

$(\mathcal{L}\left(\mathbf{U}_{\alpha},\mathbf{W}_{\alpha}\right)\otimes_{a}\mathrm{span}\\{\mathbf{id}_{[\alpha]}\\})\cap(\mathcal{L}\left(\mathbf{U}_{\beta},\mathbf{W}_{\beta}\right)\otimes_{a}\mathrm{span}\\{\mathbf{id}_{[\beta]}\\})=\\{\mathbf{0}\\}.$

By Lemma 4.14 in [9] we have

$\bigoplus_{\alpha\in\mathcal{P}_{D}}\mathcal{L}\left(\mathbf{U}_{\alpha},\mathbf{W}_{\alpha}\right)\otimes_{a}\mathrm{span}\\{\mathbf{id}_{[\alpha]}\\}\in\mathbb{G}\left(\mathcal{L}(\mathbf{V}_{D_{\|\cdot\|_{D}}},\mathbf{V}_{D_{\|\cdot\|_{D}}})\right).$

This proves the lemma.

Lemma 2.4 allows to introduce the following linear isomorphism:

$\Delta:\mathop{\mathchoice{\raise-2.20001pt\hbox{\huge$\times$}}{\raise-0.50003pt\hbox{\Large$\times$}}{\hbox{\large$\times$}}{\times}}_{\alpha\in\mathcal{P}_{D}}\mathcal{L}(\mathbf{U}_{\alpha},\mathbf{W}_{\alpha})\longrightarrow\bigoplus_{\alpha\in\mathcal{P}_{D}}\mathcal{L}\left(U_{\alpha},\mathbf{W}_{\alpha}\right)\otimes_{a}\mathrm{span}\\{\mathbf{id}_{[\alpha]}\\},\quad(L_{\alpha})_{\alpha\in\mathcal{P}_{D}}\mapsto\sum_{\alpha\in\mathcal{P}_{D}}L_{\alpha}\otimes\mathbf{id}_{[\alpha]}.$

where
$\mathbf{id}_{[\alpha]}:=\bigotimes_{\beta\in\mathcal{P}_{D}\setminus\\{\alpha\\}}id_{\mathbf{V}_{\beta}}$
for $\alpha\in\mathcal{P}_{D}.$ The next proposition gives us a useful
property of the elements in the image of the map $\Delta.$

###### Proposition 2.5

Assume that $\mathcal{P}_{D}$ is a partition of $D,$
$(\mathbf{V}_{\alpha},\|\cdot\|_{\alpha})$ is a normed space for each
$\alpha\in\mathcal{P}_{D}$ and $\|\cdot\|_{D}$ is a norm on the tensor space
$\mathbf{V}_{D}=\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{D}}\mathbf{V}_{\alpha}\right.$
such that (2.3) holds. Then for each
$(L_{\alpha})_{\alpha\in\mathcal{P}_{D}}\in\mathop{\mathchoice{\raise-2.20001pt\hbox{\huge$\times$}}{\raise-0.50003pt\hbox{\Large$\times$}}{\hbox{\large$\times$}}{\times}}_{\alpha\in\mathcal{P}_{D}}\mathcal{L}(U_{\alpha},\mathbf{W}_{\alpha})$
it holds that

$\exp(\Delta\left((L_{\alpha})_{\alpha\in\mathcal{P}_{D}})\right)=\bigotimes_{\alpha\in\mathcal{P}_{D}}\exp(L_{\alpha}).$

_Proof._ Put
$L:=\Delta\left((L_{\alpha})_{\alpha\in\mathcal{P}_{D}}\right)=\sum_{\alpha\in\mathcal{P}_{D}}L_{\alpha}\otimes\mathbf{id}_{[\alpha]}$
and observe that for each $\alpha\in\mathcal{P}_{D}$ it holds

$\exp(L_{\alpha}\otimes\mathbf{id}_{[\alpha]})=\sum_{n=0}^{\infty}\frac{1}{n!}(L_{\alpha}\otimes\mathbf{id}_{[\alpha]})^{n}=\left(\sum_{n=0}^{\infty}\frac{1}{n!}L_{\alpha}^{n}\right)\otimes\mathbf{id}_{[\alpha]}=\exp(L_{\alpha})\otimes\mathbf{id}_{[\alpha]}.$

Moreover for $\alpha,\beta\in\mathcal{P}_{D}$ and $\alpha\neq\beta$ we have

$(L_{\alpha}\otimes\mathbf{id}_{[\alpha]})\circ(L_{\beta}\otimes\mathbf{id}_{[\beta]})=(L_{\beta}\otimes\mathbf{id}_{[\beta]})\circ(L_{\alpha}\otimes\mathbf{id}_{[\alpha]})=L_{\alpha}\otimes
L_{\beta}\otimes\left(\bigotimes_{\delta\in\mathcal{P}_{D}\setminus\\{\alpha,\beta\\}}id_{\mathbf{V}_{\delta}}\right).$

Finally, by seing $\mathcal{P}_{D}$ as an ordered set, and by denoting
$\bigodot_{i=1}^{n}A_{i}:=A_{1}\circ A_{2}\circ\cdots\circ A_{n}$ is the
composition of maps $A_{i}$, $1\leq i\leq n$, we have

$\displaystyle\exp\left(L\right)=\bigodot_{\alpha\in\mathcal{P}_{D}}\exp(L_{\alpha}\otimes\mathbf{id}_{[\alpha]})=\bigodot_{\alpha\in\mathcal{P}_{D}}\exp(L_{\alpha})\otimes\mathbf{id}_{[\alpha]}=\bigotimes_{\alpha\in\mathcal{P}_{D}}\exp(L_{\alpha}).$

Note that since operators $\exp(L_{\alpha})\otimes\mathbf{id}_{[\alpha]}$ and
$\exp(L_{\beta})\otimes\mathbf{id}_{[\beta]}$ commute for any
$\alpha,\beta\in\mathcal{P}_{D}$, the above result is independent of the
chosen order on $\mathcal{P}_{D}$. This proves the proposition.

To conclude we re-state Theorem 2.2 as follows.

###### Theorem 2.6

Assume that $\mathcal{P}_{D}$ is a partition of $D,$
$(V_{\alpha},\|\cdot\|_{\alpha})$ is a normed space for each
$\alpha\in\mathcal{P}_{D}$ and let $\|\cdot\|_{D}$ be a norm on the tensor
space $\mathbf{V}_{D}=\left.{}_{a}\bigotimes_{\alpha\in
D}\mathbf{V}_{\alpha}\right.$ such that (2.3) holds. Then there exists a
$\mathcal{C}^{\infty}$-atlas
$\\{\mathcal{U}(\mathbf{v}),\xi_{\mathbf{v}}\\}_{\mathbf{v}\in\mathfrak{M}_{\mathfrak{r}}(\mathbf{V}_{D})}$
for $\mathfrak{M}_{\mathfrak{r}}(\mathbf{V}_{D})$ and hence
$\mathfrak{M}_{\mathfrak{r}}(\mathbf{V}_{D})$ is a
$\mathcal{C}^{\infty}$-Banach manifold modelled on a Banach space

$\left(\bigoplus_{\alpha\in\mathcal{P}_{D}}\mathcal{L}\left(\mathbf{U}_{\alpha},\mathbf{W}_{\alpha}\right)\otimes_{a}\mathrm{span}\\{\mathbf{id}_{[\alpha]}\\}\right)\times\mathbb{R}^{\mathop{\mathchoice{\raise-1.54001pt\hbox{\huge$\times$}}{\raise-0.35002pt\hbox{\Large$\times$}}{\hbox{\large$\times$}}{\times}}_{\alpha\in\mathcal{P}_{D}}r_{\alpha}},$

here $\mathbf{U}_{\alpha}\in\mathbb{G}_{r_{\alpha}}(\mathbf{V}_{\alpha})$ and
$\mathbf{V}_{\alpha_{\|\cdot\|_{\alpha}}}=\mathbf{U}_{\alpha}\oplus\mathbf{W}_{\alpha},$
where $\mathbf{V}_{{\alpha}_{\|\cdot\|_{\alpha}}}$ is the completion of
$\mathbf{V}_{\alpha}$ for $\alpha\in\mathcal{P}_{D}.$ Moreover,

$\left(\mathfrak{M}_{\mathfrak{r}}(\mathbf{V}_{D}),\mathop{\mathchoice{\raise-2.20001pt\hbox{\huge$\times$}}{\raise-0.50003pt\hbox{\Large$\times$}}{\hbox{\large$\times$}}{\times}}_{\alpha\in\mathcal{P}_{D}}\mathbb{G}_{r_{\alpha}}(\mathbf{V}_{\alpha}),\varrho_{\mathfrak{r}}\right)$

is a $\mathcal{C}^{\infty}$-fibre bundle with typical fibre
$\mathbb{R}_{*}^{\mathop{\mathchoice{\raise-1.54001pt\hbox{\huge$\times$}}{\raise-0.35002pt\hbox{\Large$\times$}}{\hbox{\large$\times$}}{\times}}_{\alpha\in\mathcal{P}_{D}}r_{\alpha}}.$

We recall the construction of the local charts $\xi_{\mathbf{v}}$ for a given
$\mathbf{v}\in\mathfrak{M}_{\mathfrak{r}}(\mathbf{V}_{D}).$ Once minimal
subspaces $\mathbf{U}_{\alpha}$ of
$\mathbf{v}\in\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{D}}\mathbf{U}_{\alpha}\right.$
are obtained for each $\alpha\in\mathcal{P}_{D}$, we can choose closed
subspaces $\mathbf{W}_{\alpha}$ in $\mathbf{V}_{\alpha_{\|\cdot\|_{\alpha}}}$
such that
$\mathbf{V}_{\alpha_{\|\cdot\|_{\alpha}}}=\mathbf{U}_{\alpha}\oplus\mathbf{W}_{\alpha}$
holds. Then $\xi_{\mathbf{v}}^{-1}$ is a bijection between the set

$\left(\bigoplus_{\alpha\in\mathcal{P}_{D}}\mathcal{L}\left(\mathbf{U}_{\alpha},\mathbf{W}_{\alpha}\right)\otimes_{a}\mathrm{span}\\{\mathbf{id}_{[\alpha]}\\}\right)\times\mathfrak{M}_{\mathfrak{r}_{k}}\left(\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{D}}\mathbf{U}_{\alpha}\right.\right)$

and the subset
$\mathcal{U}(\mathbf{v})\subset\mathfrak{M}_{\mathfrak{r}}(\mathbf{V}_{D})$
containing $\mathbf{v}.$ To simplify notation, let

$\mathbf{E}_{\mathcal{P}_{D}}(\mathbf{v}):=\left(\bigoplus_{\alpha\in\mathcal{P}_{D}}\mathcal{L}\left(\mathbf{U}_{\alpha},\mathbf{W}_{\alpha}\right)\otimes_{a}\mathrm{span}\\{\mathbf{id}_{[\alpha]}\\}\right).$

It can be shown (see Lemma 3.12 in [9]) that
$\mathbf{w}\in\mathcal{U}(\mathbf{v})$ if and only if there exists a unique

$(\Delta((L_{\alpha})_{\alpha\in\mathcal{P}_{D}}),\mathbf{u})\in\mathbf{E}_{\mathcal{P}_{D}}(\mathbf{v})\times\mathfrak{M}_{\mathfrak{r}_{k}}\left(\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{k}(T_{D})}\mathbf{U}_{\alpha}\right.\right)$

such that

$\displaystyle\mathbf{w}=\xi_{\mathbf{v}}^{-1}(\Delta(L_{\alpha})_{\alpha\in\mathcal{P}_{D}},\mathbf{u})=\left(\bigotimes_{\alpha\in\mathcal{P}_{D}}\exp(L_{\alpha})\right)(\mathbf{u}).$
(2.4)

Put $L:=\Delta((L_{\alpha})_{\alpha\in\mathcal{P}_{D}}),$ thanks to
Proposition 2.5, the equality (2.4) is equivalent to

$\displaystyle\mathbf{w}=\xi_{\mathbf{v}}^{-1}(L,\mathbf{u})=\exp(L)(\mathbf{u}),$
(2.5)

where
$L=\sum_{\alpha\in\mathcal{P}_{D}}L_{\alpha}\otimes\mathbf{id}_{[\alpha]}$ is
a Laplacian-like map. Thus, every tensor in Tucker format is locally
characterised by a full-rank tensor and a Laplacian-like map.

##  3 The set of tensors in tree-based format with fixed tree-based rank

To introduce the set of tensors in tree-based format with fixed tree-based
rank we shall use the minimal subspaces, in particular, Proposition 2.6 in [9]
(see also [6] or [11]). Let $\mathcal{P}_{D}$ be a given partition of $D.$ By
definition of the minimal subspaces $U_{\alpha}^{\min}(\mathbf{v}),$
$\alpha\in\mathcal{P}_{D}$, we have

$\mathbf{v}\in\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{D}}U_{\alpha}^{\min}(\mathbf{v})\right..$

For a given $\alpha\in\mathcal{P}_{D}$ with $\\#\alpha\geq 2$ and any
partition $\mathcal{P}_{\alpha}$ of $\alpha$, we also have

$\mathbf{v}\in\left(\left.{}_{a}\bigotimes_{\beta\in\mathcal{P}_{\alpha}}U_{\beta}^{\min}(\mathbf{v})\right.\right)\otimes_{a}\left(\left.{}_{a}\bigotimes_{\delta\in\mathcal{P}_{D}\setminus\\{\alpha\\}}U_{\delta}^{\min}(\mathbf{v})\right.\right).$

We finally recall a useful result on the relation between minimal subspaces
(see Section 2 in [6]).

###### Proposition 3.1

For any $\alpha\in 2^{D}$ with $\\#\alpha\geq 2$ and any partition
$\mathcal{P}_{\alpha}$ of $\alpha$, it holds

$U_{\alpha}^{\min}(\mathbf{v})\subset\left.{}_{a}\bigotimes_{\beta\in\mathcal{P}_{\alpha}}U_{\beta}^{\min}(\mathbf{v})\right..$

In order to define tree-based tensor format we introduce the three
definitions.

######  Definition 3.2 (Dimension partition tree)

A tree $T_{D}$ is called _a dimension partition tree over $D$_ if

  1. (a)

all vertices $\alpha\in T_{D}$ are non-empty subsets of $D,$

  2. (b)

$D$ is the _root_ of $T_{D},$

  3. (c)

every vertex $\alpha\in T_{D}$ with $\\#\alpha\geq 2$ has at least two sons
and the set of sons of $\alpha$, denoted $S(\alpha)$, is a non-trivial
partition of $\alpha$,

  4. (d)

every vertex $\alpha\in T_{D}$ with $\\#\alpha=1$ has no son and is called a
_leaf_.

The set of leaves is denoted by $\mathcal{L}(T_{D}).$

A straightforward consequence of Definition 3.2 is that the set of leaves
$\mathcal{L}(T_{D})$ coincides with the singletons of $D,$ i.e.,
$\mathcal{L}(T_{D})=\\{\\{j\\}:j\in D\\}$.

######  Definition 3.3 (Levels, depth and partitions)

The _levels_ of the vertices of a dimension partition tree $T_{D}$, denoted by
$\mathrm{level}(\alpha)$, $\alpha\in T_{D}$, are integers defined such that
$\mathrm{level}(D)=0$ and for any pair $\alpha,\beta\in T_{D}$ such that
$\beta\in S(\alpha),$ $\mathrm{level}(\beta)=\mathrm{level}(\alpha)+1$. The
_depth_ 222By using the notion of edge, that is, the connection between one
vertex to another, then our definition of depth coincides with the classical
definition of height, i.e. the longest downward path between the root and a
leaf. of the tree $T_{D}$ is defined as $\mathrm{depth}(T_{D})=\max_{\alpha\in
T_{D}}\mathrm{level}(\alpha).$ Then to each level $k$ of $T_{D}$, $1\leq k\leq
0pt(T_{D})$, is associated a partition of $D:$

$\mathcal{P}_{k}(T_{D})=\\{\alpha\in
T_{D}:\mathrm{level}(\alpha)=k\\}\cup\\{\alpha\in\mathcal{L}(T_{D}):\mathrm{level}(\alpha)<k\\}.$

###### Remark 3.4

Note that for any tree, $\mathcal{P}_{1}(T_{D})=S(D)$ and
$\mathcal{P}_{0pt(T_{D})}(T_{D})=\mathcal{L}(T_{D})$. Also note that some of
the leaves of $T_{D}$ may be contained in several partitions, and if
$\alpha\in\mathcal{L}(T_{D})$, then $\alpha\in\mathcal{P}_{k}(T_{D})$ for
$\mathrm{level}(\alpha)\leq k\leq 0pt(T_{D})$.

For any partition $\mathcal{P}_{k}(T_{D})$ of level $k$, $1\leq k\leq
0pt(T_{D})$, we use the identification

$\mathbf{V}_{D}=\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{k}(T_{D})}\mathbf{V}_{\alpha}\right..$

This leads us to the following definition of the representation of the tensor
space $\mathbf{V}_{D}$ in tree-based format.

###### Definition 3.5

For a tensor space $\mathbf{V}_{D}$ and a dimension partition tree $T_{D}$,
the pair $(\mathbf{V}_{D},T_{D})$ is called a representation of the tensor
space $\mathbf{V}_{D}$ in _tree-based format_ , and corresponds to the
identification of $\mathbf{V}_{D}$ with tensor spaces
$\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{k}(T_{D})}\mathbf{V}_{\alpha}\right.$
of different levels $k$, $1\leq k\leq 0pt(T_{D}).$

###### Remark 3.6

By Proposition 3.1, for each $\mathbf{v}\in\mathbf{V}_{D},$ it holds that

$\mathbf{v}\in\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{1}(T_{D})}U_{\alpha}^{\min}(\mathbf{v})\right.\subset\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{2}(T_{D})}U_{\alpha}^{\min}(\mathbf{v})\right.\subset\cdots\subset\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{0pt(T_{D})}(T_{D})}U_{\alpha}^{\min}(\mathbf{v})\right..$

######  Example 3.7 (Tucker format)

In Figure 3.1, $D=\\{1,2,3,4,5,6\\}$ and

$T_{D}=\\{D,\\{1\\},\\{2\\},\\{3\\},\\{4\\},\\{5\\},\\{6\\}\\}.$

Here $0pt(T_{D})=1$ and $\mathcal{P}_{1}(T_{D})=\mathcal{L}(T_{D}).$ This tree
is related to the basic identification of $\mathbf{V}_{D}$ with
$\left.{}_{a}\bigotimes_{j=1}^{6}V_{j}\right..$

[$\\{1,2,3,4,5,6\\}$[$\\{1\\}$][$\\{2\\}$][$\\{3\\}$]
[$\\{4\\}$][$\\{5\\}$][$\\{6\\}$]]

Figure 3.1: a dimension partition tree with $0pt(T_{D})=1$ (Tucker tree).

###### Example 3.8

In Figure 3.2, $D=\\{1,2,3,4,5,6\\}$ and

$T_{D}=\\{D,\\{1,2,3\\},\\{4,5\\},\\{2,3\\},\\{1\\},\\{2\\},\\{3\\},\\{4\\},\\{5\\},\\{6\\}\\}.$

Here $0pt(T_{D})=3$,
$\mathcal{P}_{1}(T_{D})=\\{\\{1,2,3\\},\\{4,5\\},\\{6\\}\\}$,
$\mathcal{P}_{2}(T_{D})=\\{\\{1\\},\\{2,3\\},\\{4\\},\\{5\\},\\{6\\}\\}$ and
$\mathcal{P}_{3}(T_{D})=\mathcal{L}(T_{D}).$ This tree is related to the
identification of $\mathbf{V}_{D}$ with
$\left.{}_{a}\bigotimes_{j=1}^{6}V_{j}\right.$,
$\mathbf{V}_{D}={V}_{1}\otimes_{a}\mathbf{V}_{23}\otimes_{a}{V}_{4}\otimes_{a}V_{5}\otimes_{a}V_{6}$
and
$\mathbf{V}_{D}=\mathbf{V}_{123}\otimes_{a}\mathbf{V}_{45}\otimes_{a}V_{6}$.

[$\\{1,2,3,4,5,6\\}$[$\\{1,2,3\\}$[$\\{1\\}$][$\\{2,3\\}$[$\\{2\\}$][$\\{3\\}$]]]
[$\\{4,5\\}$[$\\{4\\}$][$\\{5\\}$]][$\\{6\\}$ ]]

Figure 3.2: A dimension partition tree with $0pt(T_{D})=3$.

Let $\mathbb{N}_{0}:=\mathbb{N}\cup\\{0\\}$ denote the set of non-negative
integers. For each $\mathbf{v}\in\mathbf{V}_{D}$, we have that
$(\dim{U}_{\alpha}^{\min}(\mathbf{v}))_{\alpha\in
2^{D}\setminus\\{\emptyset\\}}$ is in $\mathbb{N}_{0}^{2^{\\#D}-1}.$

######  Definition 3.9 (Tree-based rank)

For a given dimension partition tree $T_{D}$ over $D$, we define the _tree-
based rank_ of a tensor $\mathbf{v}\in\mathbf{V}_{D}$ by the tuple
$\mathrm{rank}_{T_{D}}(\mathbf{v}):=(\dim{U}_{\alpha}^{\min}(\mathbf{v}))_{\alpha\in
T_{D}}\in\mathbb{N}_{0}^{\\#T_{D}}.$

######  Definition 3.10 (Admissible ranks)

A tuple $\mathfrak{r}:=(r_{\alpha})_{\alpha\in T_{D}}\in\mathbb{N}^{\\#T_{D}}$
is said to be an _admissible tuple for $T_{D}$_ if there exists
$\mathbf{v}\in\mathbf{V}_{D}$ such that $\dim
U_{\alpha}^{\min}(\mathbf{v})=r_{\alpha}$ for all $\alpha\in T_{D}.$ The set
of admissible ranks for the representation $(\mathbf{V}_{D},T_{D})$ of the
tensor space $\mathbf{V}_{D}$ is denoted by

$\mathcal{AD}(\mathbf{V}_{D},T_{D}):=\\{(\dim
U_{\alpha}^{\min}(\mathbf{v}))_{\alpha\in
T_{D}}:\mathbf{v}\in\mathbf{V}_{D}\\}.$

###### Definition 3.11

Let $T_{D}$ be a given dimension partition tree and fix some tuple
$\mathfrak{r}\in\mathcal{AD}(\mathbf{V}_{D},T_{D})$. Then _the set of tensors
of fixed tree-based rank $\mathfrak{r}$_ is defined by

$\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D},T_{D}):=\left\\{\mathbf{v}\in\mathbf{V}_{D}:\dim{U}_{\alpha}^{\min}(\mathbf{v})=r_{\alpha}\text{
for all }\alpha\in T_{D}\right\\}$ (3.1)

and the _set of tensors of tree-based rank bounded by $\mathfrak{r}$_ is
defined by

$\mathcal{FT}_{\leq\mathfrak{r}}(\mathbf{V}_{D},T_{D}):=\left\\{\mathbf{v}\in\mathbf{V}_{D}:\dim{U}_{\alpha}^{\min}(\mathbf{v})\leq
r_{\alpha}\text{ for all }\alpha\in T_{D}\right\\}.$ (3.2)

For $\mathfrak{r},\mathfrak{s}\in\mathbb{N}_{0}^{\\#T_{D}}$ we write
$\mathfrak{s}\leq\mathfrak{r}$ if and only if $s_{\alpha}\leq r_{\alpha}$ for
all $\alpha\in T_{D}.$ Then for a fixed
$\mathfrak{r}\in\mathcal{AD}(\mathbf{V}_{D},T_{D})$, we have

$\mathcal{FT}_{\leq\mathfrak{r}}(\mathbf{V}_{D},T_{D}):=\bigcup_{\begin{subarray}{c}\mathfrak{s}\leq\mathfrak{r}\\\
\mathfrak{s}\in\mathcal{AD}(\mathbf{V}_{D},T_{D})\end{subarray}}\mathcal{FT}_{\mathfrak{s}}(\mathbf{V}_{D},T_{D}).$
(3.3)

For each partition $\mathcal{P}_{k}(T_{D})$ of $D$, $1\leq k\leq 0pt(T_{D})$,
we can introduce a set of tensors in Tucker format with fixed rank
$\mathfrak{r}_{k}:=(r_{\alpha})_{\alpha\in\mathcal{P}_{k}(T_{D})}$ given by

$\mathfrak{M}_{\mathfrak{r}_{k}}(\mathbf{V}_{D},\mathcal{P}_{k}(T_{D}))=\\{\mathbf{v}\in\mathbf{V}_{D}:\dim
U_{\alpha}^{\min}(\mathbf{v})=r_{\alpha}\text{ for
}\alpha\in\mathcal{P}_{k}(T_{D})\\}.$

###### Theorem 3.12

For a dimension partition tree $T_{D}$ and for
$\mathfrak{r}=(r_{\alpha})_{\alpha\in
T_{D}}\in\mathcal{AD}(\mathbf{V}_{D},T_{D}),$

$\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D},T_{D})=\bigcap_{k=1}^{0pt(T_{D})}\mathfrak{M}_{\mathfrak{r}_{k}}(\mathbf{V}_{D},\mathcal{P}_{k}(T_{D})).$

###### Remark 3.13

We point out that in [9] we introduce a representation of $\mathbf{V}_{D}$ in
Tucker format. Letting $T_{D}^{\text{Tucker}}$ be the Tucker dimension
partition tree (see example 3.7) and given
$\mathfrak{r}\in\mathcal{AD}(\mathbf{V}_{D},T_{D}^{\text{Tucker}})$, the set
of tensors with fixed Tucker rank $\mathfrak{r}$ is defined by

$\mathfrak{M}_{\mathfrak{r}}(\mathbf{V}_{D}):=\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D},T_{D}^{\text{Tucker}})=\left\\{\mathbf{v}\in\mathbf{V}_{D}:\dim
U_{k}^{\min}(\mathbf{v})=r_{k},\,k\in\mathcal{L}(T_{D}^{\text{Tucker}})\right\\}.$

This leads to the following representation of $\mathbf{V}_{D}$ in Tucker
format:

$\mathbf{V}_{D}=\bigcup_{\mathfrak{r}\in\mathcal{AD}(\mathbf{V}_{D},T_{D}^{\text{Tucker}})}\mathfrak{M}_{\mathfrak{r}}(\mathbf{V}_{D}).$

Note that for any tree $T_{D}$ with $0pt(T_{D})=1$,

$\mathfrak{M}_{\mathfrak{r}_{0pt(T_{D})}}(\mathbf{V}_{D},\mathcal{P}_{0pt(T_{D})}(T_{D}))=\mathfrak{M}_{\mathfrak{r}_{0pt(T_{D})}}(\mathbf{V}_{D}).$

Finally, we need to take into account the following situation. Let $T_{D}$ be
the rooted tree given in Figure 3.3. For this rooted tree we have
$0pt(T_{D})=2$ and also

$\displaystyle\mathcal{P}_{1}(T_{D})$
$\displaystyle=\\{\\{1\\},\\{2,3,4,5,6\\}\\},$
$\displaystyle\mathcal{P}_{2}(T_{D})$
$\displaystyle=\\{\\{1\\},\\{2\\},\\{3\\},\\{4\\},\\{5\\},\\{6\\}\\}.$

From Lemma 2.4 in [6] it can be shown that $\dim
U_{\\{1\\}}^{\min}(\mathbf{v})=\dim U_{\\{2,3,4,5,6\\}}^{\min}(\mathbf{v})$
holds for all $\mathbf{v}\in\mathbf{V}_{D}.$ Hence

$\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D},T_{D})=\mathfrak{M}_{\mathfrak{r}_{1}}(\mathbf{V}_{D},\mathcal{P}_{1}(T_{D}))\cap\mathfrak{M}_{\mathfrak{r}_{2}}(\mathbf{V}_{D},\mathcal{P}_{2}(T_{D}))=\mathfrak{M}_{\mathfrak{r}_{2}}(\mathbf{V}_{D},\mathcal{P}_{2}(T_{D}))$

holds because

$\displaystyle\mathfrak{M}_{\mathfrak{r}_{1}}(\mathbf{V}_{D},\mathcal{P}_{1}(T_{D}))$
$\displaystyle=\\{\mathbf{v}\in\mathbf{V}_{D}:\dim
U_{\\{1\\}}^{\min}(\mathbf{v})=r_{\\{1\\}}=\dim
U_{\\{2,3,4,5,6\\}}^{\min}(\mathbf{v})\\}$

contains

$\displaystyle\mathfrak{M}_{\mathfrak{r}_{2}}(\mathbf{V}_{D},\mathcal{P}_{2}(T_{D}))$
$\displaystyle=\\{\mathbf{v}\in\mathbf{V}_{D}:\dim
U_{\\{i\\}}^{\min}(\mathbf{v})=r_{\\{i\\}},\,1\leq i\leq 6\\}.$

[$\\{1,2,3,4,5,6\\}$[$\\{1\\}$][$\\{2,3,4,5,6\\}$[$\\{2\\}$][$\\{3\\}$]
[$\\{4\\}$][$\\{5\\}$][$\\{6\\}$ ]]]

Figure 3.3: A dimension partition tree with $0pt(T_{D})=2.$

Thus in order to avoid this situation we introduce the following definition.

###### Definition 3.14

For a dimension partition tree $T_{D}$ and for
$\mathfrak{r}=(r_{\alpha})_{\alpha\in
T_{D}}\in\mathcal{AD}(\mathbf{V}_{D},T_{D}),$ we will say that
$\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D},T_{D})$ is a proper set of tree-
based tensors with a fixed tree-based rank $\mathfrak{r}$ if

$\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D},T_{D})\neq\mathfrak{M}_{\mathfrak{r}_{k}}(\mathbf{V}_{D},\mathcal{P}_{k}(T_{D}))\text{
holds for }1\leq k\leq 0pt(T_{D}).$

##  4 The geometry of tree-based tensor format

For a dimension partition tree $T_{D}$ and for
$\mathfrak{r}=(r_{\alpha})_{\alpha\in
T_{D}}\in\mathcal{AD}(\mathbf{V}_{D},T_{D}),$ assume that
$\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D},T_{D})$ is a proper set of tree-
based tensors with a fixed tree-based rank $\mathfrak{r}$ such that

$\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D},T_{D})=\bigcap_{k=1}^{0pt(T_{D})}\mathfrak{M}_{\mathfrak{r}_{k}}(\mathbf{V}_{D},\mathcal{P}_{k}(T_{D})).$

Assume that $(\mathbf{V}_{\alpha},\|\cdot\|_{\alpha})$ is a normed space for
each $\alpha\in\mathcal{P}_{k}(T_{D})$ and that $\|\cdot\|_{D}$ is a norm on
the tensor space
$\mathbf{V}_{D}=\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{k}(T_{D})}\mathbf{V}_{\alpha}\right.$
such that (2.3) holds for $1\leq k\leq 0pt(T_{D}).$

From Theorem 2.6 we have that for each $1\leq k\leq 0pt(T_{D})$ the collection
$\mathcal{A}_{k}=\\{(\mathcal{U}^{(k)}(\mathbf{v}),\xi_{\mathbf{v}}^{(k)})\\}_{\mathbf{v}\in\mathfrak{M}_{\mathfrak{r}_{k}}(\mathbf{V}_{D},T_{D})}$
is a $\mathcal{C}^{\infty}$-atlas for
$\mathfrak{M}_{\mathfrak{r}_{k}}(\mathbf{V}_{D},T_{D})$ and hence
$\mathfrak{M}_{\mathfrak{r}_{{k}}}(\mathbf{V}_{D},T_{D})$ is a
$\mathcal{C}^{\infty}$-Banach manifold modelled on

$\left(\bigoplus_{\alpha\in\mathcal{P}_{k}(T_{D})}\mathcal{L}\left(\mathbf{U}_{\alpha},\mathbf{W}_{\alpha}\right)\otimes_{a}\mathrm{span}\\{\mathbf{id}_{[\alpha]}\\}\right)\times\mathbb{R}^{\bigtimes_{\alpha\in\mathcal{P}_{k}(T_{D})}r_{\alpha}},$

where $\mathbf{U}_{\alpha}=U_{\alpha}^{\min}(\mathbf{v})$ is a
$r_{\alpha}$-dimensional subspace of $\mathbf{V}_{\alpha}$ for each
$\alpha\in\mathcal{P}_{k}(T_{D})$ where
$\mathbf{v}\in\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{k}(T_{D})}\mathbf{U}_{\alpha}\right.$
and $\mathbf{W}_{\alpha}$ is a closed subspace of
$\mathbf{V}_{\alpha_{\|\cdot\|_{\alpha}}}$ such that
$\mathbf{V}_{\alpha_{\|\cdot\|_{\alpha}}}=\mathbf{U}_{\alpha}\oplus\mathbf{W}_{\alpha},$
where $\mathbf{V}_{{\alpha}_{\|\cdot\|_{\alpha}}}$ is the completion of
$\mathbf{V}_{\alpha}$ for $\alpha\in\mathcal{P}_{k}(T_{D}).$

To simplify notation, here we write

$\mathbf{E}_{k}(\mathbf{v}):=\left(\bigoplus_{\alpha\in\mathcal{P}_{k}(T_{D})}\mathcal{L}\left(\mathbf{U}_{\alpha},\mathbf{W}_{\alpha}\right)\otimes_{a}\mathrm{span}\\{\mathbf{id}_{[\alpha]}\\}\right)$

for $1\leq k\leq 0pt(T_{D}).$ Next, we characterise the elements in the set

$\bigcap_{k=1}^{0pt(T_{D})}\xi_{\mathbf{v}}^{(k)}(\mathcal{U}^{(k)}(\mathbf{v}))=\bigcap_{k=1}^{0pt(T_{D})}\mathbf{E}_{k}(\mathbf{v})\times\bigcap_{k=1}^{0pt(T_{D})}\mathfrak{M}_{\mathbf{r}_{k}}\left(\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{k}(T_{D})}\mathbf{U}_{\alpha}\right.\right).$

By using Remark 3.6 we have

$\bigcap_{k=1}^{0pt(T_{D})}\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{k}(T_{D})}\mathbf{U}_{\alpha}\right.=\bigcap_{k=1}^{0pt(T_{D})}\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{k}(T_{D})}U_{\alpha}^{\min}(\mathbf{v})\right.=\left.{}_{a}\bigotimes_{\delta\in\mathcal{P}_{1}(T_{D})}U_{\delta}^{\min}(\mathbf{v})\right.=\left.{}_{a}\bigotimes_{\delta\in\mathcal{P}_{1}(T_{D})}\mathbf{U}_{\delta}\right..$

It allows us to take into account the open set

$\displaystyle\mathcal{O}(\mathbf{v}):=\bigcap_{k=1}^{0pt(T_{D})}\mathfrak{M}_{\mathfrak{r}_{k}}\left(\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{k}(T_{D})}\mathbf{U}_{\alpha}\right.\right)\subset\left(\left.{}_{a}\bigotimes_{\delta\in\mathcal{P}_{1}(T_{D})}\mathbf{U}_{\delta}\right.\right)\bigcap\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D},T_{D}),$
(4.1)

in
$\left.{}_{a}\bigotimes_{\delta\in\mathcal{P}_{1}(T_{D})}U_{\delta}^{\min}(\mathbf{v})\right.,$
which is the smaller tensor product of minimal subspaces that contains
$\mathbf{v}.$

Now,

$\mathbf{E}(\mathbf{v}):=\bigcap_{k=1}^{0pt(T_{D})}\mathbf{E}_{k}(\mathbf{v})$

is a linear closed subspace in the Banach space $\mathbf{E}_{k}(\mathbf{v})$
for $1\leq k\leq 0pt(T_{D})$ and also in
$\mathcal{L}(\mathbf{V}_{D_{\|\cdot\|_{D}}},\mathbf{V}_{D_{\|\cdot\|_{D}}}).$
Hence $\mathbf{E}(\mathbf{v})$ is a Banach space. Moreover, given
$L\in\mathbf{E}(\mathbf{v})$, for each $1\leq k\leq 0pt(T)$ there exists a
unique

$(L_{\alpha}^{(k)})_{\alpha\in\mathcal{P}_{k}(T_{D})}\in\mathop{\mathchoice{\raise-2.20001pt\hbox{\huge$\times$}}{\raise-0.50003pt\hbox{\Large$\times$}}{\hbox{\large$\times$}}{\times}}_{\alpha\in\mathcal{P}_{k}(T_{D})}\mathcal{L}(\mathbf{U}_{\alpha},\mathbf{W}_{\alpha})$

such that

$L=\Delta((L_{\alpha}^{(k)})_{\alpha\in\mathcal{P}_{k}(T_{D})})=\sum_{\alpha\in\mathcal{P}_{k}(T_{D})}L_{\alpha}^{(k)}\otimes\mathbf{id}_{[\alpha]}$

holds. From (2.5), each
$(L,\mathbf{u})\in\mathbf{E}(\mathbf{v})\times\mathcal{O}(\mathbf{v})$
satisfies that

$(\xi_{\mathbf{v}}^{(k)})^{-1}((L,\mathbf{u}))=\exp(L)(\mathbf{u})\in\mathcal{U}^{(k)}(\mathbf{v})$

for $1\leq k\leq 0pt(T_{D}).$ Hence the image of $(L,\mathbf{u})$ by
$(\xi_{\mathbf{v}}^{(k)})^{-1}$ is independent on the index $k.$ Thus
$(\xi_{\mathbf{v}}^{(k)})^{-1}$ is a bijection that maps
$\mathbf{E}(\mathbf{v})\times\mathcal{O}(\mathbf{v})$ onto a subset
$\mathcal{W}(\mathbf{v})\subset\bigcap_{l=1}^{0pt(T_{D})}\mathcal{U}^{(l)}(\mathbf{v})$
containing $\mathbf{v}$ for each $1\leq k\leq 0pt(T_{D}).$ It allows to we
define the bijection

$\boldsymbol{\xi}_{\mathbf{v}}:\mathcal{W}(\mathbf{v})\longrightarrow\mathbf{E}(\mathbf{v})\times\mathcal{O}(\mathbf{v})$

by
$\boldsymbol{\xi}_{\mathbf{v}}(\mathbf{w})=\xi_{\mathbf{v}}^{(k)}(\exp(L)(\mathbf{u}))=(L,\mathbf{u}).$

Then the following result is straightforward.

###### Theorem 4.1

Let $T_{D}$ be a dimension partition tree with $0pt(T_{D})\geq 2,$ and
$\mathfrak{r}=(r_{\alpha})_{\alpha\in
T_{D}}\in\mathcal{AD}(\mathbf{V}_{D},T_{D})$ such that
$\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D},T_{D})$ is a proper set of tree-
based tensors with a fixed tree-based rank $\mathfrak{r}.$ Assume that
$(\mathbf{V}_{\alpha},\|\cdot\|_{\alpha})$ is a normed space for each
$\alpha\in T_{D}\setminus\\{D\\}$ and that $\|\cdot\|_{D}$ is a norm on the
tensor space
$\mathbf{V}_{D}=\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{k}(T_{D})}\mathbf{V}_{\alpha}\right.$
is such that (2.3) holds for $1\leq k\leq 0pt(T_{D}).$ Then the collection

$\mathcal{B}=\\{(\mathcal{W}(\mathbf{v}),\boldsymbol{\xi}_{\mathbf{v}})\\}_{\mathbf{v}\in\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D},T_{D})}$

is a $\mathcal{C}^{\infty}$-atlas for
$\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D},T_{D})$, and hence
$\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D},T_{D})$ is a
$\mathcal{C}^{\infty}$-Banach manifold modelled on

$\mathbf{E}\times\mathbb{R}^{\bigtimes_{\alpha\in\mathcal{P}_{1}(T_{D})}r_{\alpha}},$

where

$\mathbf{E}=\bigcap_{k=1}^{0pt(T_{D})}\left(\bigoplus_{\alpha\in\mathcal{P}_{k}(T_{D})}\mathcal{L}\left(\mathbf{U}_{\alpha},\mathbf{W}_{\alpha}\right)\otimes_{a}\mathrm{span}\\{\mathbf{id}_{[\alpha]}\\}\right).$

Here $\mathbf{U}_{\alpha}=U_{\alpha}^{\min}(\mathbf{v})$ is a
$r_{\alpha}$-dimensional subspace of $\mathbf{V}_{\alpha}$ for each $\alpha\in
T_{D}\setminus\\{D\\}$ where
$\mathbf{v}\in\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{k}(T_{D})}\mathbf{U}_{\alpha}\right.$
for $1\leq k\leq 0pt(T_{D})$ and $\mathbf{W}_{\alpha}$ is a closed subspace of
$\mathbf{V}_{\alpha_{\|\cdot\|_{\alpha}}}$ such that
$\mathbf{V}_{\alpha_{\|\cdot\|_{\alpha}}}=\mathbf{U}_{\alpha}\oplus\mathbf{W}_{\alpha},$
where $\mathbf{V}_{{\alpha}_{\|\cdot\|_{\alpha}}}$ is the completion of
$\mathbf{V}_{\alpha}$ for $\alpha\in T_{D}\setminus\\{D\\}.$

###  4.1 $\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D},T_{D})$ as embedded sub-
manifold of $\mathfrak{M}_{\mathfrak{r}_{{k}}}(\mathbf{V}_{D},T_{D})$ for
$1\leq k\leq 0pt(T_{D})$

By construction, the natural ambient space of the manifold
$\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D},T_{D})$ is any manifold
$\mathfrak{M}_{\mathfrak{r}_{{k}}}(\mathbf{V}_{D},T_{D})$ for $1\leq k\leq
0pt(T_{D}).$ We claim that the natural inclusion map
$\mathfrak{i}:\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D},T_{D})\longrightarrow\mathfrak{M}_{\mathfrak{r}_{{k}}}(\mathbf{V}_{D},T_{D})$
given by $\mathfrak{i}(\mathbf{v})=\mathbf{v}$ is also written in local
coordinates as the natural inclusion map. Indeed, for
$\mathbf{v}\in\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D},T_{D}),$ the open set
$\mathcal{W}(\mathbf{v})\subset\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D},T_{D})$
and hence

$\mathfrak{i}:\mathcal{W}(\mathbf{v})\longrightarrow\mathcal{U}^{(k)}(\mathbf{v})$

is the identity map on $\mathcal{W}(\mathbf{v})$, that is,
$\mathfrak{i}|_{\mathcal{W}(\mathbf{v})}=id_{\mathcal{W}(\mathbf{v})}.$ Thus

$(\xi_{\mathbf{v}}^{(k)}\circ\mathfrak{i}\circ\boldsymbol{\xi}^{-1}_{\mathbf{v}}):\mathbf{E}(\mathbf{v})\times\mathcal{O}(\mathbf{v})\longrightarrow\mathbf{E}_{k}(\mathbf{v})\times\mathfrak{M}_{\mathfrak{r}_{k}}\left(\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{k}(T_{D})}\mathbf{U}_{\alpha}\right.\right)$

is the natural inclusion map. Hence its derivative

$\mathrm{T}_{\mathbf{v}}\mathfrak{i}=(\xi_{\mathbf{v}}\circ\mathfrak{i}\circ\boldsymbol{\xi}_{\mathbf{v}}^{-1})^{\prime}(\boldsymbol{\xi}_{\mathbf{v}}(\mathbf{v})):\mathbf{E}(\mathbf{v})\times\left(\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{1}(T_{D})}\mathbf{U}_{\alpha}\right.\right)\longrightarrow\mathbf{E}_{k}(\mathbf{v})\times\left(\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{k}(T_{D})}\mathbf{U}_{\alpha}\right.\right)$

is also the natural inclusion map which is clearly injective.

In order to prove that $\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D},T_{D})$ is
an embedded sub-manifold of
$\mathfrak{M}_{\mathfrak{r}_{{k}}}(\mathbf{V}_{D},T_{D})$ for $1\leq k\leq
0pt(T_{D})$, we need to check the following two conditions for each $1\leq
k\leq 0pt(T_{D}):$

  1. (C1)

The map $\mathfrak{i}$ should be an immersion. From Proposition 4.1 in [9], it
is true when the linear map

$T_{\mathbf{v}}\mathfrak{i}=(\xi_{\mathbf{v}}\circ\mathfrak{i}\circ\boldsymbol{\xi}_{\mathbf{v}}^{-1})^{\prime}(\boldsymbol{\xi}_{\mathbf{v}}(\mathbf{v})):\mathrm{T}_{\mathbf{v}}\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D},T_{D})\longrightarrow\mathrm{T}_{\mathbf{v}}\mathfrak{M}_{\mathfrak{r}_{k}}(\mathbf{V}_{D},T_{D})$

is injective and
$T_{\mathbf{v}}\mathfrak{i}(\mathrm{T}_{\mathbf{v}}\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D},T_{D}))\in\mathbb{G}\left(\mathrm{T}_{\mathbf{v}}\mathfrak{M}_{\mathfrak{r}_{k}}(\mathbf{V}_{D},T_{D})\right)$

  2. (C2)

The map

$\mathfrak{i}:\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D},T_{D})\longrightarrow\mathfrak{i}\left(\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D},T_{D})\right)$

is a topological homeomorphism.

In consequence, to obtain the desired result we only need to prove that for
each $\mathbf{v}\in\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D},T_{D})$ the
tangent space

$\mathrm{T}_{\mathbf{v}}\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D},T_{D})=\bigcap_{k=1}^{0pt(T_{D})}\mathrm{T}_{\mathbf{v}}\mathfrak{M}_{\mathfrak{r}_{{k}}}(\mathbf{V}_{D},T_{D})=\mathbf{E}(\mathbf{v})\times\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{1}(T_{D})}\mathbf{U}_{\alpha}\right.$

belongs to

$\mathbb{G}\left(\mathbf{E}_{k}(\mathbf{v})\times\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{k}(T_{D})}\mathbf{U}_{\alpha}\right.\right)=\mathbb{G}\left(\mathbf{E}_{k}(\mathbf{v})\right)\times\mathbb{G}\left(\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{k}(T_{D})}\mathbf{U}_{\alpha}\right.\right).$

Clearly

$\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{1}(T_{D})}\mathbf{U}_{\alpha}\right.\in\mathbb{G}\left(\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{k}(T_{D})}\mathbf{U}_{\alpha}\right.\right),$

because
$\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{k}(T_{D})}\mathbf{U}_{\alpha}\right.$
is a finite dimensional vector space. From Lemma 2.4 we have

$\mathbf{E}_{k}(\mathbf{v})\in\mathbb{G}\left(\mathcal{L}(\mathbf{V}_{D_{\|\cdot\|_{D}}},\mathbf{V}_{D_{\|\cdot\|_{D}}})\right)$

for $1\leq k\leq 0pt(T_{D}).$ The second statement of Lemma 4.14 in [9]
implies

$\mathbf{E}(\mathbf{v})=\bigcap_{k=1}^{0pt(T_{D})}\mathbf{E}_{k}(\mathbf{v})\in\mathbb{G}\left(\mathcal{L}(\mathbf{V}_{D_{\|\cdot\|_{D}}},\mathbf{V}_{D_{\|\cdot\|_{D}}})\right).$

Thus we have the following theorem.

###### Theorem 4.2

Let $T_{D}$ be a dimension partition tree over $D$ and
$\mathfrak{r}\in\mathcal{AD}(\mathbf{V}_{D},T_{D})$ such that
$\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D},T_{D})$ is a proper set of tree-
based tensors with a fixed tree-based rank $\mathfrak{r}.$ Assume that
$(\mathbf{V}_{\alpha},\|\cdot\|_{\alpha})$ is a normed space for each
$\alpha\in T_{D}\setminus\\{D\\}$ and let $\|\cdot\|_{D}$ be a norm on the
tensor space $\mathbf{V}_{D}$ such that (2.3) holds for $1\leq k\leq
0pt(T_{D}).$ Then $\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D},T_{D})$ is an
embedded sub-manifold of
$\mathfrak{M}_{\mathfrak{r}_{{k}}}(\mathbf{V}_{D},T_{D})$ for $1\leq k\leq
0pt(T_{D}).$

Observe that we can also consider the natural inclusion map $\mathfrak{i}$
from $\mathfrak{M}_{\mathfrak{r}_{{k}}}(\mathbf{V}_{D},T_{D})$ to
$\mathbf{V}_{D_{\|\cdot\|_{D}}}.$ Under the assumptions of Theorem 4.2, by
using Theorem 4.14 of [9], we have that
$\mathfrak{M}_{\mathfrak{r}_{{k}}}(\mathbf{V}_{D},T_{D})$ is an immersed sub-
manifold of $\mathbf{V}_{D_{\|\cdot\|_{D}}}$ and, for each
$\mathbf{v}\in\mathfrak{M}_{\mathfrak{r}_{{k}}}(\mathbf{V}_{D},T_{D}),$ the
tangent space

$\mathrm{T}_{\mathbf{v}}\mathfrak{M}_{\mathfrak{r}_{{k}}}(\mathbf{V}_{D},T_{D})=\mathbf{E}_{k}(\mathbf{v})\times\left(\left.{}_{a}\bigotimes_{\alpha\in\mathcal{P}_{k}(T_{D})}\mathbf{U}_{\alpha}\right.\right)$

is linearly isomorphic to the linear space
$\mathrm{T}_{\mathbf{v}}\mathfrak{i}\left(\mathrm{T}_{\mathbf{v}}\mathfrak{M}_{\mathfrak{r}_{{k}}}(\mathbf{V}_{D},T_{D})\right)\in\mathbb{G}(\mathbf{V}_{D_{\|\cdot\|_{D}}}).$
Then, by using that $\mathrm{T}_{\mathbf{v}}\mathfrak{i}$ is injective, we
obtain

$\mathrm{T}_{\mathbf{v}}\mathfrak{i}\left(\mathrm{T}_{\mathbf{v}}\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D},T_{D})\right)=\mathrm{T}_{\mathbf{v}}\mathfrak{i}\left(\bigcap_{k=1}^{0pt(T_{D})}\mathrm{T}_{\mathbf{v}}\mathfrak{M}_{\mathfrak{r}_{{k}}}(\mathbf{V}_{D},T_{D})\right)=\bigcap_{k=1}^{0pt(T_{D})}\mathrm{T}_{\mathbf{v}}\mathfrak{i}\left(\mathrm{T}_{\mathbf{v}}\mathfrak{M}_{\mathfrak{r}_{{k}}}(\mathbf{V}_{D},T_{D})\right)\in\mathbb{G}(\mathbf{V}_{D_{\|\cdot\|_{D}}}),$

also by Lemma 4.14 in [9], and it is linearly isomorphic to
$\mathrm{T}_{\mathbf{v}}\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D},T_{D}).$
Thus, also $\mathcal{FT}_{\mathfrak{r}}(\mathbf{V}_{D},T_{D})$ is an immersed
sub-manifold in $\mathbf{V}_{D_{\|\cdot\|_{D}}}.$

## References

  * [1] P. A. Absil, R. Mahoni, and R. Sepulchre, _Optimization Algorithms on Matrix Manifolds_ , Princeton University Press, 2008.
  * [2] M. Bachmayr, R. Schneider, and A. Uschmajew,  Tensor networks and hierarchical tensors for the solution of high-dimensional partial differential equations.  _Found. Comput. Math_ 16 (2016), pp. 1423–1472.
  * [3] G. Ceruti, C. Lubich, and H. Walach,  Time integration of tree tensor networks, https://arxiv.org/abs/2002.11392 (2020).
  * [4] A. Cichocki, N. Lee, I. Oseledets, A.-H. Phan, Q. Zhao, and D. Mandic,  Tensor networks for dimensionality reduction and large-scale optimization: Part 1 low-rank tensor decompositions.  Foundations and Trends® in Machine Learning, 9 4-5 (2016), pp. 249–429.
  * [5] A. Cichocki, A.-H. Phan, Q. Zhao, N. Lee, I. Oseledets, M. Sugiyama, and D. Mandic,  Tensor networks for dimensionality reduction and large-scale optimization: Part 2 applications and future perspectives.  Foundations and Trends® in Machine Learning, 9 6 (2017), pp. 431–673.
  * [6] A. Falcó and W. Hackbusch,  On minimal subspaces in tensor representations.  _Found. Comput. Math_ 12 (2012), pp. 765-803.
  * [7] A. Falcó, W. Hackbusch, and A. Nouy,  Geometric Structures in Tensor Representations (Final Release).  https://arxiv.org/abs/1505.03027 (2015).
  * [8] A. Falcó, W. Hackbusch, and A. Nouy,  Tree-based tensor formats.  SeMA Journal (2018).
  * [9] A. Falcó, W. Hackbusch and A. Nouy, On the Dirac-Frenkel Variational Principle on Tensor Banach Spaces. _Found. Comput. Math._ 19 (2019), 159-204.
  * [10] E. Grelier, A. Nouy, and M. Chevreuil,  Learning with tree-based tensor formats.  https://arxiv.org/abs/1811.04455, (2018).
  * [11] W. Hackbusch, _Tensor spaces and numerical tensor calculus._ 2nd ed. Springer–Verlag (2019).
  * [12] W. Hackbusch and S. Kühn, A new scheme for the tensor representation. _J. Fourier Anal. Appl._ 15 (2009), pp. 706–722.
  * [13] S. Holtz, Th. Rohwedder, and R. Schneider, On manifold of tensors of fixed TT rank. _Numer. Math._ 121 (2012), pp. 701–731.
  * [14] O. Koch and C. Lubich, Dynamical tensor approximation. _SIAM J. Matrix Anal. Appl._ 31 (2010), pp. 2360-2375.
  * [15] T. G. Kolda and B. W. Bader,  Tensor decompositions and applications.  SIAM Review, 51 3 (2009), pp. 455–500.
  * [16] B. Michel and A. Nouy,  Learning with tree tensor networks: complexity estimates and model selection, https://arxiv.org/abs/2007.01165 (2020).
  * [17] A. Nouy,  Low-Rank Methods for High-Dimensional Approximation and Model Order Reduction, in Model Reduction and Approximation: Theory and Algorithms (P. Benner , M. Ohlberger , A. Cohen and K Willcox, eds),  SIAM, Philadelphia, PA, 2017, pp. 171-226.
  * [18] A. Nouy,  Low-Rank Tensor Methods for Model Order Reduction, in Handbook of Uncertainty Quantification (R. Ghanem, D. Higdon and H. Owhadi, eds).  Springer International Publishing, 2017, pp. 857–882.
  * [19] R. Orús,  Tensor networks for complex quantum systems.  Nature Reviews Physics, 1 9 (2019), pp. 538–550.
  * [20] I. V. Oseledets, Tensor-train decomposition. _SIAM J. Sci. Comput._ 33 (2011), pp. 2295–2317.
  * [21] E. Stoudenmire and D. J. Schwab,  Supervised learning with tensor networks, in Advances in Neural Information Processing Systems 30th Annual Conference on Neural Information Processing Systems 2016 (D. D. Lee, M. Sugiyama, U. von Luxburg, I. Guyon and R. Garnett, eds) 2016, pp. 4799–4807.
  * [22] A. Uschmajew and B. Vandereycken, The geometry of algorithms using hierarchical tensors. _Linear Algebra and its Applications_ , 439 1 (2013), pp. 133–166.
  * [23] A. Uschmajew and B. Vandereycken,  Geometric Methods on Low-Rank Matrix and Tensor Manifolds, in Handbook of Variational Methods for Nonlinear Geometric Data (Ph. Grohs, M. Holler and A. Weinmann, eds),  Springer International Publishing, Cham, 2020, pp. 261–313.


/pgfplots/ybar legend/.style=
/pgfplots/legend image code/.code=
(0cm,0cm) rectangle (3pt,0.8em);,

Autonomous vehicles require a precise understanding of their environment to navigate safely.
Reliable identification of unknown objects, especially those that are absent during training, such as wild animals, is critical due to their potential to cause serious accidents.
Significant progress in semantic segmentation of anomalies has been driven by the availability of out-of-distribution (OOD) benchmarks.
However, a comprehensive understanding of scene dynamics requires the segmentation of individual objects, and thus the segmentation of instances is essential.
Development in this area has been lagging, largely due to the lack of dedicated benchmarks.
To address this gap, we have extended the most commonly used anomaly segmentation benchmarks to include the instance segmentation task.
Our evaluation of anomaly instance segmentation methods shows that this challenge remains an unsolved problem.
The benchmark website and the competition page can be found at: <https://vision.rwth-aachen.de/oodis>.

[regular]envelope<EMAIL_ADDRESS>
§ INTRODUCTION

Annotation example for the previous semantic annotation of the RoadAnomaly21 dataset (top) and the extended annotation labels (bottom) for our newly proposed benchmark.

Modern segmentation methods [Cheng et al., 2022, Chen et al., 2018] perform well on curated closed-world datasets with a fixed set of classes.
However, models trained with a fixed training set fall short of solving the task when unexpected objects are present [Hein et al., 2019, Hendrycks and Gimpel, 2018].
These anomalies often cause models to misclassify, assigning known classes to unknown objects [Guo et al., 2017, Kendall and Gal, 2017].
To prevent such behavior in real world applications, it is important to design or adapt models to handle such anomalies.
The task of anomaly detection spans multiple modalities [Wong et al., 2019, Bergmann et al., 2022, Park et al., 2020, Maag et al., 2022], applications [Bergmann et al., 2019, Li et al., 2022], and tasks [Du et al., 2021, Yang et al., 2022, Tian et al., 2022].
The particular focus of this work is the anomaly instance segmentation task, that aims to provide segmentation models with the ability to segment out-of-distribution (OOD) objects.
This task is particularly critical for autonomous driving scenarios, where a recognition error can cause serious accidents.
A collision with lost cargo on the road or with livestock could be life-threatening.
To evaluate the performance of anomaly segmentation methods, a number of benchmarks have been proposed [Pinggera et al., 2016, Chan et al., 2021].

While anomaly segmentation [Nayal et al., 2023, Tian et al., 2022, Liang et al., 2022] methods achieve exciting results on popular benchmarks, the area of anomaly instance segmentation remains unexplored.
Early datasets [Pinggera et al., 2016] for anomaly segmentation included partial instance annotations of anomalies, but recently proposed datasets omit instance information [Blum et al., 2021, Chan et al., 2021].
However, instance segmentation is critical for understanding complex scenes with multiple anomalous objects, such as cows and sheep as shown in Figure <ref>, that may appear in a group.
Previous anomaly segmentation approaches that operate on a pixel level would fail to distinguish individual objects.
Understanding these objects separately provides context about the potential dynamics of a scene, improving downstream tasks such as navigation or planning.
We hypothesize that recent advances in open set [Wong et al., 2019, Hwang et al., 2021] and class-agnostic [Kirillov et al., 2023] instance segmentation have encouraged research in the area of anomaly instance segmentation, which was previously too challenging.
Recently, three works following different paradigms proposed to solve the task of anomaly instance segmentation [Gasperini et al., 2023, Rai et al., 2023, Nekrasov et al., 2023].
However, each of these works proposes a different evaluation procedure.

To address this limitation, we propose a benchmark and evaluate existing methods in a unified manner.
We extend the labels of popular anomaly segmentation datasets [Blum et al., 2021, Chan et al., 2021] to instance segmentation.
These datasets provide diverse real-world cases of road anomalies with precise annotations.
We reuse the Average Precision (AP) metric [Hariharan et al., 2014] for instance evaluation similarly to the Cityscapes setup [Cordts et al., 2016], with a slight modification to evaluate instances as small as 10 pixels in size.
In comparison to the semantic anomaly benchmarks, the AP metric avoids size bias and requires high precision for smaller anomalous objects.
This is particularly important in the context of autonomous driving, where detecting anomalies in the distance is critical to give the system time to react.

To this end, we re-annotated anomalies within the Fishyscapes [Blum et al., 2021], RoadAnomaly21, and RoadObstacle21 [Chan et al., 2021] datasets
to evaluate anomaly instance segmentation methods.
We apply publicly available instance segmentation methods on both validation and test set and provide qualitative evaluation of the results.
Our evaluations show that while current anomaly segmentation methods perform well on semantic anomaly segmentation, instance segmentation methods achieve moderate performance, suggesting a considerable space for improvement.
We make validation data available on our challenge website, and open a submission portal where new approaches can be submitted.

§ RELATED WORK

Out-of-Distribution (OOD) Datasets have primarily focused on classification tasks, with several benchmarks recently introduced [Yang et al., 2022, Zhang et al., 2023].
A common evaluation task is disentanglement of two classification datasets such as CIFAR and SVHN.
Methods such as deep ensembles [Lakshminarayanan et al., 2017] and Monte Carlo dropout [Srivastava et al., 2014], while performing well on OOD classification, show limited usefulness in anomaly segmentation tasks [Chan et al., 2021].
Open-set instance segmentation [Hwang et al., 2021, Wong et al., 2019] assumes the presence of OOD data during training, a condition not applicable to anomaly segmentation where completely unseen objects may appear [Gasperini et al., 2023].
In autonomous driving, novel evaluation schemes have been proposed for detection tasks [Du et al., 2021, Li et al., 2022].
However, these works do not address the need for precise pixel-level mapping in monocular driving detection setups.
Our work explores the segmentation of anomaly instances, which allows accurate prediction of individual, previously unseen, objects.

Anomaly Segmentation Datasets.
Anomaly segmentation has received significant attention with the emergence of several recent datasets and benchmarks [Pinggera et al., 2016, Blum et al., 2021, Chan et al., 2021].
The Lost and Found (L&F) dataset [Pinggera et al., 2016] introduced the task of anomaly segmentation in a camera setup similar to the one used for the Cityscapes dataset [Cordts et al., 2016].
L&F has annotations limited to the road area and anomaly classes; however, it has questionable labels that include bicycles and kids as anomalies [Blum et al., 2021].
To fully control for anomalies in the training and test sets, the CAOS benchmark [Hendrycks et al., 2022] introduces a real dataset based on BDD100K [Yu et al., 2020], treating certain inlier classes as anomalies, and a synthetic dataset for training and testing.
FishyScapes Lost and Found (FS L&F) [Blum et al., 2021] reannotates images from L&F to extend in-distribution regions outside of the road class and introduces a separate benchmark with artificial anomalies.
Despite its popularity, FS L&F lacks anomaly instance segmentation and it is constrained to lost cargo on the road.
To solve the diversity issue, SegmentMeIfYouCan [Chan et al., 2021] introduces a diverse dataset with real anomalies on roads, which are not limited to the Cityscapes camera perspective.
In past years, evaluation on FS L&F and SegmentMeIfYouCan dataset has been a standard practice.
However, instance annotations are missing from these datasets.
Our work aims to extend these popular benchmarks by providing accurate instance annotations.

Anomaly Segmentation Methods.
Segmentation of anomaly instances has been underexplored until recently.
There are previous works in open-set instance segmentation [Wong et al., 2019, Hwang et al., 2021]. However, they rely on unknown objects present in the training set; and methods that rely on depth cues [Singh et al., 2020] that are not applicable in general case.
In general anomaly instance segmentation methods produce per-pixel anomaly scores, while providing anomaly instances too.
U3HS [Gasperini et al., 2023] uses uncertainty in semantic predictions to guide the region segmentation, and then clusters predicted class-agnostic instance embeddings.
Mask2Anomaly [Rai et al., 2023] applies modifications to the Mask2Former [Cheng et al., 2022] architecture to produce reliable semantic anomaly scores in background regions, and uses a connected components on anomaly scores with a strategy to remove false-positives using intersections with in-distribution predictions.
UGainS [Nekrasov et al., 2023] combines the RbA anomaly segmentation method [Nayal et al., 2023] with an interactive segmentation model [Kirillov et al., 2023] to predict instances using point prompting.
Given the limited number of specialized methods for anomaly instance segmentation, we evaluate these models and analyze their performance, offering insights into their practical applications and limitations.

§ BENCHMARK DESIGN.

Anomaly segmentation as a task attempts to identify unexpected objects unknown during training.
Common examples include a deer or a cardboard box that may appear in the middle of the road.
Per-pixel segmentation does not provide sufficient information for downstream tasks such as tracking or navigation.
The more challenging problem of instance segmentation remains under-explored and lacks accessible benchmarks.
This benchmark addresses the lack of test evaluation protocols available to the community.

We aim to fill the gap by extending the labels of SegmentMeIfYouCan [Chan et al., 2021] and FS L&F [Blum et al., 2021] datasets for instance segmentation.
We merge these datasets into a unified benchmark and adopt commonly used Average Precision (AP) metrics [Lin et al., 2014], that closely follows the Cityscapes [Cordts et al., 2016] segmentation benchmark.

We use three datasets for anomaly segmentation: RoadAnomaly21 and RoadObstacle21 from SegmentMeIfYouCan [Chan et al., 2021], and FS L&F [Blum et al., 2021].
These are the standard benchmarks for the task, and they complement each other in label diversity well (see Figure <ref>).
To maintain data integrity, we keep the test sets from the datasets intact, using $100$ images from RoadAnomaly21, $412$ from RoadObstacle21, and $275$ from FS L&F as our full test sets.
In addition, we provide a relabeled validation set of 100 images from FS L&F.

The test set contains three relabeled datasets with different properties, but shares a common in-distribution dataset.
For the submission to the benchmark, we allow models trained on $19$ Cityscapes [Cordts et al., 2016] classes as the in-distribution dataset, and allow the use of auxiliary data, such as COCO [Lin et al., 2014] to introduce virtual anomalies, similar to other anomaly segmentation works [Grcić et al., 2022, Nayal et al., 2023, Tian et al., 2022, Di Biase et al., 2021, Chan et al., 2021, Grcić et al., 2023].
It is important to note that we expect no explicit supervision to segment unknowns, much like in the real world, we do not know what kind of anomalies we will encounter.
The benchmark data contains three classes: inlier, outlier, and ignore.
In-distribution regions contain classes known to Cityscapes; ignore regions are ambiguous regions that neither contain anomalies nor are in-distribution regions; and the outlier class contains anomalous instances (see Figure <ref>).
Ignore regions are ambiguous regions for which a class cannot be defined; common cases in Cityscapes are: bridges, advertisement posts, back side of street signs and dark regions where the class could not be determined.
We omit ignore regions in evaluation and discard cases that overlap significantly with these regions.
We evaluate predictions only for the outlier class, without focusing on evaluation of in-distribution predictions.
To calculate the final Average Precision (AP) score, we compute a weighted average based on the number of images in each dataset.

Labeling Policy.
In RoadAnomaly21, anomalies are of arbitrary size, located anywhere on the image, containing highly diverse samples.
Each individual object, such as an animal or object, is labeled as an individual object without introducing group labels.
FS L&F mainly contains anomalies on the road, separate objects such as stacked boxes, which are treated as separate instances.
Only ambiguous regions are treated as ignore for RoadAnomaly21 and FS L&F.
For RoadObstacle21, however, only the drivable area is considered an inlier, and everything outside the drivable area, including anomalies, are labeled as ignore regions.
Gaps within complex anomalies are also treated as ignore regions.
Each labeled object on an image is given a unique identifier.
Bounding boxes are also generated to facilitate anomaly localization.

Conventional anomaly segmentation metrics tend to favor larger objects.
Average Precision or False Positive Rate (FPR) per-pixel metrics, or sIoU, which groups anomalies together, do not provide the correct evaluation metric.
Our benchmark uses the Average Precision (AP) metric, a standard in instance segmentation that evaluates precision at IoU thresholds from $0.5$ to $0.95$.
Additionally, we provide the AP50 metric to assess performance at a 50% IoU threshold, following the community practice.

Detection Benchmark.
While our current focus is instance segmentation, we have converted instance data and predictions into bounding boxes to evaluate anomaly object detection capabilities.
However, our initial results show that current anomaly detection methods such as VOS [Du et al., 2021] perform suboptimally in this setup.
For more details on the detection benchmark we refer readers to the supplementary material and leave this area for future research.

§ EVALUATED METHODS & DISCUSSION OF RESULTS

We evaluate existing anomaly instance segmentation methods (see Table <ref>).
To ensure correctness, we contacted authors of the original works, and asked them for a submission to the benchmark.
In cases when code was not available, we worked closely with authors to reimplement unavailable methods and submit them to the benchmark.
We kept the test set private and allowed evaluation on the validation set.

The U3HS [Gasperini et al., 2023] method belongs to a class of models that neither require auxiliary data nor external models for instance segmentation.
The core of the method is the ability to learn class-agnostic instance embeddings that generalize beyond the training distribution.
These embeddings in uncertain regions are clustered to get instance predictions.
This allows clustering of anomalous regions occluded by other objects.
While U3HS is capable of localizing anomaly instances without external data, it struggles in generating precise object masks, as measured by the AP metric that evaluates instances with at least $50\%$ IoU with the ground truth.

Mask2Anomaly [Rai et al., 2023] is a model that uses auxilary data, but does not use an external model for instance segmentation.
Common to other methods in the community [Grcić et al., 2022, Tian et al., 2022], the model uses auxiliary data from COCO [Lin et al., 2014] for guiding the anomaly scores that are grouped using connected components to form instance proposals.
To reduce the number of false positives, Mask2Anomaly introduces a post-processing strategy.
It computes the intersection with predicted in-distribution masks and uses class entropy to determine true instance proposals.
The approach benefits from a powerful backbone and is effective in segmenting individual anomalous objects, however, it merges closely located anomalies (see Figure <ref>).

UGainS [Nekrasov et al., 2023] is a method that uses both auxiliary data and an external generalist segmentation model, namely the segment anything model (SAM) [Kirillov et al., 2023].
The method uses the anomaly segmentation method RbA [Nayal et al., 2023] based on Mask2Former [Cheng et al., 2022], fine-tuned using data from COCO, to generate uncertainty regions.
UGainS uses farthest point sampling to sample a number of points from these regions as prompts for SAM [Kirillov et al., 2023].
While the method produces accurate segmentation masks, it relies on two models to get predictions.
A limited number of prompts leads to missed detections in smaller regions and increases the number of false positives in other areas.
However, it demonstrates strong performance and produces well-separated instance masks.

§ CONCLUSION

Detecting and accurately segmenting anomaly instances on roads is a significant challenge, requiring an understanding of 'objectness' without direct training on specific anomaly classes.
In this work, we introduced a new benchmark for anomaly instance segmentation that integrates three popular anomaly datasets.
The unified benchmark provides a diverse set of anomalies that vary in size, number of images, and annotation detail.
We evaluate the performance of current methods for segmenting anomaly instances and provide intuition behind the results.
Our results show that current techniques struggle particularly with distant and small objects, and with precise segmentation masks.
The benchmark results suggest strong opportunities for advancement in the area.
As autonomous vehicle technologies continue to evolve, driven by large amounts of data, it remains a challenge to capture all possible real-world situations.
Our work addresses the need to evaluate instance segmentation as a step towards reliable autonomous driving.

§ ACKNOWLEDGMENT

We acknowledge fruitful discussions with H. Blum, R. Chan, S. Gasperini and S. Rai, as well as a contribution of annotations for Fishyscapes by H. Blum, and help with the benchmark submission from S. Gasperini and S. Rai.
M.R. an M.A. acknowledge support by the German Federal Ministry of Education and Research within the junior research group project “UnrEAL” (grant no. 01IS22069).
Alexey Nekrasov's research has been funded by BMBF project "WestAI" (grant no. 01IS22094D).
We thank M. Burdorf, G. Lydakis, C. Schmidt, and others in the lab for discussions and feedback.

[Behley et al., 2019]
J. Behley, M. Garbade, A. Milioto, J. Quenzel, S. Behnke, C. Stachniss, and J. Gall.
SemanticKITTI: A Dataset for Semantic Scene Understanding of LiDAR Sequences.
In International Conference on Computer Vision (ICCV), 2019.

[Bergmann et al., 2019]
Paul Bergmann, Michael Fauser, David Sattlegger, and Carsten Steger.
MVTec AD — A Comprehensive Real-World Dataset for Unsupervised Anomaly Detection.
In Conference on Computer Vision and Pattern Recognition (CVPR), 2019.

[Bergmann et al., 2022]
Paul Bergmann, Xin Jin, David Sattlegger, and Carsten Steger.
The MVTec 3D-AD Dataset for Unsupervised 3D Anomaly Detection and Localization.
In Proceedings of the International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications, 2022.

[Blum et al., 2021]
Hermann Blum, Paul-Edouard Sarlin, Juan Nieto, Roland Siegwart, and Cesar Cadena.
The Fishyscapes Benchmark: Measuring Blind Spots in Semantic Segmentation.
International Journal on Computer Vision (IJCV), 1290 (11):0 3119–3135, 2021.

[Chan et al., 2021]
Robin Chan, Krzysztof Lis, Svenja Uhlemeyer, Hermann Blum, Sina Honari, Roland Siegwart, Pascal Fua, Mathieu Salzmann, and Matthias Rottmann.
SegmentMeIfYouCan: A Benchmark for Anomaly Segmentation.
In Neural Information Processing Systems (NeurIPS), 2021a.

[Chan et al., 2021]
Robin Chan, Matthias Rottmann, and Hanno Gottschalk.
Entropy maximization and meta classification for out-of-distribution detection in semantic segmentation.
In International Conference on Computer Vision (ICCV), 2021b.

[Chen et al., 2018]
Liang-Chieh Chen, Yukun Zhu, George Papandreou, Florian Schroff, and Hartwig Adam.
Encoder-Decoder with Atrous Separable Convolution for Semantic Image Segmentation.
In European Conference on Computer Vision (ECCV), 2018.

[Cheng et al., 2022]
Bowen Cheng, Ishan Misra, Alexander G. Schwing, Alexander Kirillov, and Rohit Girdhar.
Masked-attention Mask Transformer for Universal Image Segmentation.
In Conference on Computer Vision and Pattern Recognition (CVPR), 2022.

[Cordts et al., 2016]
Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schiele.
The cityscapes dataset for semantic urban scene understanding.
In Conference on Computer Vision and Pattern Recognition (CVPR), 2016.

[Di Biase et al., 2021]
Giancarlo Di Biase, Hermann Blum, Roland Siegwart, and Cesar Cadena.
Pixel-wise Anomaly Detection in Complex Driving Scenes.
In Conference on Computer Vision and Pattern Recognition (CVPR), 2021.

[Du et al., 2021]
Xuefeng Du, Zhaoning Wang, Mu Cai, and Yixuan Li.
Vos: Learning what you don't know by virtual outlier synthesis.
In International Conference on Learning Representations (ICLR), 2021.

[Gasperini et al., 2023]
Stefano Gasperini, Alvaro Marcos-Ramiro, Michael Schmidt, Nassir Navab, Benjamin Busam, and Federico Tombari.
Holistic Segmentation.
In International Conference on Computer Vision (ICCV), 2023.

[Grcić et al., 2022]
Matej Grcić, Petra Bevandić, and Siniša Šegvić.
Densehybrid: Hybrid anomaly detection for dense open-set recognition.
In European Conference on Computer Vision (ECCV), 2022.

[Grcić et al., 2023]
Matej Grcić, Josip Šarić, and Siniša Šegvić.
On Advantages of Mask-level Recognition for Outlier-aware Segmentation.
In 2023 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), 2023.

[Guo et al., 2017]
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger.
On calibration of modern neural networks.
In International Conference on Machine Learning (ICML), 2017.

[Hariharan et al., 2014]
Bharath Hariharan, Pablo Arbeláez, Ross Girshick, and Jitendra Malik.
Simultaneous Detection and Segmentation.
In European Conference on Computer Vision (ECCV), 2014.

[Hein et al., 2019]
Matthias Hein, Maksym Andriushchenko, and Julian Bitterwolf.
Why relu networks yield high-confidence predictions far away from the training data and how to mitigate the problem.
In Conference on Computer Vision and Pattern Recognition (CVPR), 2019.

[Hendrycks and Gimpel, 2018]
Dan Hendrycks and Kevin Gimpel.
A Baseline for Detecting Misclassified and Out-of-Distribution Examples in Neural Networks.
In International Conference on Learning Representations (ICLR), 2018.

[Hendrycks et al., 2022]
Dan Hendrycks, Steven Basart, Mantas Mazeika, Andy Zou, Joe Kwon, Mohammadreza Mostajabi, Jacob Steinhardt, and Dawn Song.
Scaling Out-of-Distribution Detection for Real-World Settings.
In International Conference on Machine Learning (ICML), 2022.

[Hwang et al., 2021]
Jaedong Hwang, Seoung Wug Oh, Joon-Young Lee, and Bohyung Han.
Exemplar-Based Open-Set Panoptic Segmentation Network.
In Conference on Computer Vision and Pattern Recognition (CVPR), 2021.

[Kendall and Gal, 2017]
Alex Kendall and Yarin Gal.
What Uncertainties Do We Need in Bayesian Deep Learning for Computer Vision?
In Neural Information Processing Systems (NeurIPS), 2017.

[Kirillov et al., 2023]
Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander C. Berg, Wan-Yen Lo, Piotr Dollár, and Ross Girshick.
Segment Anything.
In International Conference on Computer Vision (ICCV), 2023.

[Lakshminarayanan et al., 2017]
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell.
Simple and Scalable Predictive Uncertainty Estimation using Deep Ensembles.
In Neural Information Processing Systems (NeurIPS), 2017.

[Li et al., 2022]
Kaican Li, Kai Chen, Haoyu Wang, Lanqing Hong, Chaoqiang Ye, Jianhua Han, Yukuai Chen, Wei Zhang, Chunjing Xu, Dit-Yan Yeung, Xiaodan Liang, Zhenguo Li, and Hang Xu.
CODA: A Real-World Road Corner Case Dataset for Object Detection in Autonomous Driving.
In European Conference on Computer Vision (ECCV), 2022.

[Liang et al., 2022]
Chen Liang, Wenguan Wang, Jiaxu Miao, and Yi Yang.
GMMSeg: Gaussian Mixture based Generative Semantic Segmentation Models.
In Neural Information Processing Systems (NeurIPS), 2022.

[Lin et al., 2014]
Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.
Microsoft COCO: Common objects in context.
In European Conference on Computer Vision (ECCV), 2014.

[Maag et al., 2022]
Kira Maag, Robin Chan, Svenja Uhlemeyer, Kamil Kowol, and Hanno Gottschalk.
Two Video Data Sets for Tracking and Retrieval of Out of Distribution Objects.
In Asian Conference on Computer Vision (ACCV), 2022.

[Nayal et al., 2023]
Nazir Nayal, Mısra Yavuz, João F. Henriques, and Fatma Güney.
RbA: Segmenting Unknown Regions Rejected by All.
In International Conference on Computer Vision (ICCV), 2023.

[Nekrasov et al., 2023]
Alexey Nekrasov, Alexander Hermans, Lars Kuhnert, and Bastian Leibe.
UGainS: Uncertainty Guided Anomaly Instance Segmentation.
In German Conference on Pattern Recognition (GCPR), 2023.

[Park et al., 2020]
Hyunjong Park, Jongyoun Noh, and Bumsub Ham.
Learning Memory-Guided Normality for Anomaly Detection.
In Conference on Computer Vision and Pattern Recognition (CVPR), 2020.

[Pinggera et al., 2016]
Peter Pinggera, Sebastian Ramos, Stefan Gehrig, Uwe Franke, Carsten Rother, and Rudolf Mester.
Lost and Found: Detecting Small Road Hazards for Self-Driving Vehicles.
In International Conference on Intelligent Robots and Systems (IROS), 2016.

[Rai et al., 2023]
Shyam Nandan Rai, Fabio Cermelli, Dario Fontanel, Carlo Masone, and Barbara Caputo.
Unmasking Anomalies in Road-Scene Segmentation.
In International Conference on Computer Vision (ICCV), 2023.

[Singh et al., 2020]
Aasheesh Singh, Aditya Kamireddypalli, Vineet Gandhi, and K. Madhava Krishna.
LiDAR guided Small obstacle Segmentation.
In International Conference on Intelligent Robots and Systems (IROS), 2020.

[Srivastava et al., 2014]
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov.
Dropout: a simple way to prevent neural networks from overfitting.
In Neural Information Processing Systems (NeurIPS), 2014.

[Tian et al., 2022]
Yu Tian, Yuyuan Liu, Guansong Pang, Fengbei Liu, Yuanhong Chen, and Gustavo Carneiro.
Pixel-wise Energy-biased Abstention Learning for Anomaly Segmentation on Complex Urban Driving Scenes.
In European Conference on Computer Vision (ECCV), 2022.

[Wong et al., 2019]
Kelvin Wong, Shenlong Wang, Mengye Ren, Ming Liang, and Raquel Urtasun.
Identifying Unknown Instances for Autonomous Driving.
In Conference on Robot Learning (CoRL), 2019.

[Yang et al., 2022]
Jingkang Yang, Pengyun Wang, Dejian Zou, Zitang Zhou, Kunyuan Ding, Wenxuan Peng, Haoqi Wang, Guangyao Chen, Bo Li, Yiyou Sun, Xuefeng Du, Kaiyang Zhou, Wayne Zhang, Dan Hendrycks, Yixuan Li, and Ziwei Liu.
OpenOOD: Benchmarking Generalized Out-of-Distribution Detection.
In Neural Information Processing Systems (NeurIPS), 2022.

[Yu et al., 2020]
Fisher Yu, Haofeng Chen, Xin Wang, Wenqi Xian, Yingying Chen, Fangchen Liu, Vashisht Madhavan, and Trevor Darrell.
Bdd100k: A diverse driving dataset for heterogeneous multitask learning.
In Conference on Computer Vision and Pattern Recognition (CVPR), 2020.

[Zhang et al., 2023]
Jingyang Zhang, Jingkang Yang, Pengyun Wang, Haoqi Wang, Yueqian Lin, Haoran Zhang, Yiyou Sun, Xuefeng Du, Kaiyang Zhou, Wayne Zhang, Yixuan Li, Ziwei Liu, Yiran Chen, and Hai Li.
OpenOOD v1.5: Enhanced Benchmark for Out-of-Distribution Detection.
arXiv preprint arXiv:2306.09301, 2023.

Detection benchmark.
We have converted instance labels into bounding boxes for the anomaly detection benchmark.
For evaluation, we considered three methods, namely UGainS [Nekrasov et al., 2023], Mask2Anomaly [Rai et al., 2023], and VOS [Du et al., 2021]. The COCO [Lin et al., 2014] Average Precision (AP) and Average Recall (AR) metrics serve as evaluation metrics.
Unfortunately, we observed an unexpectedly poor performance of VOS.
While performing well on ambiguous objects, the toy car is correctly predicted as an anomaly, vos struggles to predict for an unknown object (see Figure <ref>).
Note that, we have not contacted the authors of VOS for help with the submission and cannot fully trust our results.
We plan to open the detection benchmark for submission along with the instance benchmark, such that we can evaluate anomaly detection methods with the help of the community.

Qualitative Results.
We provide additional qualitative results in Figure <ref>.

Competition and Benchmark Website.
We follow a setup common [Behley et al., 2019] for hosting the benchmark.
We host competition webpage (see Figure <ref>) on <https://codalab.lisn.upsaclay.fr/> servers, and a benchmark webpage on our local server, with manually updated leaderboard for methods with at least an arXiv paper (see Figure <ref>).

VOS prediction on the Lost and Found dataset.

Qualitative results on FS L&F, RoadAnomaly21 and RoadObstacle21 dataset.

Competition website overview.

Leaderboard on the website.