# Stable Coorbit Embeddings of Orbifold Quotients

Dustin G. Mixon111Department of Mathematics, The Ohio State University,
Columbus, OH 222Translational Data Analytics Institute, The Ohio State
University, Columbus, OH Yousef Qaddura11footnotemark: 1

###### Abstract

Given a real inner product space $V$ and a group $G$ of linear isometries, we
construct a family of $G$-invariant real-valued functions on $V$ that we call
coorbit filter banks, which unify previous notions of max filter banks and
finite coorbit filter banks. When $V=\mathbb{R}^{d}$ and $G$ is compact, we
establish that a suitable coorbit filter bank is injective and locally lower
Lipschitz in the quotient metric at orbits of maximal dimension. Furthermore,
when the orbit space $\mathbb{S}^{d-1}/G$ is a Riemannian orbifold, we show
that a suitable coorbit filter bank is bi-Lipschitz in the quotient metric.

##  1 Introduction

Many machine learning algorithms are tailored for Euclidean data, typically
represenented as vectors in a real inner product space $V$. However, this
representation often has an ambiguity that stems from a subgroup $G$ of the
orthogonal group $\operatorname{O}(V)$. For example, a point cloud of $n$
points in $\mathbb{R}^{d}$ may be represented by a matrix in
$V:=\mathbb{R}^{d\times n}$, in which case an ambiguity arises from
permutating the columns.

Neglecting such ambiguities can magnify the sample complexity of the machine
learning process. To address this, one strategy involves augmenting the
training set with the entire $G$-orbit of each datapoint [30, 12, 23, 11].
However, when $G$ is large, this approach makes the machine learning process
much more computationally expensive than necessary.

Alternatively, one may address the ambiguity by representing objects as
elements $[x]:=G\cdot x$ in the orbit space $V/G$ equipped with the quotient
metric

$d([x],[y]):=\inf_{\begin{subarray}{c}p\in[x]\\\
q\in[y]\end{subarray}}\|p-q\|.$

(Indeed, this metric is nondegenerate provided the $G$-orbits are
topologically closed). In order to access Euclidean-based machine learning
algorithms, we are inclined to embed the orbit space into Euclidean space
while minimizing distortion to the quotient metric. In other words, we aim for
embeddings which admit bi-Lipschitz bounds.

Recently, [10] introduced a family of embeddings called max filter banks that
enjoy bi-Lipschitz bounds when $G$ is finite. Later work improved on those
bounds [29, 28]. A theoretical question posed in [10] is whether every
injective max filter bank is bi-Lipschitz. When $G$ is finite, this question
was settled by [5], which introduced a more general family of embeddings
called coorbit filter banks. There, it is shown that every injective coorbit
filter bank admits bi-Lipschitz bounds. The question remains open for infinite
$G$ with only three exceptions, each in the context of max filter banks:

  * •

Complex phase retrieval [8, 3], in which $V=\mathbb{C}^{d}$ and
$G=\\{z\cdot\operatorname{id}:z\in\mathbb{C},|z|=1\\}$.

  * •

Quaternionic phase retrieval, in which $V=\mathbb{H}^{d}$ and
$G=\\{z\cdot\operatorname{id}:z\in\mathbb{H},|z|=1\\}$. This follows from the
argument in [3]; see case (d) in Theorem 71.

  * •

Polar actions [29], in which $V/G$ is isometrically isomorphic to
$V^{\prime}/G^{\prime}$ for some finite
$G^{\prime}\leq\operatorname{O}(V^{\prime})$; see Propositions 97 and 10.

In this paper, we give a construction of coorbit filter banks for all compact
groups $G\leq\operatorname{O}(d)$. These maps unify the family of max filter
banks (introduced in [10] for all compact groups) with the family of coorbit
filter banks (introduced in [5, 6] only for finite groups).

It remains open whether every injective coorbit filter bank is bi-Lipschitz.
While we do not provide a complete answer to this question, we study whether
these maps are bi-Lipschitz given enough generic templates. We prove that this
behavior holds for compact groups $G$ whose spherical orbit space
$\mathbb{S}^{d-1}/G$ is a Riemannian orbifold. It remains open whether this
behavior holds for every compact group. Nonetheless, for general compact
groups, we are able to show the existence of positive local lower Lipschitz
bounds at an open and dense subset of points for sufficiently many generic
templates. In fact, we generalize the notions of injectivity, local lower
Lipschitzness and bi-Lipschitzness into the notions of weak, local and strong
subspace avoidance, respectively. The aim of this paper is to identify
conditions under which coorbit filter banks enjoy these properties.

In Section 2, we construct coorbit filter banks and prove that they are
invariant, symmetric and semialgebraic. There, we also introduce notions of
avoidance and state the problem of interest in technical terms. In Section 3,
we recall the notions of principality and cohomogeneity, and we analyze the
geometry of coorbit maps through a natural Voronoi cell decomposition of
space. This sets up the technical language of the paper. In Section 4, we
estimate the upper Lipschitz bound for coorbit filter banks. In Section 5, we
prove that $2c$ generic templates suffice for a coorbit filter bank to be
injective (more generally, weakly avoidant), where $c\leq d$ is the
cohomogeneity of $G\leq\operatorname{O}(d)$. In Section 6, we show that $2c-1$
generic templates suffice for a coorbit filter bank to be locally lower
Lipschitz (more generally, locally avoidant) at principal points, that is, the
open and dense subset of points in $\mathbb{R}^{d}$ whose stabilizers are
minimal. In Section 7, we reduce the problem of strong avoidance to the groups
for which the origin is the only point that is fixed by all of $G$. In Section
8, we classify groups with finite-index stabilizers (e.g., finite groups and
free groups), and show that for those groups, $2c$ generic templates suffice
for coorbit filter banks to be bi-Lipchitz (more generally, strongly
avoidant). In Section 9, we reduce the assertion that a coorbit filter bank of
$G$ is strongly avoidant to the assertion that a max filter bank of $G_{0}$
(the identity component of $G$) is strongly avoidant. In other words, we
reduce the problem to connected groups. In Section 10, we reduce max filtering
to the case where principal stabilizers are trivial. In Section 11, we show
that with enough templates, max filter banks are locally lower Lipschitz at
orbits of maximal dimension, namely regular orbits. In Section 12, we show
that with enough templates, max filter banks embed (spherical) orbifold
quotients into Euclidean space in a bi-Lipschitz manner. We conclude in
Section 13 with a discussion.

##  2 Construction and Basic Properties of Coorbit Maps

###  2.1 Construction and Invariance Properties

######  Definition 1.

Consider any real inner product space $V$ and $G\leq\operatorname{O}(V)$. Let
$\pi_{0}(G)$ denote the group of connected components of $G$.

  * (a)

The component coorbit map over $V$ given by $\overline{\mathcal{C}}\colon
V\times V\times\pi_{0}(G)\to\mathbb{R}$ is defined by

$\overline{\mathcal{C}}(x,y,K):=\sup_{\begin{subarray}{c}p\in K\cdot
x\end{subarray}}\langle p,y\rangle.$

  * (b)

The sorting map given by
$\downarrow\colon\operatorname{Hom}(\pi_{0}(G),\mathbb{R})\to\mathbb{R}^{|\pi_{0}(G)|}$
is defined on $f\in\operatorname{Hom}(\pi_{0}(G),\mathbb{R})$ by sorting the
entries of the sequence $(f(K))_{K\in\pi_{0}(G)}$ in descending order i.e.
largest goes first.

  * (c)

For $i\in\\{1,\dots,|\pi_{0}(G)|\\}$, the coorbit map over $V$ given by
$\overline{\Psi}_{i}\colon V\times V\to\mathbb{R}$ is defined by

$\overline{\Psi}_{i}(x,y):=\,i^{\text{th}}\text{ entry of
}\downarrow\\{K\in\pi_{0}(G)\mapsto\overline{\mathcal{C}}(x,y,K)\in\mathbb{R}\\}.$

######  Remark 2.

By taking all sort indices to be $p_{i}\equiv 1$, a coorbit filter bank
becomes a max filter bank (Definition 28).

The following lemma shows how the component coorbit map interacts with the
group action and that coorbit maps are invariant to said action hence why they
descend to orbit spaces.

######  Lemma 3.

Suppose $G\leq\operatorname{O}(d)$. Then,

  1. (a)

For any $g,h\in G$, $x,y\in\mathbb{R}^{d}$ and $K\in\pi_{0}(G)$, we have

$\overline{\mathcal{C}}(gx,hy,K)=\overline{\mathcal{C}}(x,y,h^{-1}Kg).$

  2. (b)

Let $S_{\pi_{0}(G)}:=\operatorname{Aut}(\pi_{0}(G))$ denote the group of
bijections from $\pi_{0}(G)$ to itself, and consider the canonical left-action
of $S_{\pi_{0}(G)}$ on $\operatorname{Hom}(\pi_{0}(G),\mathbb{R})$ given by
$s\cdot f=f\circ s^{-1}$ for $s\in S_{\pi_{0}(G)}$ and
$f\in\operatorname{Hom}(\pi_{0}(G),\mathbb{R})$. Then,

$\downarrow(s\cdot f)=\downarrow f$

  3. (c)

For $i\in\\{1,\dots,|\pi_{0}(G)|\\}$, it holds that

$\overline{\Psi}_{i}(x,y)=\overline{\Psi}_{i}(gx,hy)$

for all $x,y\in\mathbb{R}^{d}$ and $g,h\in G$.

###### Proof.

Fix $x,y\in\mathbb{R}^{d}$ and $g,h\in G$. For (a), observe that

$\overline{\mathcal{C}}(gx,hy,K)=\sup_{p\in K\cdot gx}\langle
p,hy\rangle=\sup_{p\in K\cdot gx}\langle h^{-1}p,y\rangle=\sup_{p\in
h^{-1}Kg\cdot x}\langle p,y\rangle=\overline{\mathcal{C}}(x,y,h^{-1}Kg),$

as desired. Next, (b) follows from invariance of sorting to permutation. For
(c), we use (a) to obtain

$\overline{\Psi}_{i}(gx,hy)=\downarrow\\{K\in\pi_{0}(G)\mapsto\overline{\mathcal{C}}(gx,hy,K)\in\mathbb{R}\\}=\,\downarrow\\{K\in\pi_{0}(G)\mapsto\overline{\mathcal{C}}(x,y,h^{-1}Kg)\in\mathbb{R}\\},$

and the result follows from using (b) and observing that $K\mapsto h^{-1}Kg$
is in $S_{\pi_{0}(G)}$. ∎

We arrive to the desired construction:

######  Definition 4.

Suppose $G\leq\operatorname{O}(d)$ and let $V=\mathbb{R}^{d}$. Denote the
identity componenet of $G$ by $G_{0}$ and denote $[x]_{0}:=G_{0}\cdot x$ for
$x\in\mathbb{R}^{d}$.

  * (a)

The component coorbit map given by ${\mathcal{C}}\colon V/G_{0}\times
V/G_{0}\times\pi_{0}(G)\to\mathbb{R}$ is the unique map that satisfies
$\overline{\mathcal{C}}(x,y,K)=\mathcal{C}([x]_{0},[y]_{0},K)$.

  * (a)

For $i\in\\{1,\dots,|\pi_{0}(G)|\\}$, the coorbit map given by $\Psi_{i}\colon
V/G\times V/G\to\mathbb{R}$ is the unique map that satisfies
$\overline{\Psi}_{i}(x,z)=\Psi_{i}([x],[z])$ for all $x,z\in V$.

  * (b)

Given templates $z_{1},\ldots,z_{n}\in V$ and sort indices
$p_{1},\ldots,p_{n}\in\\{1,\dots,|\pi_{0}(G)|\\}$, the corresponding coorbit
filter bank $\Phi\colon V/G\to\mathbb{R}^{n}$ is defined by

$\Phi([x]):=\\{\Psi_{p_{i}}([z_{i}],[x])\\}_{i=1}^{n}.$

###  2.2 Symmetry and Scalar Homogeniety Properties

The following lemma shows how the component coorbit map interacts with
switching inputs in $\mathbb{R}^{d}$ and that the coorbit map is switch-
invariant. Moreover, scalar homogeniety of the maps is shown.

######  Lemma 5.

Suppose $G\leq\operatorname{O}(d)$. Then,

  1. (a)

For any $x,y\in\mathbb{R}^{d}$, $r\geq 0$ and $K\in\pi_{0}(G)$, it holds that

$\overline{\mathcal{C}}(x,y,K)=\overline{\mathcal{C}}(y,x,K^{-1}),$

and

$\overline{\mathcal{C}}(rx,y,K)=\overline{\mathcal{C}}(x,ry,K)=r\cdot\overline{\mathcal{C}}(x,y,K).$

  2. (b)

For $i\in\\{1,\dots,|\pi_{0}(G)|\\}$, it holds that

     * (i)

$\overline{\Psi}_{i}(x,y)=\overline{\Psi}_{i}(y,x)$,

     * (ii)

$\Psi_{i}([x],[y])=\Psi_{i}([y],[x])$,

for all $x,y\in\mathbb{R}^{d}$.

  3. (c)

For $i\in\\{1,\dots,|\pi_{0}(G)|\\}$,
$\Psi_{i}([rx],[y])=\Psi_{i}([x],[ry])=r\cdot\Psi_{i}([x],[y])$.

###### Proof.

For (a), the first assertion follows from the following computation

$\overline{\mathcal{C}}(x,y,K)=\sup_{k\in K}\langle kx,y\rangle=\sup_{k\in
K^{-1}}\langle x,ky\rangle=\sup_{p\in K^{-1}y}\langle
p,x\rangle=\overline{\mathcal{C}}(y,x,K^{-1}),$

and the second assertion follows by a similar argument. The proof of (b) is
similar to the proof of 3(c) wherein here, we note that $K\mapsto K^{-1}$ is
in $S_{\pi_{0}(G)}$. Lastly, (c) is immediate since sorting commutes with
nonnegative scaling. ∎

######  Remark 6.

Occasionaly, we denote $[\cdot]$ and $\Psi_{i}$ by $[\cdot]_{G}$ and
$\Psi_{i}^{G}$ respectively to emphasize the group in consideration.

###  2.3 Preliminary on Semialgebraic Sets and Groups

A basic semialgebraic set is any set of the form
$\\{x\in\mathbb{R}^{n}:p(x)\geq 0\\}$, where
$p\colon\mathbb{R}^{n}\to\mathbb{R}$ is a polynomial function. A semialgebraic
set is any set obtained from some combination of finite unions, finite
intersections, and complements of basic semialgebraic sets. We say a subgroup
of $\operatorname{GL}(d)$ is a semialgebraic group if it is semialgebraic as a
subset of $\mathbb{R}^{d\times d}$. We say a function
$\mathbb{R}^{s}\to\mathbb{R}^{t}$ is a semialgebraic function if its graph is
semialgebraic as a subset of $\mathbb{R}^{s+t}$.

######  Definition 7.

A first-order formula of the language of ordered fields with parameters in R
is a formula written with a finite number of conjunctions, disjunctions,
negations, and universal or existential quantifiers on variables, starting
from atomic formulas which are formulas of the kind $f(x_{1},\dots,x_{n})=0$
or $g(x_{1},\dots,x_{n})>0$, where $f$ and $g$ are polynomials with
coefficients in $\mathbb{R}$. The free variables of a formula are those
variables of the polynomials appearing in the formula, which are not
quantified.

######  Proposition 8 (Proposition 2.2.4 in [7]).

Let $\phi(x_{1},\dots,x_{n})$ be a first-order formula of the language of
ordered fields, with parameters in $\mathbb{R}$ and with free variables
$x_{1},\dots,x_{n}$. Then $\\{x\in\mathbb{R}^{n}:\phi(x)\\}$ is a
semialgebraic set.

By Proposition 2.9.10 in [7], every semialgebraic set is a finite union of
manifolds. As such, the dimension of a semialgebraic set is defined by the
maximum dimension of said manifolds.

The statements in the next proposition are proven in Appendix A of [4].

######  Proposition 9.

The following statements regarding semialgebraic sets and functions hold:

  1. (a)

The family of semialgebraic sets is closed under projection, complement,
finite union and finite intersection.

  2. (b)

The family of semialgebraic functions is closed under addition,
multiplication, division (when defined), composition and concatenation.

  3. (c)

(Conservation of Dimension) If
$\pi\colon\mathbb{R}^{n+d}\mapsto\mathbb{R}^{n}$ is a coordinate projection
and $A$ is a semialgebraic subset of $\mathbb{R}^{n+d}$, then

$\dim(\pi(A))\leq\dim(A)\leq\dim(\pi(A))+\max_{x\in\pi(A)}\dim(\pi^{-1}(x)\cap
A).$ (1)

We remark that conservation of dimension is essential to many arguments in
this paper. The next proposition highlights that semialgebraicity of a group
is equivalent to its compactness.

######  Proposition 10 (Proposition 7 in [29]).

Suppose $G\leq\operatorname{O}(d)$. If the orbits of $G$ are closed, then they
are also the orbits of the topological closure $\overline{G}$ of $G$ in
$\operatorname{O}(d)$. Furthermore, the following are equivalent:

  * (a)

$G$ is topologically closed.

  * (b)

$G$ is algebraic.

  * (c)

$G$ is semialgebraic.

###  2.4 Semialgebraicity of the Coorbit Map

The coorbit map enjoys the propery of being semialgebraic as the following
lemma shows.

######  Lemma 11.

Suppose $G\leq\operatorname{O}(d)$ is a semialgebraic subgroup. Then,

  * (a)

Every component $K\in\pi_{0}(G)$ is compact and semialgebraic as a subset of
$\mathbb{R}^{d\times d}$.

  * (b)

For any fixed $K\in\pi_{0}(G)$, the $K$-component coorbit map
$\overline{\mathcal{C}}(\cdot,\cdot,K)\colon\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}$
is semialgebraic.

  * (c)

For any fixed $i\in\\{1,\dots,|\pi_{0}(G)|\\}$, the coorbit map
$\overline{\Psi}_{i}(\cdot,\cdot)\colon\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}$
is semialgebraic.

###### Proof.

By Proposition 10, $G$ is closed hence a compact Lie group with
$|\pi_{0}(G)|<\infty$. Denote the identity component of $G$ by $G_{0}$. It is
topoligically compact and hence semialgebraic again by Proposition 10. Since
$K=kG_{0}$ for any $k\in K$ and since multiplication in $G$ is semialgebraic
and homeomorphic, we also obtain that $K$ is semialgebraic and compact. This
proves (a). For (b), fix any $K\in\pi_{0}(G)$. Then, the graph of
$\overline{\mathcal{C}}(\cdot,\cdot,K)$ is given by

$\big{\\{}(x,z,r)\in(\mathbb{R}^{d})^{2}\times\mathbb{R}:(\forall k\in
K,r\geq\langle kx,z\rangle)\wedge(\forall\varepsilon\in\mathbb{R},\exists k\in
K,\varepsilon>0\implies r-\varepsilon<\langle kx,z\rangle)\big{\\}}.$

It follows from Proposition 8 that the graph is semialgebraic. For (c), fix
$i\in\\{1,\dots,|\pi_{0}(G)|\\}$. Then, the graph of
$\overline{\Psi}_{i}(\cdot,\cdot)$ is given by

$\displaystyle\bigcup_{K\in\pi_{0}(G)}$
$\displaystyle\big{\\{}(x,z,r)\in\mathbb{(}R^{d})^{2}\times\mathbb{R}:r=\overline{\mathcal{C}}(x,z,K)\
\ \wedge$ $\displaystyle(\exists I\subseteq\pi_{0}(G),|I|=i\wedge(\forall P\in
I,\overline{\mathcal{C}}(x,z,P)\geq r)\wedge(\forall P\in\pi_{0}(G)\setminus
I,\overline{\mathcal{C}}(x,z,P)\leq r))\big{\\}}$

where we note that the second line can be expressed in first-order logic as a
disjunction over all finitely many partitions of $\pi_{0}(G)$ into two sets at
least one of which has size $i$. ∎

By similar arguments, one may show that the quotient distance function is
semialgebraic hence obtaining

######  Proposition 12.

Suppose $G\leq\operatorname{O}(d)$ is compact. The quotient metric
$d([\cdot],[\cdot])\colon\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}$ is a
semialgebraic function.

###  2.5 Avoidance Notions

Fix comapct $G\leq\operatorname{O}(d)$, $z_{1},\ldots,z_{n}\in\mathbb{R}^{d}$
and $p_{1},\dots,p_{n}\in\\{1,\dots,|\pi_{0}(G)|\\}$, and consider the
corresponding coorbit filter bank
$\Phi\colon\mathbb{R}^{d}/G\to\mathbb{R}^{n}$ defined by
$\Phi([x]):=\\{\Psi_{p_{i}}([z_{i}],[x])\\}_{i=1}^{n}$. We say $\Phi$ is bi-
Lipschitz if there exists $\alpha\in(0,\infty]$ and $\beta\in[0,\infty)$ such
that the following inequality holds for all $[x]\neq[y]\in\mathbb{R}^{d}/G$

$\alpha\leq\frac{\|\Phi([x])-\Phi([y])\|}{d([x],[y])}\leq\beta.$

This is equivalent to the statement that the closure of the image of the map
$([x],[y])\mapsto\frac{\Phi([x])-\Phi([y])}{d([x],[y])}$ over $[x]\neq[y]$ is
bounded ($\Phi$ is upper Lipschitz) and avoids the zero vector ($\Phi$ is
lower Lipschitz). When we consider the image itself but not its closure, then
avoidance of the zero vector is equivalent to injectivity of $\Phi$. In Lemma
66, it becomes highly relevant to consider avoidance of not just the zero
vector but also any fixed subspace of the codomain. This motivates the
following definitions:

######  Definition 13.

Fix comapct $G\leq\operatorname{O}(d)$, $z_{1},\ldots,z_{n}\in\mathbb{R}^{d}$
and $p_{1},\dots,p_{n}\in\\{1,\dots,|\pi_{0}(G)|\\}$, and consider the
corresponding coorbit filter bank
$\Phi\colon\mathbb{R}^{d}/G\to\mathbb{R}^{n}$ defined by
$\Phi([x]):=\\{\Psi_{p_{i}}([z_{i}],[x])\\}_{i=1}^{n}$. Suppose
$K\in\operatorname{Gr}(n,k)$, that is, $K$ is a $k$-dimensional linear
subspace of $\mathbb{R}^{n}$.

  * (a)

Let $\Delta:=\\{(x,y)\in\mathbb{R}^{d}\times\mathbb{R}^{d}:[x]=[y]\\}$. The
difference quotient
$Q\colon(\mathbb{R}^{d}\times\mathbb{R}^{d})\setminus\Delta\to\mathbb{R}^{n}$
with respect to $\Phi$ is defined by

$Q(x,y):=\left\\{\frac{\Psi_{p_{i}}([x],[z_{i}])-\Psi_{p_{i}}([y],[z_{i}])}{d([x],[y])}\right\\}_{i=1}^{n}$

  * (b)

We say $\Phi$ weakly avoids $K$ if $\operatorname{im}(Q)\cap K=\varnothing$.

  * (c)

We say $\Phi$ locally avoids $K$ at $x\in\mathbb{R}^{d}$ if for all
$x_{n},y_{n}\to x$ with $[x_{n}]\neq[y_{n}]$, we have

$\lim_{n\to\infty}Q(x_{n},y_{n})\notin K,$

whenever the limit exists.

  * (d)

We say $\Phi$ strongly avoids $K$ if $\overline{\operatorname{im}(Q)}\cap
K=\varnothing$.

  * (e)

We say $\Phi$ is $\varepsilon$-locally lower Lipschitz at $x$ if

$\inf_{\begin{subarray}{c}x_{n},y_{n}\to x\\\
[x_{n}]\neq[y_{n}]\end{subarray}}\
\liminf_{n\to\infty}\|Q(x_{n},y_{n})\|\geq\varepsilon.$

Then, the theoretical problem of interest initially posed as Problem 19 in
[10] is reposed as follows:

######  Problem 14.

  * (a)

Is every injective coorbit filter bank
$\Phi\colon\mathbb{R}^{d}/G\to\mathbb{R}^{n}$ bi-Lipschitz?

  * (b)

More generally, is every coorbit filter bank
$\Phi\colon\mathbb{R}^{d}/G\to\mathbb{R}^{n}$ that weakly avoids
$K\in\operatorname{Gr}(n,k)$ also strongly avoids $K$?

We observe that the notions of avoidance are semialgebraic as summarized in
the following result whose proof is postponed to the end of the section:

######  Lemma 15.

Suppose $G\leq\operatorname{O}(d)$ is compact and fix sort indices
$p_{1},\dots,p_{n}\in\\{1,\dots,|\pi_{0}(G)|\\}$. For templates
$z_{1},\ldots,z_{n}\in\mathbb{R}^{d}$, denote the corresponding coorbit filter
bank by $\Phi\colon\mathbb{R}^{d}/G\to\mathbb{R}^{n}$ and the corresponding
difference quotient by $Q$. Consider the sets

$B:=\big{\\{}\big{(}\\{z_{i}\\}_{i=1}^{n},V\big{)}\in(\mathbb{R}^{d})^{n}\times\mathbb{R}^{n\times
k}:\Phi\text{ fails to weakly avoid }\operatorname{im}(V)\big{\\}}$

and

$D:=\big{\\{}\big{(}\\{z_{i}\\}_{i=1}^{n},V\big{)}\in(\mathbb{R}^{d})^{n}\times\mathbb{R}^{n\times
k}:\Phi\text{ fails to strongly avoid }\operatorname{im}(V)\big{\\}}$

and for any semialgebraic subset $S$ of $\mathbb{R}^{d}$, consider the set

$C_{S}:=\big{\\{}\big{(}\\{z_{i}\\}_{i=1}^{n},V\big{)}\in(\mathbb{R}^{d})^{n}\times\mathbb{R}^{n\times
k}:\Phi\text{ fails to locally avoid }\operatorname{im}(V)\text{ at every
}x\in S\big{\\}}.$

Then, $B$, $C_{S}$ and $D$ are semialgebraic subsets of their respective
ambient spaces.

Ideally and with sort indices arbitrary but fixed, we aim for a bound of the
following form

$\dim(D)\leq nd+nk-1-(n-k-2c)$

where $c\leq d$ is some constant depending on $G$ (more precisely, the
cohomogeniety of $G$ defined in Section 3.1). In other words, $n-k-2c-1$ gives
a lower bound for the codimenion of $D$ in its ambient space. The bound has
two crucial implications. First, the bound implies that it suffices to take
any $n\geq k+2c$ so that $n$ generic templates form a coorbit filter bank that
strongly avoid the image of a generic $V\in\mathbb{R}^{n\times k}$. Second,
the bound on the codimenion is linear in $n$ and $k$. This turns out to be
crucial for an inductive step in the proof of Theorem 69. By meditating on
these two observations, we arrive to the following definitions:

######  Definition 16.

Suppose $G\leq\operatorname{O}(d)$ is compact with identity component $G_{0}$.
For $z_{1},\ldots,z_{m}\in\mathbb{R}^{d}$ and sort indices
$p_{1},\ldots,p_{n}\in\\{1,\ldots,|\pi_{0}(G)|\\}$, denote the corresponding
coorbit filter bank by $\Phi$. For $V\in\mathbb{R}^{n\times k}$, consider the
semialgebraic set

$N_{V}^{\\{p_{i}\\}_{i=1}^{m}}:=\\{\\{z_{i}\\}_{i=1}^{m}\in(\mathbb{R}^{d})^{m}:\Phi\text{
fails to strongly avoid }\operatorname{im}(V)\\}.$

For $k\in\mathbb{Z}_{\geq 0}$ and $m\in\mathbb{N}$, put

$v_{k}^{m}(G):=\min_{W\in\mathbb{R}^{m\times
k}}\min_{\\{p_{i}\\}_{i=1}^{m}\in\\{1,\dots,|\pi_{0}(G)|\\}^{m}}md-\dim(N_{W}^{\\{p_{i}\\}_{i=1}^{m}}),$

and

$n_{k}(G):=\min\\{n\in\mathbb{N}:\min_{m\geq n}v_{k}^{m}(G)>0\\}.$

We define the linear dificiency threshold by

$n^{\prime}(G):=\min\\{n\in\mathbb{N}:v_{k}^{m}(G)>m-k-n\ \ \forall
m\in\mathbb{N},k\geq 0\\},$

where we take $\min\\{\varnothing\\}:=\infty$.

######  Remark 17.

It holds that $k+1\leq n_{k}(G)\leq k+n^{\prime}(G)$.

With the definitions above, we pose the following theoretical problem of
interest:

######  Problem 18.

For a compact $G\leq\operatorname{O}(d)$ with cohomogeneity $c$, does it hold
that $n^{\prime}(G)\leq 2c$?

Recall that the cohomogeneity of $G$ is the minimal codimension taken over
tangent spaces of every orbit (see Section 3.1 for a more precise definition).
The rest of this section aims to prove Lemma 15. First, we unpack basic
properties/characterizations of avoidance notions:

######  Lemma 19.

Fix compact $G\leq\operatorname{O}(d)$, $z_{1},\ldots,z_{n}\in\mathbb{R}^{d}$
and $p_{1},\dots,p_{n}\in\\{1,\dots,|\pi_{0}(G)|\\}$, and consider the
corresponding coorbit filter bank
$\Phi\colon\mathbb{R}^{d}/G\to\mathbb{R}^{n}$ and its corresponding difference
quotient $Q$. Then, the following statements hold

  1. (a)

For any $y_{1},y_{2}\in\mathbb{R}^{d}$ with $[y_{1}]\neq[y_{2}]$ and for any
nonzero $x\in\mathbb{R}^{d}$,

$Q(y_{1},y_{2})=Q\left(\frac{y_{1}}{\|x\|},\frac{y_{2}}{\|x\|}\right).$ (2)

  2. (b)

For any nonzero $x\in\mathbb{R}^{d}$,

$\Phi$ locally avoids $K$ at $x$ $\Longleftrightarrow$ $\Phi$ locally avoids
$K$ at $\frac{x}{\|x\|}$. (3)

  3. (c)

Let $\Omega\subseteq\mathbb{R}^{d}$ be a dense $G$-invariant subset such that
$c\cdot\Omega=\Omega$ for all $c>0$. Then,

$\displaystyle\Phi$ $\displaystyle\text{ strongly avoids
$K$}\iff\overline{\operatorname{im}(Q|_{(\Omega\times\Omega)\cap\Delta})}\cap
K=\varnothing$ (4) $\displaystyle\iff\big{(}\Phi\text{ weakly avoids
$K$}\big{)}\wedge(\forall\,x\in\mathbb{S}^{d-1},\forall x_{n},y_{n}\to x,$
$\displaystyle\qquad\qquad\qquad(\forall
n\in\mathbb{N},[x_{n}]\neq[y_{n}]\wedge
x_{n},y_{n}\in\Omega)\implies\lim_{n\to\infty}Q(x_{n},y_{n})\notin K),$

where we take $\lim_{n\to\infty}Q(x_{n},y_{n})\notin K$ to be true if the
limit does not exist.

###### Proof.

First, (a) follows from scalar homogeniety of distance and coorbit maps
(5(c)). Next, (b) follows from (a). For (c), the first line follows from
continuity of $Q$ and denseness of $\Omega$. The forward implication is
immediate by definition of strong avoidance. For the reverse implication,
suppose $\overline{\operatorname{im}(Q|_{(\Omega\times\Omega)\cap\Delta})}\cap
K\neq\varnothing$. Then, there exists sequences $x_{n},y_{n}\in\Omega$ such
that $[x_{n}]\neq[y_{n}]$ and $\lim_{n\to\infty}Q(x_{n},y_{n})\in K$. Since
$\max\\{\|x_{n}\|,\|y_{n}\|\\}\neq 0$, we may take a subsequence and assume
$\max\\{\|x_{n}\|,\|y_{n}\|\\}=\|x_{n}\|>0$ for all $n$. By (2), We get

$Q(x_{n},y_{n})=Q\left(\frac{x_{n}}{\|x_{n}\|},\frac{y_{n}}{\|x_{n}\|}\right).$

Since $\|x_{n}\|\cdot\Omega=\Omega$, we get that
$u_{n}:=\frac{x_{n}}{\|x_{n}\|}\in\Omega$ and
$v_{n}:=\frac{y_{n}}{\|x_{n}\|}\in\Omega$. By taking further subsequences, we
may assume $u_{n}\to x\in\mathbb{S}^{d-1}$ and $v_{n}\to y$ with $\|y\|\leq
1$. If $[x]\neq[y]$, then by continuity of $Q$ over $\Delta$, we get
$Q([x],[y])\in K$ so that weak avoidance fails. On the other hand, if
$[x]=[y]$, we may translate $u_{n}$ and $v_{n}$ so that
$x=y\in\mathbb{S}^{d-1}$ and $u_{n},v_{n}\in\Omega$ by $G$-invariance of
$\Omega$. In such case, the right hand side of the wedge in (4) fails. ∎

###### Proof of Lemma 15.

Consider a semialgebraic lift of $B$

$\displaystyle L:=\big{\\{}\big{(}\\{z_{i}\\}_{i=1}^{n},V,p,x,y\big{)}$
$\displaystyle\in(\mathbb{R}^{d})^{n}\times\mathbb{R}^{n\times
k}\times\mathbb{R}^{k}\times(\mathbb{R}^{d})^{2}:$
$\displaystyle[x]\neq[y],\|x\|^{2}+\|y\|^{2}=1,x\in\mathbb{R}^{d},y\in\mathbb{R}^{d},$
$\displaystyle\Psi_{p_{i}}([z_{i}],[x])-\Psi_{p_{i}}([z_{i}],[y])=d([x],[y])\cdot(Vp)_{i}\
\forall i\in\\{1,\ldots,n\\}\big{\\}}$

By Lemmas 11, 12 and 8, $L$ is semialgebraic. Since $B$ is the projection of
$L$ onto its $(\\{z_{i}\\}_{i=1}^{n},V)$ coordinate, we obtain that $B$ is
semialgebraic by 9(a).

Next, consider a semialgebraic lift of $C_{S}$

$\displaystyle W_{S}$
$\displaystyle:=\big{\\{}(\\{z_{i}\\}_{i=1}^{n},V,x)\in(\mathbb{R}^{d})^{n}\times\mathbb{R}^{n\times
k}\times S:\exists
p\in\mathbb{R}^{k},\forall\varepsilon\in\mathbb{R}_{>0},\exists
x_{0},y_{0}\in\mathbb{R}^{d},$
$\displaystyle\qquad\qquad[x_{0}]\neq[y_{0}]\wedge|Q(x_{0},y_{0})-Vp|<\varepsilon\wedge[x_{0}],[y_{0}]\in
B_{[x]}(\varepsilon)\big{\\}}$

Again, $W_{S}$ is semialgebraic and since $C_{S}$ is a projection of $W_{S}$,
we obtain that $C_{S}$ is semialgebraic. Lastly, by (4) applied to
$\Omega=\mathbb{R}^{d}$ and $K=\operatorname{im}(V)$, we obtain that $D$ is a
union of $B$ and $C_{\mathbb{R}^{d}}$. ∎

##  3 Geometric Analysis of Coorbit Maps

###  3.1 Preliminary on Stabilizers and Principal Points

In this section, we first recall an orbit-stabilizer type theorem and results
on the poset structure of stabilizers. Following that, we recall that an orbit
space is in fact a geodesic space, and we introduce two layers of
principality.

######  Definition 20.

Let $G\leq O(d)$ be compact with Lie algebra
$\mathfrak{g}\subseteq\mathbb{R}^{n\times n}$. For nonzero
$x\in\mathbb{R}^{d}$, the stabilizer group of $x$ is defined by

$G_{x}:=\\{g\in G:g\cdot x=x\\}$

The tangent space at $x$ is defined by

$T_{x}:=\mathfrak{g}\cdot x$

and the normal space at $x$ is denoted by $N_{x}:=T_{x}^{\perp}$.

We have the following (presumably folklore) result that $T_{x}$ and $N_{x}$
are $G_{x}$-invariant. We were unable to find a reference, so we provide a
proof:

######  Proposition 21.

Suppose $G\leq\operatorname{O}(d)$ is compact and fix $x\in\mathbb{R}^{d}$.
Then, $T_{x}\oplus N_{x}$ is a $G_{x}$-invariant orthogonal decomposition.

###### Proof.

Since $G_{x}\leq\operatorname{O}(d)$, the orthogonal complement of a
$G_{x}$-invariant subspace is $G_{x}$-invariant. As such, we only need to show
$T_{x}$ is $G_{x}$-invariant. Let $h\in G_{x}$ and $t\in T_{x}$. Then, by
definition of $T_{x}$ and continuity of the action of $G$ on $\mathbb{R}^{d}$,
there exists a sequence $g_{n}\to\operatorname{Id}$ in $G$ such that

$\lim_{r\to 0}\left(\frac{g_{n}-\operatorname{Id}}{r}\cdot
x\right)=\left(\lim_{r\to 0}\frac{g_{n}-\operatorname{Id}}{r}\right)\cdot
x=t\in T_{x}$

Now, let $g_{n}^{\prime}:=hg_{n}h^{-1}$ so that $hg_{n}=g_{n}^{\prime}h$ and
$g_{n}^{\prime}\to\operatorname{Id}$. Then, by continuity of the action of $G$
and since $h\in G_{x}$, we obtain

$ht=h\cdot\lim_{r\to 0}\left(\frac{g_{n}-\operatorname{Id}}{r}\cdot
x\right)=\lim_{r\to
0}\left(\frac{g_{n}^{\prime}-\operatorname{Id}}{r}\cdot(hx)\right)\in
T_{hx}=T_{x}$

as desired. ∎

In general, for a compact group $G\leq\operatorname{O}(d)$, we denote its
identity component by $G_{0}$ and denote $[x]_{0}:=G_{0}\cdot x$ for
$x\in\mathbb{R}^{d}$. In many instances, we abuse notation and identify
$[Kx]_{0}$ with $[kx]_{0}$ for any $K\in\pi_{0}(G)$ and any $k\in K$. For
$x\in\mathbb{R}^{d}$, we denote the set of connected components of $[x]$ by

$\pi_{0}([x]):=\\{P:P\text{ is a connected component of }[x]\\}$

The following proposition is an orbit-stabilizer type theorem. The first item
is straighforward. For the second item, see for example the proof of Corollary
3.2.3 in [22].

######  Proposition 22.

Suppose $G\leq\operatorname{O}(d)$ is compact. The following hold:

  * (a)

There exists a unique group structure on $\pi_{0}(G)$ that makes the canonical
projection $\pi_{0}^{G}\colon G\to\pi_{0}(G)$ into a surjective homomorphism.
For $x\in\mathbb{R}^{d}$, the action of $G$ on $[x]$ induces an action of
$\pi_{0}(G)$ on $\pi_{0}([x])$ with stabilizer $\pi_{0}^{G}(G_{x})$.

  * (b)

For $x\in\mathbb{R}^{d}$, $G\cdot x$ is a compact $C^{\infty}$-submanifold of
$\mathbb{R}^{d}$ whose tangent space at $x$ is given by $T_{x}$. Moreover, the
following diagram commutes

${G}$${G/G_{x}}$${G\cdot
x}$${\pi_{0}(G)/\pi_{0}^{G}(G_{x})}$${\pi_{0}([x])}$$\scriptstyle{\cdot}$$\scriptstyle{\cong}$$\scriptstyle{\cong}$

In fact, conjugacy classes of stabilizers form a partially order set. For
$H\leq G$, denote by $(H)$ the conjugacy class of $H$ in $G$. Given
$x\in\mathbb{R}^{d}$ and $g\in G$, we have $G_{gx}=gG_{x}g^{-1}$. Hence,
$(G_{x})$ depends only on $[x]$. Let $G_{\leq}$ be the set of conjugacy
classes of stabilizer subgroups of $G$, that is $(H)\in G_{\leq}$ if and only
if $H=G_{x}$ for some $x\in\mathbb{R}^{d}$. There is a partial order on
$G_{\leq}$ given by $(H_{1})\leq(H_{2})$ if and only if $H_{1}\leq
gH_{2}g^{-1}$ for some $g\in G$. We call $G_{\leq}$ the poset of conjugacy
classes of stabilizers in $G$.

######  Proposition 23 (Theorem 1.32 in [26]).

For compact $G\leq\operatorname{O}(d)$, $G_{\leq}$ is finite and has a unique
minimum $(G_{P})$.

We call $(G_{P})$ the principal isotropy class. For $H\in(G_{P})$, we call $H$
a principal isotropy group. We define the principal component size by
$C_{P}:=|\pi_{0}^{G}(H)|$ for any $H\in(G_{P})$; this does not depend on the
choice of $H$. This allows for defining principal points as those which have
the “most” trivial stabilizers:

######  Definition 24.

For compact $G\leq\operatorname{O}(d)$, the set of principal points is defined
by

$P(G):=\\{x\in\mathbb{R}^{d}:G_{x}\in(G_{P})\\}$

The set of $\pi_{0}$-principal points is defined by

$P_{\pi_{0}}(G):=\\{x\in\mathbb{R}^{d}:|\pi_{0}^{G}(G_{x})|=C_{P}\\}$

Since all principal orbits share the same maximal (submanifold) dimension
among all orbits, we define the cohomogeneity of $G$ as the codimension of
$[x]$ for any $x\in P(G)$. Now, we recall that $\mathbb{R}^{d}/G$ is a
geodesic space:

######  Definition 25.

Given a metric space $(M,d)$ and $L>0$, we say a curve $\gamma\colon[0,L]\to
M$ is a minimal geodesic from $\gamma(0)$ to $\gamma(L)$ if
$d(\gamma(s),\gamma(t))=|s-t|$ for all $s,t\in[0,L]$, and given $x,y\in M$ we
let $C(x,y)$ denote the set of all minimal geodesics from $x$ to $y$. We say
$M$ is a geodesic space if $C(x,y)\neq\varnothing$ for every $x,y\in M$.

######  Proposition 26 (Lemma 23 in [29]).

Take $G\leq\operatorname{O}(d)$ with closed orbits. For each
$x,y\in\mathbb{R}^{d}$, there exists a bijection

$\frac{\arg\min_{q\in[y]}\|q-x\|}{G_{x}}\longrightarrow C([x],[y]).$

induced by projecting straight lines from $x$ to $\arg\min_{q\in[y]}\|q-x\|$
into the orbit space. In particular, $\mathbb{R}^{d}/G$ is a geodesic space.

Furthermore, we have the following proposition regarding principal points:

######  Proposition 27.

Suppose $G\leq\operatorname{O}(d)$ is compact and denote the principal stratum
in $\mathbb{R}^{d}/G$ by $[P(G)]:=\\{[x]\in\mathbb{R}^{d}/G:x\in P(G)\\}$.
Then, each of the following holds:

  * (a)

$P(G)\subseteq P_{\pi_{0}}(G)$ are $G$-invariant open dense semialgebraic
subsets of $\mathbb{R}^{d}$.

  * (b)

$[P(G)]$ is a geodesic space and an open dense connected manifold in
$\mathbb{R}^{d}/G$. It admits a unique Riemannian structure whose geodesic
metric is the quotient metric and such that the map
$[\cdot]\big{|}_{P(G)}\colon P(G)\to[P(G)]$ is a Riemannian submersion.

###### Proof.

For (a), $G$-invariance and the inclusion are straightforward. Openness and
denseness of $P(G)$ follows from Theorem 3.82 in [2]. Then, denseness of
$P_{\pi_{0}}(G)$ follows from $P(G)\subseteq P_{\pi_{0}}(G)$, and openness of
$P_{\pi_{0}}(G)$ follows from $(G_{z})\leq(G_{x})$ for $z$ in a neighborhood
of $x$ (see Theorem 1.30 in [26] or Proposition 109). Lastly, semialgebraicity
follows by expressing the sets in first-order logic which is straightforward.

For (b), openness, denseness and connectedness of $[P(G)]$ follow from Theorem
3.82 in [2]. It being a geodesic space follows from Lemma 3.5 in [1]. The rest
of the statement regarding the unique Riemannian structure follows from
Exercise 3.81 in [2]. ∎

###  3.2 Preliminary on Max Filtering

Coorbit filter banks generalize max filter banks [10, 29] and we shall see
later in Section 9 that with enough templates, the analysis of max filtering
is very informative to the analysis of coorbit filter banks. In this section,
we recall properties of max filtering which we shall find useful throughout
the paper.

######  Definition 28.

Suppose $G\leq\operatorname{O}(d)$.

  * (a)

The max filtering map
$\langle\langle\cdot,\cdot\rangle\rangle\colon\mathbb{R}^{d}/G\times\mathbb{R}^{d}/G\to\mathbb{R}$
is defined by

$\langle\langle[x],[y]\rangle\rangle:=\sup_{\begin{subarray}{c}p\in[x]\end{subarray}}\langle
p,y\rangle.$

  * (b)

Given templates $z_{1},\ldots,z_{n}\in\mathbb{R}^{d}$, the corresponding max
filter bank $\Phi\colon\mathbb{R}^{d}/G\to\mathbb{R}^{n}$ is defined by

$\Phi([x]):=\\{\langle\langle[z_{i}],[x]\rangle\rangle\\}_{i=1}^{n}.$

Occasionally, we denote $\langle\langle[\cdot],[\cdot]\rangle\rangle$ by
$\langle\langle[\cdot],[\cdot]\rangle\rangle_{G}$ to emphasize the group in
consideration.

By direct inspection, the following equation holds and we will make use of it
frequently:

$\mathcal{C}([x]_{0},[y]_{0},K)=\langle\langle[Kx]_{0},[y]_{0}\rangle\rangle_{G_{0}}$
(5)

Recall that every convex function $f\colon\mathbb{R}^{d}\to\mathbb{R}$ has a
subdifferential $\partial f\colon\mathbb{R}^{d}\to 2^{\mathbb{R}^{d}}$ defined
by

$\partial f(x):=\big{\\{}u\in\mathbb{R}^{d}:f(x+h)\geq f(x)+\langle
h,u\rangle\big{\\}}.$

Note that $f$ is differentiable at $x$ if and only if $\partial f(x)$ is
singleton, in which case it agrees with the gradient. The following lemma
summarizes important properties of max filtering:

######  Proposition 29 (Lemma 2 and Theorem 27 in [10]).

Suppose $G\leq\operatorname{O}(d)$ is compact and let $x,y\in\mathbb{R}^{d}$.
Then, each of the following holds:

  1. (a)

$d([x],[y])^{2}=\|x\|^{2}-2\langle\langle[x],[y]\rangle\rangle+\|y\|^{2}$.

  2. (b)

$\langle\langle\cdot,[y]\rangle\rangle\colon\mathbb{R}^{d}/G\to\mathbb{R}$ is
$\|y\|$-Lipschitz.

  3. (c)

$\langle\langle[\cdot],[y]\rangle\rangle\colon\mathbb{R}^{d}\to\mathbb{R}$ is
convex.

  4. (d)

$\partial\langle\langle[\cdot],[y]\rangle\rangle(x)=\operatorname{conv}\\{q\in\mathbb{R}^{d}:q\in[y]\
\operatorname{and}\ \langle x,q\rangle=\langle\langle[x],[y]\rangle\rangle\\}$
where $\operatorname{conv}$ denotes the convex hull operator.

The following proposition forms an essential stepping stone towards proving
that the coorbit map is Lipschitz continuous (Theorem 31). Its proof follows
immediately from 29(b) and (5).

######  Proposition 30.

Suppose $G\leq\operatorname{O}(d)$ and $K\in\pi_{0}(G)$. Then, for
$z\in\mathbb{R}^{d}$,
$\mathcal{C}([z]_{0},\cdot,K)\colon\mathbb{R}^{d}/G\to\mathbb{R}$ is
$\|z\|$-Lipschitz.

###  3.3 Realizing Group Components and Continuity of Coorbit Maps

The goal of this section is to show that the coorbit map is continuous:

######  Theorem 31.

Suppose $G\leq\operatorname{O}(d)$ is compact and fix
$i\in\\{1,\dots,|\pi_{0}(G)|\\}$. Then, the following statements hold:

  * (a)

$\Psi_{i}([z],\cdot)\colon\mathbb{R}^{d}/G\to\mathbb{R}$ is $\|z\|$-Lipschitz
for $z\in\mathbb{R}^{d}$.

  * (b)

$\Psi_{i}(\cdot,\cdot)\colon\mathbb{R}^{d}/G\times\mathbb{R}^{d}/G\to\mathbb{R}$
is locally Lipschitz at every
$([z],[x])\in\mathbb{R}^{d}/G\times\mathbb{R}^{d}/G$ with local Lischitz
constant $2\sqrt{\|z\|^{2}+\|x\|^{2}}$. In particular, $\Psi_{i}$ is
continuous.

In order to do so, we shall analyze the coorbit map from the lens of realizing
group components introduced below. We mimic the approach and notation of
Section 2.2.1 in [5] which only treated the case of finite groups.

######  Definition 32.

Fix a compact group $G\leq\operatorname{O}(d)$. For a sort index
$i\in\\{1,\dots,|\pi_{0}(G)|\\}$ and $x,z\in\mathbb{R}^{d}$, we denote the set
of realizing group components of $z$ with respect to $x$ by

$L^{i}(z,x):=\\{K\in\pi_{0}(G):\mathcal{C}([z]_{0},[x]_{0},K)=\Psi_{i}([z],[x])\\}$

We also define the auxiliary sets

$L^{i}_{>}(z,x):=\\{K\in\pi_{0}(G):\mathcal{C}([z]_{0},[x]_{0},K)>\Psi_{i}([z],[x])\\}$
$L^{i}_{<}(z,x):=\\{K\in\pi_{0}(G):\mathcal{C}([z]_{0},[x]_{0},K)<\Psi_{i}([z],[x])\\}$

For $z,x\neq 0$ in $\mathbb{R}^{d}$, define the separation scale by

$\Delta^{i}(z,x):=\frac{1}{\|z\|}\begin{cases}\min_{K\notin
L^{i}(z,x)}\big{|}\,\mathcal{C}([z]_{0},[x]_{0},K)-\Psi_{i}([z],[x])\,\big{|},&\text{if
}L^{i}(z,x)\neq\pi_{0}(G)\\\ \|x\|,&\text{if
}L^{i}(z,x)=\pi_{0}(G)\end{cases}$ (6)

For $z,x\in\mathbb{R}^{d}$, define $\Delta^{i}(0,x)=\Delta^{i}(z,0)=\infty$.

The usefulness of the separation scale will be highlighted in the statement
and proof Lemma 33. We sometimes denote $L^{i}(z,x)$ by $L^{i}_{G}(z,x)$ to
emphasize the group in consideration. Observe that $\Delta^{i}(z,x)>0$ for all
$x,z\in\mathbb{R}^{d}$. Moreover, by direct inspection or by an argument
similar to Lemma 2.4 in [5], we have that

$|L^{i}_{>}(z,x)|\leq i-1\text{\ \ and \ \
}|L^{i}_{<}(z,x)|\leq|\pi_{0}(G)|-i.$ (7)

Now, we show that small perturbations of $x$ can only shrink $L^{i}(z,x)$. We
mimic the proof of Lemma 2.5 in [5] with a few changes that adapt to our
context.

######  Lemma 33.

Fix a compact group $G\leq\operatorname{O}(d)$ and a sort index
$i\in\\{1,\dots,|\pi_{0}(G)|\\}$. For $x,y,z\in\mathbb{R}^{d}$ such that
$\|y\|<\frac{1}{2}\Delta^{i}(z,x)$, it holds that $L^{i}(z,x+y)\subseteq
L^{i}(z,x)$.

###### Proof.

The result is trivial whenever $L^{i}(z,x)=\pi_{0}(G)$, so assume
$L^{i}(z,x)\neq\pi_{0}(G)$ so that in particular $x,z\neq 0$, and
$\Delta^{i}(z,x)$ is given by the first case of (6).

We claim that if $K\in L^{i}_{<}(z,x)$ and $H\in L^{i}_{>}(z,x)\cup
L^{i}(z,x)$, then
$\mathcal{C}([z]_{0},[x+y]_{0},H)>\mathcal{C}([z]_{0},[x+y]_{0},K)$. By
symmetry in the proof, the claim remains true when all inequalities are
flipped. To the end of proving the claim, assume $H\in L^{i}_{>}(z,x)\cup
L^{i}(z,x)$ and $K\in L^{i}_{<}(z,x)$. By Proposition 30, we have

$|\mathcal{C}([z]_{0},[x+y]_{0},H)-\mathcal{C}([z]_{0},[x]_{0},H)|\leq\|z\|\cdot
d([x+y],[x])\leq\|z\|\cdot\|y\|,$

and similarly for $K$. Hence, by assumption and by
$\|y\|<\frac{1}{2}\Delta^{i}(z,x)$, we get

$\displaystyle\mathcal{C}([z]_{0},[x+y]_{0},H)-\mathcal{C}([z]_{0},[x+y]_{0},K)$
$\displaystyle\geq\mathcal{C}([z]_{0},[x]_{0},H)-\mathcal{C}([z]_{0},[x]_{0},K)-2\|y\|\cdot\|z\|$
$\displaystyle\geq\Psi_{i}([z],[x])-\mathcal{C}([z]_{0},[x]_{0},K)-2\|y\|\cdot\|z\|$
$\displaystyle=|\Psi_{i}([z],[x])-\mathcal{C}([z]_{0},[x]_{0},K)|-2\|y\|\cdot\|z\|>0$

which proves the claim.

Now, suppose there exists $K\in L^{i}(z,x+y)$ such that $K\notin L^{i}(z,x)$.
Assume $K\in L^{i}_{<}(z,x)$ without loss generality. By the claim and since
$K\in L^{i}(z,x+y)$, we get that
$\mathcal{C}([z]_{0},[x+y]_{0},H)>\mathcal{C}([z]_{0},[x+y]_{0},K)=\Psi_{i}([z],[x+y])$,
that is, $H\in L^{i}_{>}(z,x+y)$. We obtain the contradiction

$|L^{i}_{>}(z,x)\cup L^{i}(z,x)|\leq|L^{i}_{>}(z,x+y)|$

since immediately from the definition of $\Psi_{i}$, we have
$|L^{i}_{>}(z,x)\cup L^{i}(z,x)|\geq i$ while $|L^{i}_{>}(z,x+y)|<i$. ∎

We are now able to show continuity of the coorbit map.

###### Proof of Theorem 31.

For (a), let $x\in\mathbb{R}^{d}$. Then, $\Delta^{i}(z,x)>0$ and for
$y\in\mathbb{R}^{d}$ such that $\|y\|<\frac{1}{2}\Delta^{i}(z,x)$, Lemma 33
allows us to pick $K\in L^{i}(z,x)\cap L^{i}(z,x+y)$ for some
$K\in\pi_{0}(G)$. Hence, by Proposition 30

$|\Psi_{i}([z],[x+y])-\Psi_{i}([z],[x])|=|\mathcal{C}([z]_{0},[x+y]_{0},K)-\mathcal{C}([z]_{0},[x]_{0},K)|\leq\|z\|d([x+y],[y]).$

As such, $\Psi_{i}([z],\cdot)\colon\mathbb{R}^{d}/G\to\mathbb{R}$ is locally
$\|z\|$-Lipschitz. Since by Proposition 26 $\mathbb{R}^{d}/G$ is a geodesic
space, then by patching the local Lipschitz constant $\|z\|$ along minimal
geodesics, we obtain that
$\Psi_{i}([z],\cdot)\colon\mathbb{R}^{d}/G\to\mathbb{R}$ is globally
$\|z\|$-Lipschitz as desired.

For (b), let $([z],[x])\in\mathbb{R}^{d}/G\times\mathbb{R}^{d}/G$ and for
$[y]\in\mathbb{R}^{d}/G$, denote
$U_{y}:=\\{[y^{\prime}]\in\mathbb{R}^{d}/G:\|y^{\prime}\|<2\|y\|\\}$. Then,
$U_{z}\times U_{x}$ is an open neighborhood of $([z],[x])$ in
$\mathbb{R}^{d}/G\times\mathbb{R}^{d}/G$. For
$([z_{1}],[x_{1}]),([z_{2}],[x_{2}])\in U_{z}\times U_{x}$, we have

$\displaystyle|\Psi_{i}([z_{1}],[x_{1}])-\Psi_{i}([z_{2}],[x_{2}])|$
$\displaystyle\leq|\Psi_{i}([z_{1}],[x_{1}])-\Psi_{i}([z_{1}],[x_{2}])|+|\Psi_{i}([z_{1}],[x_{2}])-\Psi_{i}([z_{2}],[x_{2}])|$
$\displaystyle\leq\|z_{1}\|d([x_{1}],[x_{2}])+\|x_{2}\|d([z_{1}],[z_{2}])$
$\displaystyle<2(\|z\|d([x_{1}],[x_{2}])+\|x\|d([z_{1}],[z_{2}]))$
$\displaystyle\leq
2\sqrt{\|z\|^{2}+\|x\|^{2}}\sqrt{d([x_{1}],[x_{2}])^{2}+d([z_{1}],[z_{2}])^{2}}$
$\displaystyle=2\sqrt{\|z\|^{2}+\|x\|^{2}}\cdot
d_{\mathbb{R}^{d}/G\times\mathbb{R}^{d}/G}\big{(}([z_{1}],[x_{1}]),([z_{2}],[x_{2}])\big{)},$

as desired. ∎

The following lemma shows the influence of stabilzers on the set of realizing
group components. It will find its use in Section 8.

######  Lemma 34.

Fix a compact group $G\leq\operatorname{O}(d)$ and a sort index
$i\in\\{1,\dots,|\pi_{0}(G)|\\}$. The following statements hold for
$x,y,z\in\mathbb{R}^{d}$:

  1. (a)

$\pi_{0}^{G}(G_{x})\cdot L^{i}_{G}(z,x)=L^{i}_{G}(z,x)$.

  2. (b)

Suppose $\|y\|<\frac{1}{2}\Delta^{i}(z,x)$, $L^{i}(z,x)=\pi_{0}^{G}(G_{x})$
and $G_{x}$ is a union of connected components in $G$. Then,
$\Psi_{i}^{G}([z],[x+y])=\Psi_{i^{\prime}}^{G_{x}}([z]_{G_{x}},[x+y]_{G_{x}})$
where

$i^{\prime}=i+1\mod|\pi_{0}^{G}(G_{x})|+1.$

###### Proof.

For (a), if $H\in\pi_{0}^{G}(G_{x})$, then by 3(a)

$\mathcal{C}([z]_{0},[x]_{0},HK)=\mathcal{C}([z]_{0},[H^{-1}x]_{0},K)=\mathcal{C}([z]_{0},[x]_{0},K)$

and the result follows by taking $K\in L^{i}(z,x)$.

For (b), we have $\pi_{0}^{G}(G_{x})=\pi_{0}(G_{x})$ and we let $k$ be the
largest nonnegative integer such that $k|\pi_{0}(G_{x})|<i$, that is
$k=\frac{i-i^{\prime}}{|\pi_{0}^{G}(G_{x})|}$. The assumption
$L^{i}(z,x)=\pi_{0}(G_{x})$ combined with (a) yield that

$L^{k|\pi_{0}(G_{x})|+1}(z,x)=L^{k|\pi_{0}(G_{x})|+2}(z,x)=\dots=L^{k|\pi_{0}(G_{x})|+|\pi_{0}(G_{x})|}(z,x)=\pi_{0}(G_{x}),$

and so

$\bigcup_{1\leq
j\leq|\pi_{0}(G_{x})|}L^{k|\pi_{0}(G_{x})|+j}(z,x)=\pi_{0}(G_{x}).$

By Lemma 33 and since $\|y\|<\frac{1}{2}\Delta^{i}(z,x)$, we obtain

$M:=\bigcup_{1\leq
j\leq|\pi_{0}(G_{x})|}L^{k|\pi_{0}(G_{x})|+j}(z,x+y)\subseteq\pi_{0}(G_{x}).$

and so

$\pi_{0}(G)\setminus M\subseteq L_{>}^{k|\pi_{0}(G_{x})|}(z,x+y)\cup
L_{<}^{k|\pi_{0}(G_{x})|+|\pi_{0}(G_{x})|}(z,x+y).$

By (7), we obtain

$|\pi_{0}(G)|-|M|\leq
k|\pi_{0}(G_{x})|+|\pi_{0}(G)|-k|\pi_{0}(G_{x})|-|\pi_{0}(G_{x})|$

so that $|M|\geq|\pi_{0}(G_{x})|$ and hence $M=\pi_{0}(G_{x})$. As such, when
the sorting map is restricted to
$\operatorname{Hom}(\pi_{0}(G_{x}),\mathbb{R})$, its output is equal to
$\\{\Psi_{k|\pi_{0}(G_{x})|+j}([z],[x+y])\\}_{j=1}^{|\pi_{0}(G_{x})|}$ which
by definition is also equal to
$\\{\Psi^{G_{x}}_{j}([z]_{G_{x}},[x+y]_{G_{x}})\\}_{j=1}^{|\pi_{0}(G_{x})|}$.
Since $i=k|\pi_{0}(G_{x})|+i^{\prime}$ and $1\leq
i^{\prime}\leq|\pi_{0}(G_{x})|$, the result follows. ∎

###  3.4 Voronoi Decompositions

In this section, we set up the technical language of the paper. We use orbits
to decompose space into two families of Voronoi cells, one based purely on the
componenets of the orbit (Definition 36) while the other drills down to the
normal bundle provided by the manifold structure of the orbit (Definition 42).
These decompositions allow us to view coorbit filter banks as “piecewise-
linear” where the pieces are given by fibers of the normal bundle (Definitions
46 and 47). Moreover, we use the decompositions to state equivalent
characterizations of principality (Lemmas 39 and 45). We begin with an
essential preliminary sourced from the theory of nonlinear orthogonal
projection on manifolds. For $x\neq y\in\mathbb{R}^{d}$, we let $(x,y]$ denote
the line segment from $x$ to $y$ which includes $y$ and excludes $x$. Take
$(x,x]:=\\{x\\}$.

######  Proposition 35 (Theorem 3.13a, Theorem 4.1, Remark 3.1 and Corollary
3.9 in [15]).

Suppose $M$ is a smooth submanifold of $\mathbb{R}^{d}$. Fix
$x,z\in\mathbb{R}^{d}$ and suppose that $x\in\arg\max_{p\in M}\langle
p,z\rangle$. Then, each of the following holds:

  1. (a)

$z\in N_{x}$ where $N_{x}$ is the orthogonal complement of the tangent space
of $M$ at $x$.

  2. (b)

There exists an open neighborhood $U$ of $(z,x]$ such that
$\\{x\\}=\arg\max_{p\in M}\langle p,n\rangle$ for $n\in U\cap N_{x}$ and
$|\arg\max_{p\in M}\langle p,t\rangle|=1$ for $t\in U$. Moreover, the map
$v_{x}$ sending $t\in U$ to the unique element in $\arg\max_{p\in M}\langle
p,t\rangle$ is smooth over $U$.

  3. (c)

If there exists an open neighborhood $U_{z}$ around $z$ such that
$|\arg\max_{p\in M}\langle p,t\rangle|=1$ for $t\in U_{z}$, then $z\in U$.

For the purposes of this section, we mainly apply Proposition 35 to orbits
under the action of the identity compoenent $G_{0}$ of a compact group
$G\leq\operatorname{O}(d)$.

######  Definition 36.

Fix a compact group $G\leq\operatorname{O}(d)$ and
$i\in\\{1,\dots,|\pi_{0}(G)|\\}$. Denote by $G_{0}$ be the identity component
of $G$. For $x\in\mathbb{R}^{d}$, we define $V_{[x]_{0}}^{i}$, the open
component Voronoi cell of $x$, through the following characterization

$z\in
V_{[x]_{0}}^{i}\Longleftrightarrow\big{\\{}[x]_{0}\big{\\}}=\big{\\{}[p]_{0}\in\pi_{0}([x]):\Psi_{i}([z],[x])=\mathcal{C}([z]_{0},[p]_{0},G_{0})\big{\\}}.$

In general, for $A\subseteq\pi_{0}([x])$, we define $V_{A}^{i}$ through its
characterization

$z\in V_{A}^{i}\Longleftrightarrow
A=\big{\\{}[p]_{0}\in\pi_{0}([x]):\Psi_{i}([z],[x])=\mathcal{C}([z]_{0},[p]_{0},G_{0})\big{\\}}.$

######  Remark 37.

By (5), $\mathcal{C}([z]_{0},[p]_{0},G_{0})$ may be replaced by
$\langle\langle[z]_{0},[p]_{0}\rangle\rangle_{G_{0}}$ in the definitions
above.

######  Lemma 38.

Fix a compact group $G\leq\operatorname{O}(d)$ with identity component $G_{0}$
and fix $i\in\\{1,\dots,|\pi_{0}(G)|\\}$. Then, the following statements hold
for all $x\in\mathbb{R}^{d}$:

  1. (a)

$V_{[hx]_{0}}^{i}=V_{[x]_{0}}^{i}$ for all $h\in G_{0}$.

  2. (b)

$V_{[gx]_{0}}^{i}=g\cdot V_{[x]_{0}}^{i}$ for all $g\in G$.

  3. (c)

For $[q_{1}]_{0},[q_{2}]_{0}\in\pi_{0}([x])$, if $V_{[q_{1}]_{0}}^{i}\cap
V_{[q_{2}]_{0}}^{i}\neq\varnothing$, then $[q_{1}]_{0}=[q_{2}]_{0}$ and
$V_{[q_{1}]_{0}}^{i}=V_{[q_{2}]_{0}}^{i}$.

  4. (d)

$V^{i}_{[x]_{0}}$ is open.

  5. (e)

The set $\\{(z,x)\in(\mathbb{R}^{d})^{2}:z\in V_{[x]_{0}}^{i}\\}$ is
semialgebraic. Moreover, for $A\subseteq\pi_{0}([x])$, the set $V_{A}^{i}$ is
semialgebraic.

  6. (f)

For every $z\in\mathbb{R}^{d}$, there exists $[q]_{0}\in\pi_{0}([x])$ such
that $z\in\overline{V_{[q]_{0}}^{i}}$.

  7. (g)

If $z\in\overline{V^{i}_{[x]_{0}}}$, then
$\Psi_{i}([z],[x])=\langle\langle[z]_{0},[x]_{0}\rangle\rangle$. The converse
holds when $i=1$.

  8. (h)

$z\in V_{[x]_{0}}^{i}$ if and only if $L^{i}(z,x)=\pi_{0}^{G}(G_{x})$.

###### Proof.

For (a), the proof follows immediately from the definition. For (b), by
normality of $G_{0}$ and 3(a), the following holds for $g\in G$ and
$z,p\in\mathbb{R}^{d}$:

$\mathcal{C}([z]_{0},[p]_{0},G_{0})=\mathcal{C}([z]_{0},[p]_{0},g^{-1}G_{0}g)=\mathcal{C}([gz]_{0},[gp]_{0},G_{0}).$

Hence, for $[p]_{0}\in\pi_{0}([x])$ and $gz\in V^{i}_{[gx]_{0}}$, we have

$\displaystyle\\{[gx]_{0}\\}$
$\displaystyle=\\{[p]_{0}\in\pi_{0}([gx]):\Psi_{i}([gz],[gx])=\mathcal{C}([gz]_{0},[p]_{0},G_{0})\\}$
$\displaystyle=\\{[gp]_{0}\in\pi_{0}([gx]):\Psi_{i}([gz],[gx])=\mathcal{C}([gz]_{0},[gp]_{0},G_{0})\\}$
$\displaystyle=g\cdot\\{[p]_{0}\in\pi_{0}([x]):\Psi_{i}([z],[x])=\mathcal{C}([z]_{0},[p]_{0},G_{0})\\}.$

Multiplying by $g^{-1}$ on the left, we obtain $z\in V^{i}_{[x]_{0}}$ as
desired.

For (c), fix $[q_{1}]_{0},[q_{2}]_{0}\in\pi_{0}([x])$ and suppose $z\in
V_{[q_{1}]_{0}}^{i}\cap V_{[q_{2}]_{0}}^{i}$. Then,

$\\{[q_{1}]_{0}\\}=\\{[q_{2}]_{0}\\}=\\{[p]_{0}\in\pi_{0}([x]):\Psi_{i}([z],[x])=\mathcal{C}([z]_{0},[p]_{0},G_{0})\\},$

and the result immediately follows.

For (d), if $z\in V_{[x]_{0}}^{i}$, then by continuity of $\Psi_{i}$ and
$\mathcal{C}$ (Theorems 31 and 30), there exists a nonempty open neighborhood
$U$ of $z$ such that
$|\Psi_{i}([u],[x])-\mathcal{C}([u]_{0},[p]_{0},G_{0})|>0$ for $u\in U$ and
$[p]_{0}\neq[x]_{0}$ in $\pi_{0}([x])$. Then, $U\subseteq V_{[x]_{0}}^{i}$ as
desired.

For (e), the first half follows from expressing the set of interest in first-
order logic as

$\displaystyle\big{\\{}(z,x)\in$
$\displaystyle(\mathbb{R}^{d})^{2}:\overline{\Psi}_{i}(z,x)=\overline{C}(z,x,G_{0})\
\wedge$ $\displaystyle\forall p\in\mathbb{R}^{d},\big{(}(\exists g\in
G,gp=x)\wedge(\forall h\in G_{0},hp\neq
x)\big{)}\implies\overline{\Psi}_{i}(z,p)\neq\overline{C}(z,p,G_{0})\big{\\}},$

so that the result follows from Proposition 8 and Lemma 11. Next, for
$A\subseteq\pi_{0}([x])$, let $x_{1},\cdots,x_{|A|}\in[x]$ be distinguished
elements from each component in $A$, that is
$A=\sqcup_{i=j}^{|A|}[x_{j}]_{0}$. The result follows from the following
semialgebraic first-order logic expression of $V_{A}^{i}$:

$\displaystyle\big{\\{}z\in$ $\displaystyle\mathbb{R}^{d}:\forall
j\in\\{1,\dots,|A|\\},\overline{\Psi}_{i}(z,x_{j})=\overline{C}(z,x_{j},G_{0})\
\wedge$ $\displaystyle\forall p\in\mathbb{R}^{d},\big{(}(\exists g\in
G,gp=x)\wedge(\forall h\in
G_{0},hp\notin\\{x_{1},\dots,x_{|A|}\\})\big{)}\implies\overline{\Psi}_{i}(z,p)\neq\overline{C}(z,p,G_{0})\big{\\}}.$

For (f), suppose by contradiction that there exists an open neighborhood $U$
such that

$\Big{|}\big{\\{}[p]_{0}\in\pi_{0}([x]):\Psi_{i}([z],[x])=\langle\langle[z]_{0},[p]_{0}\rangle\rangle_{G_{0}}\big{\\}}\Big{|}>1$

for all $z\in U$. Then, there exists $A\subseteq\pi_{0}([x])$ such that
$|A|>1$ and $\dim(V_{A}^{i})=d$. Take $[q_{1}]_{0}\neq[q_{2}]_{0}\in A$. Then,
there exists a nonempty open set $W\subseteq V_{A}^{i}$ such that
$\langle\langle[z]_{0},[q_{1}]_{0}\rangle\rangle_{G_{0}}=\langle\langle[z]_{0},[q_{2}]_{0}\rangle\rangle_{G_{0}}$
for all $z\in W$. This contradicts the strong separation of the max filter
over $G_{0}$ (Theorem 8 in [29] or Lemma 57 applied to $j=1$).

For (g), the first assertion follows from continuity of $\Psi_{i}$ proven in
Theorem 31. For the second assertion, if
$\Psi_{1}([z],[x])=\langle\langle[z]_{0},[x]_{0}\rangle\rangle_{G_{0}}$, then
$\langle\langle[x],[z]\rangle\rangle=\langle g_{0}x,z\rangle$ for some
$g_{0}\in G_{0}$. By 35(b), it follows that for any $q\in(z,g_{0}x]$, we have
$\\{g_{0}x\\}=\arg\max_{p\in[x]}\langle p,q\rangle$. In particular, $q\in
V_{[x]_{0}}^{1}$ and the result follows by taking $q\to z$.

For (h), we have $K\in L^{i}(z,x)$ if and only if
$\Psi_{i}([z],[x])=\mathcal{C}([z]_{0},[x]_{0},K)=\mathcal{C}([z]_{0},[K^{-1}x]_{0},G_{0})$
so $z\in V_{[x]_{0}}^{i}$ if and only if $K^{-1}[x]_{0}=[x]_{0}$ for every
$K\in L^{i}(z,x)$, that is $L^{i}(z,x)\subseteq\pi_{0}^{G}(G_{x})$. By 34(a),
$L^{i}(z,x)\subseteq\pi_{0}^{G}(G_{x})$ holds if and only if
$L^{i}(z,x)=\pi_{0}^{G}(G_{x})$. The result follows. ∎

The next lemma shows how the aforementioned component Voronoi cell structure
allows for a characterization of $\pi_{0}$-principality of points in
$\mathbb{R}^{d}$.

######  Lemma 39.

Fix a compact group $G\leq\operatorname{O}(d)$ with identity component
$G_{0}$, and fix a sort index $i\in\\{1,\dots,|\pi_{0}(G)|\\}$. For
$x\in\mathbb{R}^{d}$, the following are equivalent:

  1. (a)

$x\in P_{\pi_{0}}(G)$

  2. (b)

$z\in V_{[x]_{0}}^{i}$ implies $x\in V_{[z]_{0}}^{i}$.

###### Proof.

Suppose $z\in V_{[x]_{0}}^{i}$. Then,

$[z]_{0}\in
B:=\\{[q]_{0}\in\pi_{0}([z]):\Psi_{i}([z],[x])=\mathcal{C}([q]_{0},[x]_{0},G_{0})\\}.$

We claim that $K\cdot[z]_{0}\in B$ implies $K\in\pi_{0}^{G}(G_{x})$. In
particular, $\pi_{0}^{G}(G_{z})\leq\pi_{0}^{G}(G_{x})$. By Lemma 5, we have
that

$\mathcal{C}([z]_{0},[x]_{0},G_{0})=\mathcal{C}([x]_{0},[z]_{0},G_{0}^{-1})=\mathcal{C}([x]_{0},[z]_{0},G_{0}).$

By 3(a) and since $G_{0}$ is the identity of $\pi_{0}(G)$, it follows that for
$K\in\pi_{0}(G)$, we have

$\displaystyle\mathcal{C}(K\cdot[z]_{0},[x]_{0},G_{0})$
$\displaystyle=\mathcal{C}([z]_{0},[x]_{0},G_{0}K)$
$\displaystyle=\mathcal{C}([z]_{0},[x]_{0},KG_{0})$
$\displaystyle=\mathcal{C}([z]_{0},K^{-1}[x]_{0},G_{0})$
$\displaystyle=\mathcal{C}(K^{-1}[x]_{0},[z]_{0},G_{0}).$

As such, if $K\cdot[z]_{0}\in B$, then by the above computation and since
$z\in V_{[x]_{0}}^{i}$, we get $K^{-1}[x]_{0}=[x]_{0}$ and so
$K\in\pi_{0}^{G}(G_{x})$. This proves the claim.

(a)$\Rightarrow$(b). By minimality of $|\pi_{0}^{G}(G_{x})|$, we obtain
$\pi_{0}^{G}(G_{z})=\pi_{0}^{G}(G_{x})$. It follows that $K\cdot[z]_{0}\in B$
implies $K\in\pi_{0}^{G}(G_{z})$ so that $B=\\{[z]_{0}\\}$ as desired.

(b)$\Rightarrow$(a). By Proposition 27, $P_{\pi_{0}}(G)$ is dense and by Lemma
38, $V_{[x]_{0}}^{i}$ is open. We may then select $y\in V_{[x]_{0}}^{i}\cap
P_{\pi_{0}}(G)$. By assumption, $x\in V_{[y]_{0}}^{i}$ so that by the claim
above, we have $\pi_{0}^{G}(G_{x})\leq\pi_{0}^{G}(G_{y})$. The result follows
by minimality of $|\pi_{0}^{G}(G_{y})|$. ∎

######  Definition 40.

Fix a compact group $G\leq\operatorname{O}(d)$ and
$i\in\\{1,\dots,|\pi_{0}(G)|\\}$. Denote by $G_{0}$ the identity component of
$G$. For $x\in\mathbb{R}^{d}$, we define the open component Voronoi diagram of
$x$ by

$Q_{[x]_{0}}^{i}:=\bigsqcup_{[p]_{0}\in\pi_{0}([x])}V_{[p]_{0}}^{i}$

Note that

$z\in
Q_{[x]_{0}}^{i}\Longleftrightarrow\big{|}\big{\\{}[p]_{0}\in\pi_{0}([x]):\Psi_{i}([z],[x])=\langle\langle[z]_{0},[p]_{0}\rangle\rangle_{G_{0}}\big{\\}}\big{|}=1.$

The following corollary is immediate by Lemmas 38, 39 and 34(a).

######  Corollary 41.

Fix a compact group $G\leq\operatorname{O}(d)$ and
$i\in\\{1,\dots,|\pi_{0}(G)|\\}$. The following statements hold:

  1. (a)

$Q^{i}_{[gx]_{0}}=g\cdot Q^{i}_{[x]_{0}}=Q^{i}_{[x]_{0}}$ for all $g\in G$.

  2. (b)

The set $\\{(z,x)\in(\mathbb{R}^{d})^{2}:z\in Q_{[x]_{0}}^{i}\\}$ is
semialgebraic.

  3. (c)

$Q^{i}_{[x]_{0}}$ is an open dense semialgebraic subset of $\mathbb{R}^{d}$.

  4. (d)

For $z\in P_{\pi_{0}}(G)$, we have $x\in Q_{[z]_{0}}^{i}$ implies $z\in
Q_{[x]_{0}}^{i}$.

  5. (e)

$z\in Q_{[x]_{0}}^{i}$ if and only if $|L^{i}(z,x)|=|\pi_{0}^{G}(G_{x})|$.

######  Definition 42.

Fix a compact group $G\leq\operatorname{O}(d)$ and
$i\in\\{1,\dots,|\pi_{0}(G)|\\}$. For $x\in\mathbb{R}^{d}$, we define
$U_{x}^{i}$, the unique Voronoi cell of $x$, through the following
characterization

$z\in U_{x}^{i}\iff z\in
V_{[x]_{0}}^{i}\wedge\\{x\\}=\arg\max_{p\in[x]_{0}}\langle p,z\rangle$

Furthermore, we define the open Voronoi cell of $x$ by

$V^{i}_{x}:=\operatorname{relint}\big{(}U^{i}_{x}\big{)}$

and we define the open Voronoi diagram of $x$ by

$Q_{x}^{i}:=\bigsqcup_{p\in[x]}V_{p}^{i}$

The following lemma unpacks properties of $U_{x}^{i}$ and $V_{x}^{i}$ and the
third statement justifies the use of disjoint union in the definition of
$Q_{x}^{i}$.

######  Lemma 43.

Fix a compact group $G\leq\operatorname{O}(d)$ with identity component $G_{0}$
and fix $i\in\\{1,\dots,|\pi_{0}(G)|\\}$. Then, the following hold

  1. (a)

$z\in U_{x}^{i}$ if and only if $z\in V_{[x]_{0}}^{i}$ and $G_{x}=\\{g\in
G:\langle\langle[z]_{0},[x]_{0}\rangle\rangle_{G_{0}}=\langle gz,x\rangle\\}$.

  2. (b)

$U_{gx}^{i}=g\cdot U_{x}^{i}$ and $V_{gx}^{i}=g\cdot V_{x}^{i}$ for all $g\in
G$.

  3. (c)

For $q_{1},q_{2}\in[x]$, if $U_{q_{1}}^{i}\cap U_{q_{2}}^{i}\neq\varnothing$,
then $q_{1}=q_{2}$ and $U_{q_{1}}^{i}=U_{q_{2}}^{i}$.

  4. (d)

$U_{x}^{i}\subseteq N_{x}$ and $V_{x}^{i}$ is open in $N_{x}$.

  5. (e)

The following characterization holds

$z\in V_{x}^{i}\Longleftrightarrow z\in V_{[x]_{0}}^{i}\cap
U_{x}^{i}\wedge|\arg\max_{p\in[x]_{0}}\langle p,t\rangle|=1\text{ for $t$ in a
neighborhood of $z$}$

  6. (f)

The sets $\\{(z,x)\in(\mathbb{R}^{d})^{2}:z\in U_{x}^{i}\\}$ and
$\\{(z,x)\in(\mathbb{R}^{d})^{2}:z\in V_{x}^{i}\\}$ are semialgebraic.

###### Proof.

The proofs of (a), (b) and (c) are straightforward.

Next, for (d), the assertion $U_{x}^{i}\subseteq N_{x}$ follows from 35(a).
For the openness assertion, we show that the span of $U_{x}^{i}\subseteq
N_{x}$ is $N_{x}$. We first note that $V_{[x]_{0}}^{i}$ is open by Lemma 38
and that for $z\in U_{x}$, 35(b) entails that there exists a neighborhood $U$
of $(z,x]\cap V_{[x]_{0}}^{i}$ such that $\varnothing\neq U\cap N_{x}\subseteq
U_{x}^{i}$. The result follows since $\operatorname{span}(U\cap N_{x})=N_{x}$.

For the forward implication in (e), suppose $z\in V_{x}^{i}$. Then by
definition, $z\in V_{[x]_{0}}^{i}\cap U_{x}^{i}$ and by openness of
$V_{x}^{i}$ in $N_{x}$, there exists $\varepsilon>0$ such that with
$q:=z+\varepsilon(z-x)\in V_{x}^{i}$, we have
$\\{x\\}=\arg\max_{p\in[x]_{0}}\langle p,q\rangle$. Since $z\in(q,x]$, the
desired implication follows from 35(b). On the other hand, the reverse
implication in (e), follows from 35(c).

Lastly, (f) follows from a straightforward argument with first-order logic. ∎

The following lemma unpacks properties of the Voronoi open diagram
$Q_{x}^{i}$.

######  Lemma 44.

Fix a compact group $G\leq\operatorname{O}(d)$ with identity component $G_{0}$
and fix $i\in\\{1,\dots,|\pi_{0}(G)|\\}$. Then, each of the following holds:

  1. (a)

$Q_{gx}^{i}=Q_{x}^{i}=g\cdot Q_{x}^{i}=G\cdot V_{x}^{i}$ for all $g\in G$.

  2. (b)

The set $\\{(z,x)\in(\mathbb{R}^{d})^{2}:z\in Q_{x}^{i}\\}$ is semialgebraic.

  3. (c)

The following characterization holds

$z\in Q_{x}^{i}\Longleftrightarrow\exists[q]_{0}\in\pi_{0}([x]),z\in
V_{[q]_{0}}^{i}\wedge|\arg\max_{p\in[q]_{0}}\langle p,t\rangle|=1\text{ for
$t$ in a neighborhood of $z$}$

  4. (d)

$Q_{x}^{i}$ is an open dense semialgebraic subset of $\mathbb{R}^{d}$.

###### Proof.

The proofs of (a) and (b) are straightforward.

The proof of (c) follows immediately using 43(e).

Lastly, for (d), openness of $Q_{x}^{i}$ follows immediately from the openness
of the right-hand characterization in (c). As for denseness, let
$z\in\mathbb{R}^{d}$. Then, by Lemma 38, $z\in\overline{V_{[q]_{0}}^{i}}$ for
some $[q]_{0}\in\pi_{0}([x])$. Next, for $t\in V_{[q]_{0}}^{i}$ and
$q^{\prime}\in\arg\max_{p\in[q]_{0}}\langle p,t\rangle$ and by 35(b), there
exists an open neighborhood $U$ of $(t,q^{\prime}]$ such that
$|\arg\max_{p\in[q]_{0}}\langle p,u\rangle|=1$ for $u\in U$. This entails
denseness of the right-hand characterization in (c) and hence $Q_{x}^{i}$. ∎

Lastly, we end with a characterization of principal points which will its use
in Section 6. The proof is deferred to the appendix since it requires a
technical result regarding symmetry in cut points of (non-complete) Riemannian
manifolds (Section A.1).

######  Lemma 45.

Fix a compact group $G\leq\operatorname{O}(d)$ and
$i\in\\{1,\dots,|\pi_{0}(G)|\\}$. The following are equivalent:

  * (a)

$x\in P(G)$.

  * (b)

$z\in V_{x}^{i}$ implies $x\in V_{z}^{i}$.

  * (c)

$z\in Q_{x}^{i}$ implies $x\in Q_{z}^{i}$.

###### Proof.

See Section A.3. ∎

###  3.5 The Coorbit Realizer and its Local Properties

######  Definition 46.

Fix a compact group $G\leq\operatorname{O}(d)$ and
$i\in\\{1,\dots,|\pi_{0}(G)|\\}$. The Voronoi coorbit realizer given by
$v^{i}\colon\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}^{d}$ is defined by

$(z,x)\mapsto v_{z}^{i}(x):=\begin{cases}gz,&x\in V^{i}_{gz}\text{ for some
$g\in G$}\\\ 0,&x\notin Q_{z}^{i}\end{cases}$

Note that $v^{i}_{z}$ is well-defined since $Q_{z}^{i}$ is a disjoint union
$\bigsqcup_{p\in[z]}V_{p}^{i}$. The coorbit realizer map factors the coorbit
map through an inner product as the first statement of the following lemma
shows.

######  Lemma 47.

Fix a compact group $G\leq\operatorname{O}(d)$ and
$i\in\\{1,\dots,|\pi_{0}(G)|\\}$. For $x,z\in\mathbb{R}^{d}$, each of the
following statements holds:

  1. (a)

For $x\in Q_{z}^{i}$, $v_{z}^{i}(x)$ is the unique element in $[z]$ such that
$\Psi_{i}([x],[z])=\langle x,v_{z}^{i}(x)\rangle$.

  2. (b)

$v_{z}^{i}(x)\in N_{x}$ and $x\in V_{v_{z}^{i}(x)}^{i}\subseteq
N_{v_{z}^{i}(x)}$.

  3. (c)

$v_{z}^{i}(gx)=g\cdot v_{z}^{i}(x)=v_{gz}^{i}(x)$ for every $g\in G$.

  4. (d)

$v^{i}$ is semialgebraic over $(z,x)\in\mathbb{R}^{d}\times\mathbb{R}^{d}$.

  5. (e)

$v_{z}^{i}(\cdot)\colon\mathbb{R}^{d}\to\mathbb{R}^{d}$ is smooth over $x\in
Q_{z}^{i}$.

  6. (f)

$\nabla\Psi_{i}([\cdot],[z])|_{x}=v_{z}^{i}(x)$ for $x\in Q_{z}^{i}$.

  7. (g)

For $x,z\in P(G)$, $\langle x,v_{z}^{i}(x)\rangle=\langle
z,v_{x}^{i}(z)\rangle$.

###### Proof.

The proofs of (a), (b), (c) and (d) are straightforward. By 35(b), it holds
that $v_{z}^{i}(\cdot)$ is smooth over $Q_{z}^{i}\cap V_{[p]_{0}}^{i}$ for
every $p\in\pi_{0}([z])$. Then, (e) follows since
$Q_{z}^{i}=\sqcup_{p\in\pi_{0}([z])}Q_{z}^{i}\cap V_{[p]_{0}}^{i}$. The
formula of the gradient in (f) follows from 29(d). Lastly, (g) follows by
Lemma 45 and (a). ∎

##  4 Upper Lipschitz Continuity

In this section, we estimate the upper Lipschitz bound of a coorbit filter
bank by the maximum singular value one may obtain by selecting an element from
each template’s orbit.

######  Theorem 48.

Given $G\leq\operatorname{O}(d)$ with closed orbits,
$z_{1},\ldots,z_{n}\in\mathbb{R}^{d}$ and
$p_{1},\dots,p_{n}\in\\{1,\dots,|\pi_{0}(G)|\\}$, the coorbit filter bank
$\Phi\colon\mathbb{R}^{d}/G\to\mathbb{R}^{n}$ defined by
$\Phi([x]):=\\{\Psi_{p_{i}}([z_{i}],[x])\\}_{i=1}^{n}$ satisfies

$\sup_{\begin{subarray}{c}[x],[y]\in\mathbb{R}^{d}/G\\\
{[x]\neq[y]}\end{subarray}}\frac{\|\Phi([x])-\Phi([y])\|}{d([x],[y])}\leq\max_{g_{1},\ldots,g_{n}\in
G}\|\\{g_{i}z_{i}\\}_{i=1}^{n}\|_{2\to 2}.$

In fact, the result for a max filter bank has been previously established and
we will make use of it to show the same bound for coorbit filter banks:

######  Proposition 49 (Theorem 9 in [29]).

The statement of Theorem 48 holds when $p_{i}\equiv 1$.

Before proceeding, we prove a technical lemma. For $x,y\in\mathbb{R}^{d}$, we
let $[x,y]$ denote the line segment from $x$ to $y$.

######  Lemma 50.

Fix a compact group $G\leq\operatorname{O}(d)$ with identity component $G_{0}$
and fix $i\in\\{1,\dots,|\pi_{0}(G)|\\}$. Fix $x,y,z\in\mathbb{R}^{d}$. Then,
there exists $n\in\mathbb{N}$ and $c_{1}<\cdots<c_{n}\in[x,y]$ such that

  * (a)

$c_{1}=x$ and $c_{n}=y$.

  * (b)

For every $j\in\\{1,\dots,n-1\\}$, there exists $K_{j}\in\pi_{0}(G)$ such that
$[c_{j},c_{j+1}]\subseteq\overline{V_{[K_{j}z]_{0}}^{i}}$.

For that, we need the following proposition regarding the dimension of the
closure of a semialgebraic set:

######  Proposition 51 (Proposition 2.8.2 in [7]).

Let $A\subseteq\mathbb{R}^{n}$ be a semialgebraic set. Then, $\overline{A}$ is
semialgebraic and

$\dim(A)=\dim(\overline{A}).$

###### Proof of Lemma 50.

First, observe that

$[x,y]=[x,y]\cap\overline{Q^{i}_{[z]_{0}}}=\bigcup_{K\in\pi_{0}(G)}\big{(}[x,y]\cap\overline{V_{[Kz]_{0}}^{i}}\big{)}.$

By Lemma 38 and Proposition 51 and for every $K\in\pi_{0}(G)$, it holds that
$[x,y]\cap\overline{V_{[Kz]_{0}}^{i}}$ is closed, semialgebraic and at most
one-dimensional. By semialgebraicity, $[x,y]\cap\overline{V_{[Kz]_{0}}^{i}}$
is a finite union of manifolds each with dimension at most one, hence a finite
union of a collection of isolated points $B_{K}$ and a collection of closed
intervals $I_{K}$. As such, $[x,y]\setminus\bigcup_{K\in\pi_{0}(G)}(\cup
I_{K})=\varnothing$ since on one hand it is a subset of the finite set
$\bigcup_{K\in\pi_{0}(G)}B_{K}$ but on the other hand, it is open in $[x,y]$.
We conclude that

$\bigcup_{K\in\pi_{0}(G)}\big{(}[x,y]\cap\overline{V_{[Kz]_{0}}^{i}}\big{)}=\bigcup_{K\in\pi_{0}(G)}(\cup
I_{K}),$

and the result follows by partitioning. ∎

We also need the following useful result

######  Lemma 52.

Let $G\leq\operatorname{O}(d)$ be compact. Suppose $x,y\in\mathbb{R}^{d}$ such
that $d([x],[y])=\|x-y\|$. Then, for any $[c,w]\subseteq[x,y]$, it holds that
$d([c],[w])=\|c-w\|$.

###### Proof.

By applying 35(b) to $w\in[x,y]$, we obtain
$\\{x\\}\in\arg\min_{p\in[x]}d(p,w)$, and by applying it to $c\in[w,x]$, we
get $\\{w\\}\in\arg\min_{q\in[w]}d(w,c)$. The result follows. ∎

###### Proof of Theorem 48.

By Proposition 10, we may assume $G$ is closed without loss of generality. Fix
$x,y\in\mathbb{R}^{d}$ such that $[x]\neq[y]$ and $\|x-y\|=d([x],[y])$. Then,
for each $l\in[n]$, take $c_{1}^{l},\dots,c_{n_{l}}^{l}$ and
$\\{K_{j}^{l}\\}_{j=1}^{n_{l}}$ as in Lemma 50 applied with respect to
$z_{l}$. By refining the partition over $l$, we get that there exists
$m\in\mathbb{N}$ and $c_{1}<\cdots<c_{m}\in[x,y]$ such that

  * (a)

$c_{1}=x$ and $c_{m}=y$.

  * (b)

For every $j\in\\{1,\dots,m-1\\}$, there exists
$\\{K_{j}^{l}\\}_{l=1}^{n}\in\pi_{0}(G)^{n}$ such that
$[c_{j},c_{j+1}]\subseteq\bigcap_{l\in[n]}\overline{V_{[K_{j}^{l}z_{l}]_{0}}^{i}}$.

Then, for each $l\in[n]$, it holds that

$\displaystyle\Psi_{p_{l}}([x],[z_{l}])-\Psi_{p_{l}}([y],[z_{l}])$
$\displaystyle=\sum_{j=1}^{m}\big{(}\Psi_{p_{l}}([c_{j}],[z_{l}])-\Psi_{p_{l}}([c_{j+1}],[z_{l}])\big{)}$
$\displaystyle=\sum_{j=1}^{m}\big{(}\langle\langle[c_{j}],[K_{j}^{l}z_{l}]\rangle\rangle_{G_{0}}-\langle\langle[c_{j+1}],[K_{j}^{l}z_{l}]\rangle\rangle_{G_{0}}\big{)}$

where the second equality follows from Lemma 38. For $j\in\\{1,\dots,m-1\\}$,
define the max filter bank
$\Phi_{j}^{G_{0}}\colon\mathbb{R}^{d}/G\to\mathbb{R}$ by
$\Phi_{j}^{G_{0}}([y])=\\{\langle\langle[y],[K_{j}^{l}z_{l}]\rangle\rangle_{G_{0}}\\}_{l=1}^{n}$.
Then, by Lemma 52 and the above,

$\frac{\Phi([x])-\Phi([y])}{d([x],[y])}=\sum_{j=1}^{m}\frac{\|c_{j+1}-c_{j}\|}{\|x-y\|}\cdot\frac{\Phi_{j}^{G_{0}}([c_{j}]_{0})-\Phi_{j}^{G_{0}}([c_{j+1}]_{0})}{d_{G_{0}}([c_{j}]_{0},[c_{j+1}]_{0})}$

The result now follows by taking norms, applying the triangle inequality and
using Proposition 49. ∎

##  5 Injectivity and Weak Avoidance

In this section, we show that $2c+k$ generic tempaltes suffice for coorbit
filter banks to weakly avoid a fixed or generic $k$-dimensional subspace.

######  Theorem 53.

Suppose the orbits of $G$ are closed with cohomogeniety $c$. Fix
$n\in\mathbb{N}$, $k\in\mathbb{Z}_{\geq 0}$ and
$p_{1},\dots,p_{n}\in\\{1,\dots,|\pi_{0}(G)|\\}$. For a fixed or generic
$V\in\mathbb{R}^{n\times k}$ and generic
$z_{1},\ldots,z_{n}\in\mathbb{R}^{d}$, the coorbit filter bank
$\Phi\colon\mathbb{R}^{d}/G\to\mathbb{R}^{n}$ defined by
$\Phi([x]):=\\{\Psi_{p_{i}}([z_{i}],[x])\\}_{i=1}^{n}$ weakly avoids
$\operatorname{im}(V)$ provided $n\geq 2c+k$.

In particular, when $k=0$, the coorbit filter bank is injective provided
$n\geq 2c$.

When $V\in\mathbb{R}^{n\times k}$ is fixed, Theorem 53 is an immediate
consequence of the following lemma which gives a bound on the dimension of the
set of coorbit filter banks that fail to weakly avoid $\operatorname{im}(V)$.
The remark that follows addresses the case when $V\in\mathbb{R}^{n\times k}$
is generic in Theorem 53.

######  Lemma 54.

Suppose $G\leq\operatorname{O}(d)$ is compact with cohomogeniety $c$. Fix
$n\in\mathbb{N}$, $k\in\mathbb{Z}_{\geq 0}$ and
$p_{1},\dots,p_{n}\in\\{1,\dots,|\pi_{0}(G)|\\}$. For
$z_{1},\ldots,z_{n}\in\mathbb{R}^{d}$, denote by
$\Phi\colon\mathbb{R}^{d}/G\to\mathbb{R}^{n}$ the coorbit filter bank defined
by $\Phi([x]):=\\{\Psi_{p_{i}}([z_{i}],[x])\\}_{i=1}^{n}$. For
$V\in\mathbb{R}^{n\times k}$, consider the $G^{n}$-invariant failure set

$B_{V}:=\big{\\{}\\{z_{i}\\}_{i=1}^{n}\in(\mathbb{R}^{d})^{n}:\Phi\text{ fails
to weakly avoid }\operatorname{im}(V)\big{\\}}.$

Then, $B_{V}$ is semialgebraic and $\dim(B_{V})\leq nd-1-(n-2c-k)$

######  Remark 55.

By further taking

$B:=\big{\\{}\big{(}\\{z_{i}\\}_{i=1}^{n},V\big{)}\in(\mathbb{R}^{d})^{n}\times\mathbb{R}^{n\times
k}:\Phi\text{ fails to weakly avoid }\operatorname{im}(V)\big{\\}}$

as in Lemma 15, we argue that $\dim(B)\leq nd+nk+(n-2c-k)$. Let $\Pi_{2}$ be
the projection of $(\mathbb{R}^{d})^{n}\times\mathbb{R}^{n\times k}$ onto the
second component. Then, by conservation of dimension (9(c)), we have

$\dim(B)\leq\Pi_{2}(B)+\max_{V\in\Pi_{2}(B)}\dim(\Pi_{2}^{-1}(V)\cap B).$

Moreover, for every $V\in\mathbb{R}^{n\times k}$, we have
$\dim(\Pi_{2}^{-1}(V)\cap B)=\dim(B_{V})$. Hence, the claim follows by Lemma
54 and the bound $\dim(\Pi_{2}(B))\leq nk$.

The rest of this section is dedicated to proving Lemma 54. To pass from the
dimension $d$ of $\mathbb{R}^{d}$ to the cohomogeneity of the group, we
leverage the following proposition:

######  Proposition 56 (Lemma 1 in [13]).

Consider $G\leq\operatorname{O}(d)$ with closed orbits. Then, for any
$x\in\mathbb{R}^{d}$, it holds that $G\cdot N_{x}=\mathbb{R}^{d}$, that is
$N_{x}$ intersects every orbit.

We also need to the following lemma which shows that the coorbit map is
“strongly separating” (cf. [10, 29]):

######  Lemma 57.

Suppose $G\leq\operatorname{O}(d)$ is compact. Fix $1\leq j\leq|\pi_{0}(G)|$,
$r\in\mathbb{R}$ and $x,y\in\mathbb{R}^{d}$ such that $[x]\neq[y]$. Then,

$\dim\big{\\{}z\in\mathbb{R}^{d}:\Psi_{j}([z],[x])-\Psi_{j}([z],[y])=r\big{\\}}\leq
d-1.$

###### Proof.

Suppose by contradiction that there exists a nonempty open set $U$ such that
$h(z):=\Psi_{j}([z],[x])-\Psi_{j}([z],[y])=r$ for all $z\in U$. By Lemma 44,
$Q_{x}^{j}\cap Q_{y}^{j}$ is open and dense, so we may shrink $U$ so that
$U\subseteq Q_{x}^{j}\cap Q_{y}^{j}$. Then, by Lemma 47, it follows that
$\nabla h(z)=v_{x}^{j}(z)-v_{y}^{j}(z)=0$ for $z\in U$. Since
$v_{x}^{j}(z)\in[x]$ and $v_{y}^{j}(z)\in[y]$, we obtain the contradiction
$[x]=[y]$. ∎

###### Proof of Lemma 54.

Semialgebraicity follows from $B_{V}$ being a projection of the $V$ section of
the semialgebraic set $B$ defined in Lemma 15. Let $N:=N_{w}$ for some $w\in
P(G)$. Then $G\cdot N=\mathbb{R}^{d}$ by Proposition 56. Fix
$V\in\mathbb{R}^{n\times k}$ and consider the semialgebraic lift of $B_{V}$

$\displaystyle L_{V}:=\big{\\{}\big{(}\\{z_{i}\\}_{i=1}^{n},p,x,y\big{)}\in$
$\displaystyle(\mathbb{R}^{d})^{n}\times\mathbb{R}^{k}\times(\mathbb{R}^{d})^{2}:$
$\displaystyle[x]\neq[y],\|x\|^{2}+\|y\|^{2}=1,x\in N,y\in N,$
$\displaystyle\Psi_{p_{i}}([z_{i}],[x])-\Psi_{p_{i}}([z_{i}],[y])=d([x],[y])\cdot(Vp)_{i}\
\forall i\in\\{1,\ldots,n\\}\big{\\}}.$

Observe that $B_{V}$ is a projection of $L_{V}$ on the $\\{z_{i}\\}_{i=1}^{n}$
coordinate. Denote by $\Pi_{pxy}$ the projection of
$(\mathbb{R}^{d})^{n}\times\mathbb{R}^{k}\times(\mathbb{R}^{d})^{2}$ on the
components $(p,x,y)$. By conservation of dimension (9(c)), we get

$\dim(B_{V})\leq\dim(L_{V})\leq\Pi_{pxy}(L_{V})+\max_{(p,x,y)\in\Pi_{pxy}(L_{V})}\dim(\Pi_{pxy}^{-1}(p,x,y)\cap
L_{V}).$

Observe that $\dim(\Pi_{pxy}(L_{V}))\leq(2c-1)+k$ since $x,y\in N$ and
$p\in\mathbb{R}^{k}$ contribute $2c+k$ degrees of freedom while the condition
$\|x\|^{2}+\|y\|^{2}=1$ takes away one. It now suffices to show that

$\dim(\Pi_{pxy}^{-1}(p,x,y)\cap L_{V})\leq n(d-1)$

for every $(p,x,y)\in\Pi_{pxy}(L_{V})$. To this end, fix
$(p,x,y)\in\Pi_{pxy}(L_{V})$ and observe that

$\displaystyle\dim(\Pi_{pxy}^{-1}(p,x,y)\cap L_{V})$
$\displaystyle=\dim\big{\\{}\\{z_{i}\\}_{i=1}^{n}\in(\mathbb{R}^{d})^{n}:\Psi_{p_{i}}([z_{i}],[x])-\Psi_{p_{i}}([z_{i}],[y])=d([x],[y])\cdot(Vp)_{i}\
\forall i\in\\{1,\ldots,n\\}\big{\\}}$ $\displaystyle\leq
n\cdot\max_{\begin{subarray}{c}1\leq j\leq|\pi_{0}(G)|\\\
r\in\mathbb{R}\end{subarray}}\dim\big{\\{}z\in\mathbb{R}^{d}:\Psi_{j}([z],[x])-\Psi_{j}([z],[y])=r\big{\\}}$
$\displaystyle\leq n\cdot(d-1)$

where the last inequality follows from Lemma 57. This finishes the proof. ∎

##  6 Local Avoidance at Principal Points

The purpose of this section is to show that $2c+k-1$ generic templates suffice
for a coorbit filter bank to locally avoid a fixed or generic $k$-dimensional
subspace at principal points.

######  Theorem 58.

Suppose $G\leq\operatorname{O}(d)$ is compact with cohomogeniety $c$. Fix sort
indices $p_{1},\dots,p_{n}\in\\{1,\dots,|\pi_{0}(G)|\\}$. Then, for a fixed or
generic $V\in\mathbb{R}^{n\times k}$ and generic
$z_{1},\ldots,z_{n}\in\mathbb{R}^{d}$, the coorbit filter bank
$\Phi\colon\mathbb{R}^{d}/G\to\mathbb{R}^{n}$ defined by
$\Phi([x]):=\\{\Psi_{p_{i}}([z_{i}],[x])\\}_{i=1}^{n}$ locally avoids
$\operatorname{im}(V)$ at every $x\in P(G)$ provided $n\geq 2c-1+k$.

In particular, when $k=0$ and with $n$ generic templates, the coorbit filter
bank is locally lower Lipschitz at every $x\in P(G)$ provided $n\geq 2c-1$.

We also settle Problem 18 for the case of groups acting freely on the sphere:

######  Theorem 59.

Suppose $G\leq\operatorname{O}(d)$ is compact with cohomogeniety $c$. If the
action of $G$ is free on the sphere, then $n^{\prime}(G)\leq 2c$.

In fact, Theorem 58 with fixed $V$ and Theorem 59 follow immediately from the
following lemma. The case of generic $V$ in Theorem 58 follows by a similar
argument as in Remark 55.

######  Lemma 60.

Suppose $G\leq\operatorname{O}(d)$ is compact with cohomogeniety $c$. Fix
$n\in\mathbb{N}$, $k\in\mathbb{Z}_{\geq 0}$ and
$p_{1},\dots,p_{n}\in\\{1,\dots,|\pi_{0}(G)|\\}$. For
$z_{1},\ldots,z_{n}\in\mathbb{R}^{d}$, denote by
$\Phi\colon\mathbb{R}^{d}/G\to\mathbb{R}^{n}$ the coorbit filter bank defined
by $\Phi([x]):=\\{\Psi_{p_{i}}([z_{i}],[x])\\}_{i=1}^{n}$. For
$V\in\mathbb{R}^{n\times k}$, consider the failure set

$C_{V}:=\big{\\{}\\{z_{i}\\}_{i=1}^{n}\in(\mathbb{R}^{d})^{n}:\Phi\text{ fails
to locally avoid }\operatorname{im}(V)\text{ at every }x\in P(G)\big{\\}}.$

Then, $C_{V}$ is semialgebraic and $\dim(C_{V})\leq nd-1-(n-2c-k+1)$.

The rest of this section is dedicated to proving Lemma 60. We need the
following lemma which is essential in reducing the proof to the linear algebra
of singular value decompoisitions.

######  Lemma 61.

Suppose $G\leq\operatorname{O}(d)$ is compact, $x\in P(G)$ and $x_{n},y_{n}\to
x$ with $[x_{n}]\neq[y_{n}]$. Then, there exists a nonzero $u\in N_{x}$ such
that

$\|u\|=\liminf_{n\to\infty}\frac{||x_{n}-y_{n}||}{d([x_{n}],[y_{n}])}\in[1,\infty)$

and such that for each $i\in\\{1,\dots,|\pi_{0}(G)|\\}$ and for each $z\in
Q_{x}^{i}$, the following convergence holds after taking subsequences

$\frac{\Psi_{i}([x_{n}],[z])-\Psi_{i}([y_{n}],[z])}{d([x_{n}],[y_{n}])}\to\langle
v^{i}_{z}(x),u\rangle.$

###### Proof.

The proof is technical and is postponed to Section B.2. ∎

For $n\geq c$ and a matrix $X\in\mathbb{R}^{n\times c}$, we denote by
$\sigma_{c}(X)$ the minimum singular value of $X$. When $n<c$, we take
$\sigma_{c}(X):=0$. Then, Lemma 61 immediately yields the following
interesting corollary.

######  Corollary 62.

Suppose $G\leq\operatorname{O}(d)$ is compact with cohomogeniety $c$. Fix sort
indices $p_{1},\dots,p_{n}\in\\{1,\dots,|\pi_{0}(G)|\\}$. For
$z_{1},\ldots,z_{n}\in\mathbb{R}^{d}$, denote by
$\Phi\colon\mathbb{R}^{d}/G\to\mathbb{R}^{n}$ the coorbit filter bank defined
by $\Phi([x]):=\\{\Psi_{p_{i}}([z_{i}],[x])\\}_{i=1}^{n}$. Then, for $x\in
P(G)$, $\Phi$ is $\sigma_{c}(\\{\langle
v^{p_{i}}_{z_{i}}(x),\cdot\rangle\\}_{i=1}^{n}|_{N_{x}})$-locally lower
Lipschitz at $x$.

###### Proof.

Let $x_{n},y_{n}\to x$ be such that $[x_{n}]\neq[y_{n}]$. By Lemma 61, there
exists nonzero $u\in N_{x}$ such that $\|u\|\geq 1$ and

$Q(x_{n},y_{n})\to\|u\|\cdot\left\\{\left\langle
v^{p_{i}}_{z_{i}}(x),\frac{u}{\|u\|}\right\rangle\right\\}_{i=1}^{n}$

The result now follows by taking norms and using $\|u\|\geq 1$. ∎

###### Proof of Lemma 60.

Semialgebraicity follows from $C_{V}$ being a projection of the $V$ section of
the semialgebraic set $C_{P(G)}$ defined in Lemma 15. Let $N:=N_{w}$ for some
$w\in P(G)$. Then, $G\cdot N=\mathbb{R}^{d}$ by Proposition 56. Denote by $Q$
the difference quotient corresponding to $\Phi$ and put
$P_{\mathbb{S}}(G):=\mathbb{S}^{d-1}\cap P(G)$. Fix $V\in\mathbb{R}^{n\times
k}$ and consider a semialgebraic lift of $C_{V}$

$\displaystyle W_{V}$
$\displaystyle:=\big{\\{}\big{(}\\{z_{i}\\}_{i=1}^{n},x\big{)}\in(\mathbb{R}^{d})^{n}\times(P_{\mathbb{S}}(G)\cap
N):\Phi\text{ does not locally avoid }\text{im}(V)\text{ at }x\big{\\}}$
$\displaystyle=\big{\\{}\big{(}\\{z_{i}\\}_{i=1}^{n},x\big{)}\in(\mathbb{R}^{d})^{n}\times(P_{\mathbb{S}}(G)\cap
N):\exists p\in\mathbb{R}^{k},\forall\varepsilon\in\mathbb{R}_{>0},\exists
x_{0},y_{0}\in\mathbb{R}^{d},$
$\displaystyle\qquad\qquad[x_{0}]\neq[y_{0}]\wedge|Q(x_{0},y_{0})-Vp|<\varepsilon\wedge[x_{0}],[y_{0}]\in
B_{[x]}(\varepsilon)\big{\\}}.$

Observe that $C_{V}$ is a projection of $W_{V}$ on its $\\{z_{i}\\}_{i=1}^{n}$
coordinate.

For
$\big{(}\\{z_{i}\\}_{i=1}^{n},x\big{)}\in(\mathbb{R}^{d})^{n}\times(P_{\mathbb{S}}(G)\cap
N)$ with associated Voronoi coorbit realizers denoted by
$v_{i}:=v^{p_{i}}_{z_{i}}$, define
$I_{x,\\{z_{i}\\}}:=\operatorname{diag}\big{(}\\{1_{v_{i}(x)\neq
0}\\}_{i=1}^{n}\big{)}\in\mathbb{R}^{n\times n}$. By Lemma 47, it is
semialgebraic in $\big{(}\\{z_{i}\\}_{i=1}^{n},x\big{)}$. Now, let
$\mathbb{I}:=\\{I\in\mathbb{R}^{n\times
n}:I=\operatorname{diag}\\{\varepsilon_{i}\\}_{i=1}^{n},\\{\varepsilon_{i}\\}_{i=1}^{n}\in\\{0,1\\}_{i=1}^{n}\\}$.
We have a partion $W_{V}=\bigcup_{I\in\mathbb{I}}W_{V}^{I}$ where

$W_{V}^{I}:=\big{\\{}\big{(}\\{z_{i}\\}_{i=1}^{n},x\big{)}\in(\mathbb{R}^{d})^{n}\times(P_{\mathbb{S}}(G)\cap
N):I_{x,\\{z_{i}\\}}=I\text{ and }\Phi\text{ does not locally avoid
}\text{im}(V)\text{ at }x\big{\\}}.$

To the end of bounding
$\dim(C_{V})\leq\dim(W_{V})=\max_{I\in\mathbb{I}}\dim(W_{V}^{I})$, we fix a
dimension maximizing $I\in\mathbb{I}$ and proceed with bounding
$\dim(W_{V}^{I})$. Without loss of generality, we take
$\\{j:I_{jj}=1\\}=\\{1,\dots,m\\}$ for some $m\in\\{0,\dots,n\\}$. Denote by
$\Pi_{2}$ the projection of $\big{(}\\{z_{i}\\}_{i=1}^{n},x\big{)}\mapsto x$.
By conservation of dimension (9(c)),

$\dim(C_{V})\leq\dim(W_{V}^{I})\leq\dim(\Pi_{2}(W_{V}^{I}))+\max_{x\in\Pi_{2}(W_{V}^{I})}\dim(\Pi_{2}^{-1}(x)\cap
W_{V}^{I}).$

Observe that $\dim(\Pi_{2}(W_{V}^{I}))\leq\dim(P_{\mathbb{S}}(G)\cap N)=c-1$.
It now suffices to fix $x\in\Pi_{2}(W_{V}^{I})$ and show that
$\dim(\Pi_{2}^{-1}(x)\cap W_{V}^{I})\leq nd-1-(n-k-c)$.

Let $\Phi_{I}$ denote the coorbit filter bank corresponding to templates
$\\{z_{i}\\}_{i=1}^{m}$ and sort indices $\\{p_{i}\\}_{i=1}^{m}$. For
$\\{z_{i}\\}_{i=1}^{n}\in\Pi_{2}^{-1}(x)\cap W_{V}^{I}$ and by definition of
$I\in\mathbb{I}$, we have that
$\\{z_{i}\\}_{i=1}^{m}\in\prod_{i=1}^{m}Q_{x}^{p_{i}}$ and
$\\{z_{i}\\}_{i=m+1}^{n}\in\prod_{i=m+1}^{n}(Q_{x}^{p_{i}})^{c}$. Next, let
$V_{m}\in\mathbb{R}^{m\times n}$ denote the truncation of $V$ that only keeps
its first $m$ rows. By Lemma 61, we have

$\\{z_{i}\\}_{i=1}^{m}\in
E:=\left\\{\\{z_{i}\\}_{i=1}^{m}\in\prod_{i=1}^{m}Q_{x}^{p_{i}}:\operatorname{im}(\\{\langle
v_{i}(x),\cdot\rangle|_{N_{x}\setminus\\{0\\}}\\}_{i=1}^{m})\cap\operatorname{im}(V_{m})\neq\varnothing\right\\}.$

Note that $E$ is semialgebraic. We obtain

$\Pi_{2}^{-1}(x)\cap W_{V}^{I}\subseteq
E\times\prod_{i=m+1}^{n}(Q_{x}^{p_{i}})^{c}.$

Since $\dim\left(\prod_{i=m+1}^{n}(Q_{x}^{p_{i}})^{c}\right)\leq(n-m)(d-1)$,
we get

$\dim(\Pi_{2}^{-1}(x)\cap W_{V}^{I})\leq\dim(E)+(n-m)(d-1).$

It now suffices to show that $\dim(E)\leq md-1-(m-k-c)$. We lift $E$ to

$\displaystyle
E_{L}:=\Big{\\{}\big{(}\\{z_{i}\\}_{i=1}^{m},\\{v_{i}\\}_{i=1}^{m}\big{)}\in$
$\displaystyle(\mathbb{R}^{d})^{m}\times\prod_{i=1}^{m}V_{x}^{p_{i}}:\operatorname{im}(\\{\langle
v_{i},\cdot\rangle|_{N_{x}\setminus\\{0\\}}\\}_{i=1}^{m})\cap\operatorname{im}(V_{m})\neq\varnothing$
$\displaystyle\qquad\qquad\qquad\qquad\quad\wedge\exists\\{g_{i}\\}_{i=1}^{m}\in
G^{m},z_{i}=g_{i}v_{i}\ \forall i\in[m]\Big{\\}}.$

Let $\pi_{1}$ and $\pi_{2}$ denote projections on the $\\{z_{i}\\}_{i=1}^{m}$
and $\\{v_{i}\\}_{i=1}^{m}$ coordinates respectively. Then, $E=\pi_{1}(E_{L})$
and for any $\\{v_{i}\\}_{i=1}^{m}\in\pi_{2}(E_{L})$, we have
$\dim(\pi_{2}^{-1}(\\{v_{i}\\}_{i=1}^{m}))\leq m(d-c)$ since each $z_{i}$ has
at most $d-c$ degrees of freedom in the fiber. By conservation of dimension
(9(c)), it suffices to show that $\dim(\pi_{2}(E_{L}))\leq mc-1-(m-k-c)$.
Since $V_{x}^{p_{i}}\subseteq N_{x}$, we have

$\pi_{2}(E_{L})\subseteq F:=\big{\\{}\\{v_{i}\\}_{i=1}^{m}\in
N_{x}^{m}:\operatorname{im}(\\{\langle
v_{i},\cdot\rangle|_{N_{x}\setminus\\{0\\}}\\}_{i=1}^{m})\cap\operatorname{im}(V_{m})\neq\varnothing\big{\\}}$

where we note that $F$ is semialgebraic. By identifying $N_{x}$ with
$\mathbb{R}^{c}$, we lift to the space of singular value decompositions

$\displaystyle F_{L}:=$
$\displaystyle\big{\\{}\big{(}\\{v_{i}\\}_{i=1}^{m},U,\Sigma,W\big{)}\in(\mathbb{R}^{c})^{m}\times\mathbb{R}^{c\times(c-1)}\times
D_{\geq 0}^{(c-1)\times(c-1)}\times\mathbb{R}^{m\times(c-1)}:$
$\displaystyle\qquad\qquad\qquad U^{T}U=\operatorname{Id}_{c-1}\wedge
W^{T}W=\operatorname{Id}_{c-1}\wedge\\{\langle
v_{i},\cdot\rangle|_{\mathbb{R}^{c}}\\}_{i=1}^{m}=W\Sigma U^{T}\big{\\}}$
$\displaystyle\cup\big{\\{}\big{(}\\{v_{i}\\}_{i=1}^{m},U,\Sigma,W\big{)}\in(\mathbb{R}^{c})^{m}\times\mathbb{R}^{c\times
c}\times D_{\geq 0}^{c\times c}\times\mathbb{R}^{m\times
c}:U^{T}U=\operatorname{Id}_{c}\wedge W^{T}W=\operatorname{Id}_{c}$
$\displaystyle\qquad\wedge\big{(}\exists v\in\operatorname{im}(V_{m}),\exists
O\in\operatorname{O}(c),v\text{ is a column of $WO$}\big{)}\wedge\\{\langle
v_{i},\cdot\rangle|_{\mathbb{R}^{c}}\\}_{i=1}^{m}=W\Sigma U^{T}\big{\\}}.$

where $D_{\geq 0}^{c\times c}$ is the space of diagonal matrices with
nonnegative entries. We note that $F_{L}$ is semialgebraic and $F$ is the
projection of $F_{L}$ onto the first component $\\{v_{i}\\}_{i=1}^{m}$. Let
$\pi_{\sigma}$ denote the projection onto the other three components
$(U,\Sigma,W)$. Then, the fibers of $\pi_{\sigma}$ are singleton. Hence, by
conservation of dimension (9(c)), it suffices to show that
$\dim(\pi_{\sigma}(F_{L}))\leq mc-1-(m-k-c)$. We have

$\displaystyle\pi_{\sigma}(F_{L}):=\big{\\{}\big{(}U,\Sigma,W\big{)}\in$
$\displaystyle\mathbb{R}^{c\times(c-1)}\times D_{\geq
0}^{(c-1)\times(c-1)}\times\mathbb{R}^{m\times(c-1)}:U^{T}U=\operatorname{Id}_{c-1}\wedge
W^{T}W=\operatorname{Id}_{c-1}\big{\\}}$
$\displaystyle\cup\big{\\{}\big{(}U,\Sigma,W\big{)}\in$
$\displaystyle\mathbb{R}^{c\times c}\times D_{\geq 0}^{c\times
c}\times\mathbb{R}^{m\times c}:U^{T}U=\operatorname{Id}_{c}\wedge
W^{T}W=\operatorname{Id}_{c}$ $\displaystyle\wedge\exists
v\in\operatorname{im}(V_{m}),\exists O\in\operatorname{O}(c),v\text{ is a
column of $WO$}\big{\\}}.$

We count dimensions. For the first set and by orthonormality constraints, it
holds that $\Sigma$ has $c$ degrees of freedom, $U$ has $c(c-1)-c-c(c-1)/2$
degrees of freedom and $W$ has $m(c-1)-(c-1)-(c-1)(c-2)/2$ degrees of freedom.
The total degrees of freedom are $mc-1-(m-c)$. For the second set, if some
$v\in\operatorname{im}(V_{m})$ is a column of $WO$, then $\Sigma$ has $c$
degrees of freedom and $U$ has $c^{2}-c-c(c-1)/2$ degrees of freedom. With
$O\in\operatorname{O}(c)$ fixed, $WO$ has $m(c-1)+k-c-c(c-1)/2$ degrees of
freedom. These degrees of freedom also account for a right action of $O(c-1)$
which keeps $v$ as a column of $WO$. Then, $W$ may only get an additional
$\dim(\operatorname{O}(c)/\operatorname{O}(c-1))=c-1$ degrees of freedom. By
summing up, the dimension is bounded by $mc-1-(m-k-c)$ and the result follows.
∎

In fact, from the proof above, we have

######  Corollary 63.

Suppose $G\leq\operatorname{O}(d)$ is compact with cohomogeniety $c$. Fix sort
indices $p_{1},\dots,p_{n}\in\\{1,\dots,|\pi_{0}(G)|\\}$. Then, for generic
$z_{1},\ldots,z_{n}\in\mathbb{R}^{d}$,

$\sigma_{c}(\\{\langle
v^{p_{i}}_{z_{i}}(x),\cdot\rangle\\}_{i=1}^{n}|_{N_{x}})>0$

for every $x\in P(G)$ provided $n\geq 2c-1$.

##  7 Strong Avoidance Reduction to Full Groups

######  Definition 64.

For a compact subgroup $G\leq\operatorname{O}(d)$, we denote

$F_{G}:=\\{x\in\mathbb{R}^{d}:G_{x}=G\\}.$

We say that the action of $G$ is full if $F_{G}=\\{0\\}$.

Note that $F_{G}^{\perp}$ is the largest invariant subspace over which the
restriction of $G$ is full. In this section, we show how strong avoidance for
a group $G$ reduces to its action on $F_{G}^{\perp}$:

######  Theorem 65.

Suppose $G\leq\operatorname{O}(d)$ is compact. Let $F:=F_{G}$ and denote by
$G_{F^{\perp}}\leq\operatorname{O}(F^{\perp})$ the restriction of $G$ to
$F^{\perp}$. Then, $n_{k}(G)\leq n_{k+\dim(F)}(G_{F^{\perp}})$ and
$n^{\prime}(G)\leq n^{\prime}(G_{F^{\perp}})+\dim(F)$.

Once we show the following lemma, the proof of Theorem 65 follows:

######  Lemma 66.

Suppose $G\leq\operatorname{O}(d)$ is compact and $F:=F_{G}$, and denote by
$G_{F^{\perp}}\leq\operatorname{O}(F^{\perp})$ the restriction of $G$ to
$F^{\perp}$. Then, for $k\geq 0$ and $m\geq k+\dim(F)$, it holds that

$v_{k}^{m}(G)\geq\min\\{m-k-\dim(F)+1,v_{k+\dim(F)}^{m}(G_{F^{\perp}})\\}.$

###### Proof of Theorem 65.

Denote $f:=\dim(F)$. First, we tackle the assertion $n^{\prime}(G)\leq
n^{\prime}(G_{F^{\perp}})+f$. By definition of $n^{\prime}(G_{F^{\perp}})$,

$v_{k+f}^{m}(G_{F^{\perp}})\geq m-k-f-n^{\prime}(G_{F^{\perp}})+1.$

By Lemma 66 and with $m\geq k+f$, we have

$\displaystyle v_{k}^{m}(G)$
$\displaystyle\geq\min\big{\\{}m-k-f+1,v_{k+f}^{m}(G_{F^{\perp}})\big{\\}}$
$\displaystyle\geq
m-k-f+1+\min\big{\\{}0,v_{k+f}^{m}(G_{F^{\perp}})-m+k+f-1\big{\\}}$
$\displaystyle\geq m-k-f+1+\min\\{0,-n^{\prime}(G_{F^{\perp}})\\}$
$\displaystyle\geq m-k-f+1-n^{\prime}(G_{F^{\perp}})$

The inequality still holds when $m<k+f$ since $v_{k}^{m}(G)\geq 0$ and
$n^{\prime}(G_{F^{\perp}})\geq 1$. Then, the assertion $n^{\prime}(G)\leq
n^{\prime}(G_{F^{\perp}})+f$ follows by definition of $n^{\prime}(G)$.

Next, we tackle the assertion $n_{k}(G)\leq n_{k+f}(G_{F^{\perp}})$. By Remark
17, recall that $n_{k+f}(G_{F^{\perp}})>k+f$. Then, for $m\geq
n_{k+f}(G_{F^{\perp}})>k+f$, Lemma 66 entails that
$v_{k}^{m}(G)\geq\min\\{m-k-f+1,v_{k+f}^{m}(G_{F^{\perp}})\\}>0$. By
definition of $n_{k}(G)$, it follows that $n_{k}(G)\leq
n_{k+f}(G_{F^{\perp}})$ as desired. ∎

The rest of this section is dedicated to proving Lemma 66. First, we need to
unpack how the coorbit map and the quotient distance interact with the
decomposition $F_{G}\oplus F_{G}^{\perp}$.

######  Lemma 67.

Fix a compact group $G\leq\operatorname{O}(d)$ and a sort index
$i\in\\{1,\dots,|\pi_{0}(G)|\\}$. Let $F:=F_{G}$. Denote by $P_{F}$ and
$P_{F}^{\perp}$ the orthogonal projections of $\mathbb{R}^{d}$ onto $F$ and
$F^{\perp}$ respectively. Then, for $y,z\in\mathbb{R}^{d}$, it holds that

$\Psi_{i}([z],[y])=\Psi_{i}([P_{F}^{\perp}z],[P_{F}^{\perp}y])+\langle
P_{F}z,P_{F}y\rangle$

and

$d([z],[y])^{2}=d([P_{F}^{\perp}z],[P_{F}^{\perp}y])^{2}+\|P_{F}z-P_{F}y\|^{2}.$

###### Proof.

Note that by the $G$-invariant orthogonal decomposition
$\mathbb{R}^{d}=F\oplus_{G}F^{\perp}$, we have
$\operatorname{Id}=P_{F}+P_{F}^{\perp}$, $P_{F}^{\perp}g=gP_{F}^{\perp}$ and
$P_{F}g=gP_{F}=P_{F}$ for any $g\in G$. The first equality is by orthogonal
decomposition and the second equality follows from the following computation

$P_{F}^{\perp}g=P_{F}^{\perp}g(P_{F}+P_{F}^{\perp})=P_{F}^{\perp}gP_{F}+P_{F}^{\perp}gP_{F}^{\perp}=gP_{F}^{\perp}.$

The last step follows from the $G$-invariance of $F$ and $F^{\perp}$. The
third equality $P_{F}g=gP_{F}=P_{F}$ follows by a similar computation and the
observation that $g$ fixes $F$.

Then, for any $K\in\pi_{0}(G)$, we have

$\mathcal{C}([z]_{0},[y]_{0},K)=\sup_{k\in K}\langle kz,y\rangle=\langle
P_{F}z,P_{F}y\rangle+\sup_{k\in K}\langle
kP_{F}^{\perp}z,P_{F}^{\perp}y\rangle=\langle
P_{F}z,P_{F}y\rangle+\mathcal{C}([P_{F}^{\perp}z]_{0},[P_{F}^{\perp}y]_{0},K)$

so that the first assertion follows by sorting. For the second assertion and
by the Pythagorean Theorem, it holds that

$\|gz-y\|^{2}=\|P_{F}^{\perp}(gz-y)\|^{2}+\|P_{F}(gz-y)\|^{2}=\|gP_{F}^{\perp}z-P_{F}^{\perp}y\|^{2}+\|P_{F}z-P_{F}y\|^{2}.$

The assertion then follows by taking the minimum over $g\in G$ on both sides.
∎

###### Proof of Lemma 66.

Fix arbitrary templates $\\{z_{i}\\}_{i=1}^{m}\in(\mathbb{R}^{d})^{m}$ and
arbitrary sort indices $\\{p_{i}\\}_{i=1}^{m}$. Denote the corresponding
coorbit filter map by $\Phi$ and the corresponding difference quotient by $Q$.
Fix $V\in\mathbb{R}^{m\times k}$. Suppose that $\Phi$ fails to strongly avoid
$\operatorname{im}(V)$. Then, there exists sequences $x_{n}\to x$ and
$y_{n}\to y$ such that $[x_{n}]\neq[y_{n}]$,
$d([x_{n}],[y_{n}])=\|x_{n}-y_{n}\|$, and
$\lim_{n\to\infty}Q(x_{n},y_{n})\in\operatorname{im}(V)$. By Lemma 67, the
following holds for every $i\in\\{1,\dots,m\\}$

$\displaystyle\frac{\Psi_{p_{i}}([z_{i}],[x_{n}])-\Psi_{p_{i}}([z_{i}],[y_{n}])}{d([x_{n}],[y_{n}])}$
$\displaystyle\qquad=\frac{d([P_{F}^{\perp}x_{n}],[P_{F}^{\perp}y_{n}])}{d([x_{n}],[y_{n}])}\cdot\frac{\Psi_{p_{i}}([P_{F}^{\perp}z_{i}],[P_{F}^{\perp}x_{n}])-\Psi_{p_{i}}([P_{F}^{\perp}z_{i}],[P_{F}^{\perp}y_{n}])}{d([P_{F}^{\perp}x_{n}],[P_{F}^{\perp}y_{n}])}$
$\displaystyle\qquad\qquad\qquad\qquad+\frac{\|P_{F}x_{n}-P_{F}y_{n}\|}{d([x_{n}],[y_{n}])}\cdot\left\langle
P_{F}z_{i},\frac{P_{F}x_{n}-P_{F}y_{n}}{\|P_{F}x_{n}-P_{F}y_{n}\|}\right\rangle$

where we define $\frac{0}{0}=\frac{0}{\|0\|}=0$. Set
$w_{1,n}:=\frac{d([P_{F}^{\perp}x_{n}],[P_{F}^{\perp}y_{n}])}{d([x_{n}],[y_{n}])}\geq
0$ and $w_{2,n}:=\frac{\|P_{F}x_{n}-P_{F}y_{n}\|}{d([x_{n}],[y_{n}])}\geq 0$
and $u_{n}:=\frac{P_{F}x_{n}-P_{F}y_{n}}{\|P_{F}x_{n}-P_{F}y_{n}\|}\in F$.
Denote by $\Phi_{F^{\perp}}$ the coorbit filter bank with group
$G_{F^{\perp}}\leq\operatorname{O}(F^{\perp})$, templates
$\\{P^{\perp}_{F}z_{i}\\}_{i=1}^{m}$ and sort indices $\\{p_{i}\\}_{i=1}^{m}$,
and denote by $Q_{F^{\perp}}$ the corresponding difference quotient. Then, for
every $i\in\\{1,\dots,m\\}$, it holds that

$Q(x_{n},y_{n})=w_{1,n}\cdot
Q_{F^{\perp}}(P^{\perp}_{F}x_{n},P^{\perp}_{F}y_{n})+w_{2,n}\cdot\left\langle
P_{F}z_{i},u_{n}\right\rangle$ (8)

where we take $Q_{F^{\perp}}(P^{\perp}_{F}x_{n},P^{\perp}_{F}y_{n}):=0$ if
$w_{1,n}=0$. By Lemma 67, we have $w_{1,n}^{2}+w_{2,n}^{2}=1$. Then, take a
subsequence such that $w_{j,n}\to w_{j}$ for $j\in\\{1,2\\}$ and $u_{n}\to
u\in F$. There are three cases of interest

  * (i)

If $w_{1}=0$, then $w_{2}=1$, $u\in F\cap\mathbb{S}^{d-1}$ and
$\lim_{n\to\infty}Q(x_{n},y_{n})=\left\langle
P_{F}z_{i},u\right\rangle\in\operatorname{im}(V)$. As such,
$\operatorname{im}(\\{\langle
P_{F}z_{i},\cdot\rangle|_{F\setminus\\{0\\}}\\}_{i=1}^{m})\cap\operatorname{im}(V)\neq\varnothing$.

  * (ii)

If $w_{2}=0$, then $w_{1}=1$ and
$\lim_{n\to\infty}Q(x_{n},y_{n})=\lim_{n\to\infty}Q_{F^{\perp}}(P_{F}^{\perp}x_{n},P_{F}^{\perp}y_{n})\in\operatorname{im}(V)\subseteq\operatorname{im}(V)+\operatorname{im}(\\{\langle
P_{F}z_{i},\cdot\rangle|_{F}\\}_{i=1}^{m})$, so $Q_{F^{\perp}}$ fails to
strongly avoid $\operatorname{im}(V)+\operatorname{im}(\\{\langle
P_{F}z_{i},\cdot\rangle|_{F}\\}_{i=1}^{m})$.

  * (iii)

If $w_{1},w_{2}>0$, then
$\lim_{n\to\infty}Q_{F^{\perp}}(P_{F}^{\perp}x_{n},P_{F}^{\perp}y_{n})=\frac{1}{w_{1}}\lim_{n\to\infty}Q(x_{n},y_{n})+\langle
P_{F}z_{i},-\frac{w_{2}}{w_{1}}u\rangle\in\operatorname{im}(V)+\operatorname{im}(\\{\langle
P_{F}z_{i},\cdot\rangle|_{F}\\}_{i=1}^{m})$. Again, $Q_{F^{\perp}}$ fails to
strongly avoid $\operatorname{im}(V)+\operatorname{im}(\\{\langle
P_{F}z_{i},\cdot\rangle|_{F}\\}_{i=1}^{m})$.

We obtain that $N_{V}^{\\{p_{i}\\}_{i=1}^{m}}\subseteq A_{1}\cup A_{2}$ where

$\displaystyle
N_{V}^{\\{p_{i}\\}_{i=1}^{m}}:=\\{\\{(P_{F}z_{i},P_{F}^{\perp}z_{i})\\}_{i=1}^{m}\in(F\times
F^{\perp})^{m}|\Phi\text{ fails to strongly avoid }\operatorname{im}(V)\\},$
$\displaystyle
A_{1}:=\big{\\{}\\{(P_{F}z_{i},P_{F}^{\perp}z_{i})\\}_{i=1}^{m}\in(F\times
F^{\perp})^{m}\big{|}\operatorname{im}(\\{\langle
P_{F}z_{i},\cdot\rangle|_{F\setminus\\{0\\}}\\}_{i=1}^{m})\cap\operatorname{im}(V)\neq\varnothing\big{\\}},$
$\displaystyle
A_{2}:=\big{\\{}\\{(P_{F}z_{i},P_{F}^{\perp}z_{i})\\}_{i=1}^{m}\in(F\times
F^{\perp})^{m}\big{|}\text{$Q_{F^{\perp}}$ fails to strongly avoid
$\operatorname{im}(V)+\operatorname{im}(\\{\langle
P_{F}z_{i},\cdot\rangle|_{F}\\}_{i=1}^{m})$}\big{\\}}.$

Note that $A_{1}$ and $A_{2}$ are semialgebraic. Denote $f:=\dim(F)$. We bound
dimensions of $A_{1}$ and $A_{2}$ using conservation of dimension (9(c)). For
$A_{1}$, $\\{P_{F^{\perp}}z_{i}\\}_{i=1}^{m}$ has $m(d-f)$ degrees of freedom.
Next, either $\\{\langle
P_{F}z_{i},\cdot\rangle|_{F\setminus\\{0\\}}\\}_{i=1}^{m}$ does not have rank
$f$ or there are at most $k$ degrees of freedom for the witness of
intersection $v\in\operatorname{im}(V)\cap\operatorname{im}(\\{\langle
P_{F}z_{i},\cdot\rangle|_{F\setminus\\{0\\}}\\}_{i=1}^{m})$. Then, by a
singular value decomposition argument as in the proof of Lemma 60, the degrees
of freedom of $\\{P_{F}z_{i}\\}_{i=1}^{m}$ are bounded by $mf-1-(m-f-k)$.
Hence, $\dim(A_{1})\leq md-1-(m-f-k)$.

For $A_{2}$, $\\{P_{F}z_{i}\\}_{i=1}^{m}$ has $mf$ degrees of freedom and for
each fixed $\\{P_{F}z_{i}\\}_{i=1}^{m}$, we have $\\{\langle
P_{F}z_{i},\cdot\rangle|_{F\setminus\\{0\\}}\\}_{i=1}^{m}$ has rank at most
$f$, so there exists $W\in\mathbb{R}^{m\times(k+f)}$ such that
$\operatorname{im}(W)=\operatorname{im}(V)+\operatorname{im}(\\{\langle
P_{F}z_{i},\cdot\rangle|_{F\setminus\\{0\\}}\\}_{i=1}^{m})$. Then, by
definition of $v_{k+f}^{m}(G_{F^{\perp}})$, we get

$\displaystyle\dim\\{\\{P_{F}^{\perp}z_{i}\\}_{i=1}^{m}\in(F^{\perp})^{m}:$
$\displaystyle\text{$\Phi_{F^{\perp}}$ fails to strongly avoid
$\operatorname{im}(W)$ }\\}\leq m(d-f)-v_{k+f}^{m}(G_{F^{\perp}}).$

By conservation of dimension, we obtain $\dim(A_{2})\leq md-
v_{k+f}^{m}(G_{F^{\perp}})$. Since $N_{V}^{\\{p_{i}\\}_{i=1}^{m}}\subseteq
A_{1}\cup A_{2}$, it follows that $md-\dim(N_{V}^{\\{p_{i}\\}_{i=1}^{m}})\geq
md-\max\\{\dim(A_{1}),\dim(A_{2})\\}\geq\min\\{m-k-f+1,v_{k+f}^{m}(G_{F^{\perp}})\\}$.
Since $V$ and $\\{p_{i}\\}_{i=1}^{m}$ were arbitrary, the result follows. ∎

##  8 Strong Avoidance for Groups with Finite-Index Stabilizers

######  Definition 68.

Fix a compact subgroup $G\leq\operatorname{O}(d)$. We say $H\leq G$ has finite
index if $G/H$ is a finite set. We say $G$ has a finite-index stabilizer at
$x\in\mathbb{R}^{d}$ if $G_{x}$ has finite index. We say $G$ has finite-index
stabilizers if $G_{x}$ has finite index for every $x\in P(G)^{c}$.

In this section, we investigate the local avoidance behavior at points with
finite-index stabilizers (Lemma 73). More importantly, we solve Problem 18 for
the case where $G$ has finite-index stabilizers:

######  Theorem 69.

Suppose $G\leq\operatorname{O}(d)$ is compact with finite-index stabilizers
and cohomogeniety $c$. Then, $n^{\prime}(G)\leq 2c$.

With Theorem 69 and as in Remark 55, we obtain

######  Corollary 70.

Suppose $G\leq\operatorname{O}(d)$ is compact with finite-index stabilizers
and cohomogeniety $c$. Fix sort indices
$p_{1},\dots,p_{n}\in\\{1,\dots,|\pi_{0}(G)|\\}$. Then, for a fixed or generic
$V\in\mathbb{R}^{n\times k}$ and generic
$z_{1},\ldots,z_{n}\in\mathbb{R}^{d}$, the coorbit filter bank
$\Phi\colon\mathbb{R}^{d}/G\to\mathbb{R}^{n}$ defined by
$\Phi([x]):=\\{\Psi_{p_{i}}([z_{i}],[x])\\}_{i=1}^{n}$ strongly avoids
$\operatorname{im}(V)$ provided $n\geq 2c+k$.

In particular, when $k=0$, the coorbit filter bank is bi-Lipschitz provided
$n\geq 2c$. For the sake of completion, we give a classification for such
class of groups:

######  Theorem 71.

Suppose $G\leq\operatorname{O}(d)$ is compact. Then, $G$ has finite-index
stabilizers if and only if $G$ is a finite group or $G$ acts either freely or
transitively on the sphere in $F_{G}^{\perp}$. In fact, one of the following
cases occurs:

  1. (a)

$G$ is a finite group.

  2. (b)

$G$ act transitively over the sphere in $F_{G}^{\perp}$.

  3. (c)

$G=S^{1}\subseteq\mathbb{C}$ and
$\mathbb{R}^{d}\cong_{\mathbb{R}}\mathbb{C}^{l}\oplus\mathbb{R}^{f}$ such that
for $g=e^{i\theta}\in S^{1}$ and $(c,v)\in\mathbb{C}^{l}\oplus\mathbb{R}^{f}$,
the action is given by $e^{i\theta}(c,v)=(e^{i\theta}c,v)$.

  4. (d)

$G=S^{3}\subseteq\mathbb{H}$ and
$\mathbb{R}^{d}\cong_{\mathbb{R}}\mathbb{H}^{l}\oplus\mathbb{R}^{f}$ such that
for $g=q\in S^{3}$ and $(c,v)\in\mathbb{H}^{l}\oplus\mathbb{R}^{f}$, the
action is given by $q(c,v)=(qc,v)$.

  5. (e)

$G=S^{1}\rtimes_{\varphi}\mathbb{Z}/2\mathbb{Z}$ and
$\mathbb{R}^{d}\cong_{\mathbb{R}}(\mathbb{C}^{2})^{l}\oplus\mathbb{R}^{k}\oplus\mathbb{R}^{f}$
where $\varphi:\mathbb{Z}/2\mathbb{Z}\to\operatorname{Aut}(S^{1})$ is defined
by $\varphi(0)$ being the identity and $\varphi(1)$ being conjugation, such
that for $g=(e^{i\theta},j)\in G$ and
$(\\{(z_{2p-1},z_{2p})\\}_{p=1}^{l},v_{1},v_{2})\in(\mathbb{C}^{2})^{l}\oplus\mathbb{R}^{k}\oplus\mathbb{R}^{f}$,
the action is given by

$(e^{i\theta},j)\cdot(\\{(z_{2p-1},z_{2p})\\}_{p=1}^{l},v_{1},v_{2})=\begin{cases}(\\{(e^{i\theta}z_{2p-1},e^{i\theta}z_{2p})\\}_{p=1}^{l},v_{1},v_{2})&j=0,\\\
(\\{(-e^{i\theta}\overline{z_{2p-1}},e^{i\theta}\overline{z_{2p}})\\}_{p=1}^{l},-v_{1},v_{2})&j=1.\end{cases}$

###### Proof.

The proof is technical and is postponed to Appendix C. ∎

While the class of groups with finite-index stabilizers is limited, we hope
that the induction method we follow in this section informs future
developments towards strong avoidance and/or bilipschitz properties for
coorbit filter banks.

The rest of this section is dedicated to proving Theorem 69. For $H\leq G$,
denote $\operatorname{Fix}(H):=\\{x\in\mathbb{R}^{d}:H=G_{x}\\}$. Then, by
Section 7.4 in [27], $\operatorname{Fix}(H)$ is open in the linear space
$\overline{\operatorname{Fix}(H)}=\\{x\in\mathbb{R}^{d}:H\subseteq G_{x}\\}$.
We need the following corollary of classification

######  Corollary 72.

Suppose $G\leq\operatorname{O}(d)$ is compact with finite-index stabilizers.
Then, every nonprincipal stabilizers contains the entire principal conjugacy
class $(G_{P})$ of $G$.

###### Proof.

By Theorem 71, $G$ has finite-index stabilizers if and only if either (1) $G$
is a finite group or (2) $G$ acts freely on the sphere in $F_{G}^{\perp}$ or
(3) $G$ acts transitively on the sphere in $F_{G}^{\perp}$. In the first case,
there are finitely many proper $1$-eigenspaces for the finitely many
nonidentity elements of $G$ so the principal isotropy group is trivial. In the
second case and due to freeness, $G$ also has trivial principal isotropy
group. In the third case and due to transitivity, the only nonprincipal
stabilizer is $G$ itself. The result follows. ∎

We also need the following lemma:

######  Lemma 73.

Suppose $G\leq\operatorname{O}(d)$ is compact with cohomogeniety $c$ and
identity component $G_{0}$. Suppose $x\in P(G)^{c}$ and $G_{x}$ has finite
index. Set $F:=\operatorname{Fix}(G_{x})$. For
$p_{1},\dots,p_{n}\in\\{1,\dots,|\pi_{0}(G)|\\}$ and
$z_{1},\ldots,z_{n}\in\mathbb{R}^{d}$, denote by
$\Phi\colon\mathbb{R}^{d}/G\to\mathbb{R}^{n}$ the coorbit filter bank defined
by $\Phi([x]):=\\{\Psi_{p_{i}}([z_{i}],[x])\\}_{i=1}^{n}$. Then, for
$V\in\mathbb{R}^{n\times k}$, consider the failure set

$D_{V}:=\big{\\{}\\{z_{i}\\}_{i=1}^{n}\in(\mathbb{R}^{d})^{n}:\Phi\text{ fails
to locally avoid }\operatorname{im}(V)\text{ at every
}x\in\operatorname{Fix}(G_{x})\big{\\}}.$

Then, $D_{V}$ is semialgebraic and

$\dim(D_{V})\leq nd-1-(n-k-2\dim(F)+n^{\prime}(G_{x}|_{F^{\perp}})).$

###### Proof.

Fix $V\in\mathbb{R}^{n\times k}$. Semialgebraicity follows from $D_{V}$ being
a projection of the $V$ section of the semialgebraic set $D$ defined in Lemma
15. Set $F:=\operatorname{Fix}(G_{x})$ and $f:=\dim(\overline{F})$. By a
lifting technique as in the proofs of Lemmas 60 and 54, we fix a witness of
failure $x\in F\cap\mathbb{S}^{d-1}$. We note that the space of such witnesses
has dimension at most $f-1$. Then, by conservation of dimension, it suffices
to show that $\dim(D_{V}^{x})\leq nd-(n-k-f+n^{\prime}(G_{x}|_{F^{\perp}}))$
where

$D_{V}^{x}:=\big{\\{}\\{z_{i}\\}_{i=1}^{n}\in(\mathbb{R}^{d})^{n}:\Phi\text{
fails to locally avoid }\operatorname{im}(V)\text{ at }x\big{\\}}.$

By a similar argument as in the proof of Lemma 60, we may assume that there
exists $m\in\\{0,\dots,n\\}$ such that after modifying $D_{V}^{x}$, we have

$\begin{cases}\\{z_{i}\\}_{i=m+1}^{n}\in\prod_{i=m+1}^{n}(Q_{x}^{p_{i}})^{c},\\\
\\{z_{i}\\}_{i=1}^{m}\in\big{\\{}\\{z_{i}\\}_{i=1}^{m}\in\prod_{i=1}^{m}Q_{x}^{p_{i}}:\Phi_{m}\text{
fails to locally avoid }\operatorname{im}(V_{m})\text{ at
}x\big{\\}}\end{cases}$

for $\\{z_{i}\\}_{i=1}^{n}\in D_{V}^{x}$. Here, $V_{m}$ denotes a truncation
of $V$ to its first $m$ rows and $\Phi_{m}$ denotes the coorbit filter bank
corresponding to templates $\\{z_{i}\\}_{i=1}^{m}$ and sort indices
$\\{p_{i}\\}_{i=1}^{m}$. Since $G_{x}$ has finite index, we have that $[x]$ is
finite and so with $l:=\operatorname{size}([x])$, there exists
$h_{1},\dots,h_{l}$ such that $[x]=\\{h_{j}x\\}_{j=1}^{l}$ and
$Q_{x}^{p_{i}}=\sqcup_{1\leq j\leq l}(h_{j}\cdot V_{x}^{p_{i}})$. For each
$z_{i}\in Q_{x}^{p_{i}}$, there exists $h_{i}\in\\{h_{j}\\}_{j=1}^{l}$ such
that $h_{i}z_{i}\in V_{x}^{p_{i}}$. By taking a finite union over the
possibilities of $h_{i}$ and since there are at most $(n-m)(d-1)$ degrees of
freedom contributed by $\\{z_{i}\\}_{i=m+1}^{n}$, it suffices to show that
$\dim(D_{V_{m}}^{x})\leq md-(m-k-f+n^{\prime}(G_{x}|_{F^{\perp}}))$ where

$D_{V_{m}}^{x}:=\big{\\{}\\{z_{i}\\}_{i=1}^{m}\in\prod_{i=1}^{m}V_{x}^{p_{i}}:\Phi_{m}\text{
fails to locally avoid }\operatorname{im}(V_{m})\text{ at }x\big{\\}}.$

Fix arbitrary $\\{z_{i}\\}_{i=1}^{m}\in D_{V_{m}}^{x}$ and let $Q_{m}$ denote
the difference quotient correspoding to $\Phi_{m}$. By definition of
$D_{V_{m}}^{x}$, there exists sequences $x_{j},y_{j}\to x$ such that
$[x_{j}]\neq[y_{j}]$, $d([x_{j}],[y_{j}])=\|x_{j}-y_{j}\|$, and
$\lim_{n\to\infty}Q_{m}(x_{j},y_{j})\in\operatorname{im}(V_{m})$. By 34(b) and
for large enough $j$, we have
$\Psi_{p_{i}}([z_{i}],[x_{j}])=\Psi_{p_{i}^{\prime}}^{G_{x}}([z_{i}]_{G_{x}},[x_{j}]_{G_{x}})$
and
$\Psi_{p_{i}}([z_{i}],[y_{j}])=\Psi_{p_{i}^{\prime}}^{G_{x}}([z_{i}]_{G_{x}},[y_{j}]_{G_{x}})$
where $p_{i}^{\prime}=p_{i}+1\mod|\pi_{0}(G_{x})|+1$. Then, since
$d([x_{j}],[y_{j}])=\|x_{j}-y_{j}\|=d_{G_{x}}([x_{j}]_{G_{x}},[y_{j}]_{G_{x}})$,
the following holds for every $i\in\\{1,\dots,m\\}$

$\frac{\Psi_{p_{i}}([z_{i}],[x_{j}])-\Psi_{p_{i}}([z_{i}],[y_{j}])}{d([x_{j}],[y_{j}])}=\frac{\Psi_{p_{i}^{\prime}}^{G_{x}}([z_{i}]_{G_{x}},[x_{j}]_{G_{x}})-\Psi_{p_{i}^{\prime}}^{G_{x}}([z_{i}]_{G_{x}},[y_{j}]_{G_{x}})}{d_{G_{x}}([x_{j}]_{G_{x}},[y_{j}]_{G_{x}})}.$

We obtain that $D_{V_{m}}^{x}$ is a subset of
$\\{\\{z_{i}\\}_{i=1}^{m}\in(\mathbb{R}^{d})^{m}:\Phi^{G_{x}}_{m}\text{ fails
to strongly avoid }\operatorname{im}(V_{m})\\}$. By Theorem 65 and the
definitions of $v_{k}^{m}(G)$ and $n^{\prime}(G_{x})$, it follows that

$\dim(D_{V_{m}}^{x})\leq md-v_{k}^{m}(G)<md-(m-k-n^{\prime}(G_{x}))\leq
md-(m-k-f-n^{\prime}(G_{x}|_{F^{\perp}})),$

as desired. ∎

###### Proof of Theorem 69.

Fix $n\in\mathbb{N}$, $k\in\mathbb{Z}_{\geq 0}$ and
$p_{1},\dots,p_{n}\in\\{1,\dots,|\pi_{0}(G)|\\}$. Fix
$z_{1},\ldots,z_{n}\in\mathbb{R}^{d}$ and consider the coorbit filter bank
$\Phi\colon\mathbb{R}^{d}/G\to\mathbb{R}^{n}$ defined by
$\Phi([x]):=\\{\Psi_{p_{i}}([z_{i}],[x])\\}_{i=1}^{n}$. We argue by induction
on $d$. First, the case $d=1$ is trivial since all nonzero points are
principal so the result follows from Lemmas 54 and 60. Assume that for
dimensions $l\in\\{1,\dots,d-1\\}$, every compact $G\leq\operatorname{O}(l)$
with finite-index stabilizers satisfies $n^{\prime}(G)\leq 2c$. Fix
$V\in\mathbb{R}^{n\times k}$, let $x\in P(G)^{c}$ and denote
$F:=\overline{\operatorname{Fix}(G_{x})}$.

Let $c_{F^{\perp}}^{G_{x}}$ be the cohomogeneity of
$G_{x}|_{F^{\perp}}\leq\operatorname{O}(F^{\perp})$. We claim that
$G_{x}|_{F^{\perp}}$ has finite-index statbilizers and
$c_{F^{\perp}}^{G_{x}}=c-f$. By Corollary 72, $G_{x}$ contains all of
$(G_{P})$. The stabilizer in $G_{x}$ of $y\in F^{\perp}$, given by $G_{y}\cap
G_{x}$, is either in $(G_{P})$ or has finite index. As such, $G_{x}$ has
finite-index stabilizers and the dimension of a $G_{x}$-principal orbit in
$F^{\perp}$ is given by
$(d-f)-c_{F^{\perp}}^{G_{x}}=\dim(G_{0})-\dim(G_{p})=d-c$ where $p\in P(G)$.
We get that $c_{F^{\perp}}^{G_{x}}=c-f$ and the claim follows.

Hence, by induction $n^{\prime}(G_{x}|_{F_{x}}^{\perp})\leq 2c-2f$. By Lemma
73, we get $\dim(D_{V}^{G_{x}})\leq nd-1-(n-k-2c)$ where

$D_{V}^{G_{x}}:=\big{\\{}\\{z_{i}\\}_{i=1}^{n}\in(\mathbb{R}^{d})^{n}:\Phi\text{
fails to locally avoid }\operatorname{im}(V)\text{ at every
}x\in\operatorname{Fix}(G_{x})\big{\\}}.$

Since $G$ has finite-index stabilizers, the set $S:=\\{H\leq G:\exists x\in
P(G)^{c},H=G_{x}\\}$ is finite. Hence, by taking a finite union of
$D_{V}^{G_{x}}$ over $S$ and by combining that with the bounds in Lemmas 54
and 60, we obtain $n^{\prime}(G)\leq 2c$ as desired. ∎

##  9 The Component Voronoi Characteristic and Connected Reduction

In this section, we mimic and generalize the Voronoi characteristic
developments in Section 3 of [29]. The main goal is to find quantities
$\chi^{\\{p_{i}\\}_{i=1}^{n}}_{\pi_{0}}(G)\leq\chi^{T}_{\pi_{0}}(G)\leq|\pi_{0}(G)|$
(Definition 83) with which we are able to reduce the problem of strong
avoidance to the identity component of the group. When fixed sort indices are
considered, we obtain the following reduction:

######  Theorem 74.

Fix a compact group $G\leq\operatorname{O}(d)$ and sort indices
$p_{1},\dots,p_{n}\in\\{1,\dots,\pi_{0}(G)\\}$. Fix $V\in\mathbb{R}^{n\times
k}$. Then, for any generic templates $z_{1},\ldots,z_{n}\in\mathbb{R}^{d}$,
the corresponding coorbit filter bank $\Phi$ strongly avoids
$\operatorname{im}(V)$ provided
$n>\chi_{\pi_{0}}^{\\{p_{i}\\}_{i=1}^{n}}(G)\cdot(n_{k}(G_{0})-1)$.

With all sort indices considered, we obtain the following result:

######  Theorem 75.

Fix a compact group $G\leq\operatorname{O}(d)$. Then, $v_{k}^{n}(G)\geq
v_{k}^{\lceil n/\chi_{\pi_{0}}^{T}(G)\rceil}(G_{0})$ and
$n_{k}(G)\leq\chi_{\pi_{0}}^{T}(G)(n_{k}(G_{0})-1)+1$.

The rest of this section aims to set up all the tools necessary to the end of
proving Theorems 74 and 75.

######  Definition 76.

Fix a compact group $G\leq\operatorname{O}(d)$ and a sort index
$i\in\\{1,\dots,|\pi_{0}(G)|\\}$. For each $x,y\in\mathbb{R}^{d}$, we define

$S^{i}([x]_{0},[y]_{0}):=\big{\\{}[q]_{0}\in\pi_{0}([y]):V_{[q]_{0}}^{i}\cap
V_{[x]_{0}}^{i}\neq\varnothing\big{\\}}.$

In words, the components of $[x]$ and $[y]$ decompose $\mathbb{R}^{d}$ into
component Voronoi cells in different ways, and $S^{i}([x]_{0},[y]_{0})$
captures which closures of component Voronoi cells corresponding to $[y]_{0}$
are needed to cover $\overline{V_{[x]_{0}}^{i}}$. This is captured in part (b)
of the following lemma:

######  Lemma 77.

Fix compact $G\leq\operatorname{O}(d)$, sort index
$i\in\\{1,\dots,|\pi_{0}(G)|\\}$, $x,y\in\mathbb{R}^{d}$, and
$T\subseteq\pi_{0}([y])$. Consider the statements:

  * (a)

$T\supseteq S^{i}([x]_{0},[y]_{0})$.

  * (b)

$\bigcup_{[p]_{0}\in
T}\overline{V_{[p]_{0}}^{i}}\supseteq\overline{V_{[x]_{0}}^{i}}$.

  * (c)

For every $z\in\mathbb{R}^{d}$, there exists $[v]_{0}\in\pi_{0}([z])$ such
that $\Psi_{i}([z],[x])=\mathcal{C}([v]_{0},[x]_{0},G_{0})$ and

$T\cap\big{\\{}[p]_{0}\in\pi_{0}([y]):\Psi_{i}([z],[y])=\mathcal{C}([v]_{0},[p]_{0},G_{0})\big{\\}}\neq\varnothing.$

Then (a) $\Leftrightarrow$ (b) $\Rightarrow$ (c), and furthermore, (c)
$\Rightarrow$ (b) holds if $i=1$ and $x\in P_{\pi_{0}}(G)$.

###### Proof.

(a)$\Rightarrow$(b). Select $q\in\pi_{0}([y])\setminus T$. Since
$S^{i}([x]_{0},[y]_{0})\subseteq T$, it follows that $V_{[q]_{0}}^{i}\cap
V_{[x]_{0}}^{i}=\varnothing$. Thus, $(V_{[x]_{0}}^{i})^{c}\supseteq
V_{[q]_{0}}^{i}$, and since $(V_{[x]_{0}}^{i})^{c}$ is closed (38(d)), we get
$(V_{[x]_{0}}^{i})^{c}\supseteq\overline{V_{[q]_{0}}^{i}}$, meaning
$\overline{V_{[q]_{0}}^{i}}\cap V_{[x]_{0}}^{i}=\varnothing$. As such,

$V_{[x]_{0}}^{i}\subseteq\mathbb{R}^{d}\setminus\bigg{(}\bigcup_{[q]_{0}\in\pi_{0}([y])\setminus
T}\overline{V_{[q]_{0}}^{i}}\bigg{)}\subseteq\bigcup_{[p]_{0}\in
T}\overline{V_{[p]_{0}}^{i}}.$

The result now follows from the fact that the right-hand side is closed.

(b)$\Rightarrow$(a). Select $[q]_{0}\in\pi_{0}([y])\setminus T$. Then our
assumption on $T$ implies

$V_{[x]_{0}}^{i}\subseteq\overline{V_{[x]_{0}}^{i}}\subseteq\bigcup_{[p]_{0}\in
T}\overline{V_{[p]_{0}}^{i}}\subseteq\bigcup_{[p]_{0}\in\pi_{0}([y])\setminus\\{[q]_{0}\\}}\overline{V_{[p]_{0}}^{i}}\subseteq(V_{[q]_{0}}^{i})^{c}.$

As such, $V_{[q]_{0}}^{i}\cap V_{[x]_{0}}^{i}=\varnothing$, and so
$[q]_{0}\not\in S^{i}([x]_{0},[y]_{0})$.

(b)$\Rightarrow$(c). By Lemma 38, take $[v]_{0}\in\pi_{0}([z])$ such that
$\Psi_{i}([z],[x])=\mathcal{C}([v]_{0},[x]_{0},G_{0})$ and
$v\in\overline{V_{[x]_{0}}^{i}}$. By assumption, there exists $[w]_{0}\in T$
such that $v\in\overline{V_{[w]_{0}}^{i}}$ so that by Lemma 38,
$[w]_{0}\in\\{[p]_{0}\in\pi_{0}([y]):\Psi_{i}([z],[y])=\mathcal{C}([v]_{0},[p]_{0},G_{0})\big{\\}}$.
Then, $[w]_{0}$ witnesses the desired nonemptiness.

(c)$\Rightarrow$(b). Suppose $x\in P_{\pi_{0}}(G)$ and $[z]_{0}\in
V_{[x]_{0}}^{1}$. Then, Lemma 39 gives that $[x]_{0}\in V_{[z]_{0}}^{1}$. By
definition, it follows that
$\\{[z]_{0}\\}=\arg\max_{[p]_{0}\in\pi_{0}([z])}\langle\langle[x]_{0},[p]_{0}\rangle\rangle_{G_{0}}$.
By assumption, there exists $[v]_{0}\in\\{[z]_{0}\\}$ such that
$T\cap\arg\max_{[q]_{0}\in\pi_{0}([y])}\langle\langle[q]_{0},[v]_{0}\rangle\rangle_{G_{0}}\neq\varnothing$.
That is, by Lemma 38, there exists $[p]_{0}\in T$ such that
$[z]_{0}\in\overline{V_{[p]_{0}}^{1}}$. This shows that
$V_{[x]_{0}}^{1}\subseteq\bigcup_{p\in T}\overline{V_{[p]_{0}}^{1}}$, and so
we are done by taking closures. ∎

######  Definition 78.

Define the auxiliary set
$\mathcal{O}_{\pi_{0}}(\\{(z_{i},p_{i})\\}_{i=1}^{n},G):=P_{\pi_{0}}(G)\cap\bigcap_{i=1}^{n}Q_{[z_{i}]_{0}}^{p_{i}}$.

In the following corollary, (a) follows from Corollary 41 while part (b)
follows from Lemma 77.

######  Corollary 79.

Fix compact $G\leq\operatorname{O}(d)$, $z_{1},\ldots,z_{n}\in\mathbb{R}^{d}$,
$p_{1},\ldots,p_{n}\in\\{1,\dots,|\pi_{0}(G)|\\}$,
$x\in\mathcal{O}(\\{(z_{i},p_{i})\\}_{i=1}^{n},G)$, and $y\in\mathbb{R}^{d}$.

  * (a)

For every $i\in\\{1,\ldots,n\\}$, the set
$\big{\\{}[p]_{0}\in\pi_{0}([z_{i}]_{0}):\Psi_{p_{i}}([z],[x])=\mathcal{C}([p]_{0},[x]_{0},G_{0})\big{\\}}$
consists of a single element $v_{i}([x]_{0})$.

  * (b)

There is a nonempty set $\mathcal{F}([x]_{0},[y]_{0})$ of choice functions
$f\colon\\{1,\ldots,n\\}\to\pi_{0}([y])$ such that

$f(i)\in
S^{p_{i}}([x]_{0},[y]_{0})\cap\big{\\{}[p]_{0}\in\pi_{0}([y]):\Psi_{p_{i}}([z],[y])=\mathcal{C}([v_{i}(x)]_{0},[p]_{0},G_{0})\big{\\}}\neq\varnothing$

In words, $[z_{i}]_{0}$ is realized as $v_{i}([x]_{0})$ with respect to
$[x]_{0}$ while $[y]_{0}$ is realized as $f(i)\in S^{p_{i}}([x]_{0},[y]_{0})$
with respect to $v_{i}([x]_{0})$. The importance of what we have introduced
thus far will shine once we show how it interacts with the following
quantitative interpretation of strong avoidance:

######  Definition 80.

Given compact $G\leq\operatorname{O}(d)$, $V\in\mathbb{R}^{n\times k}$,
$\\{z_{i}\\}_{i=1}^{n}\in\mathbb{(}\mathbb{R}^{d})^{n}$ and
$p_{1},\ldots,p_{n}\in\\{1,\dots,|\pi_{0}(G)|\\}$, the optimal strong
avoidance bound for the corresponding coorbit filter bank $\Phi$ is denoted by

$\sigma_{\min{}}^{G}(\\{(z_{i},p_{i})\\}_{i=1}^{n},V):=\inf_{\begin{subarray}{c}[x],[y]\in\mathbb{R}^{d}/G\\\
{[x]\neq[y]}\end{subarray}}d\bigg{(}\frac{\Phi([x])-\Phi([y])}{d_{G}([x],[y])},\operatorname{im}(V)\bigg{)}.$

When $p_{i}\equiv 1$, we shorten the notation to
$\sigma_{\min{}}^{G}(\\{z_{i}\\}_{i=1}^{n},V)$. When $n=0$, we take
$\sigma_{\min{}}^{G}(\varnothing,V):=0$. Moreover, for
$V\in\mathbb{R}^{n\times k}$ and $I\subseteq[n]$, we denote by
$V_{I}\in\mathbb{R}^{|I|\times k}$ the truncation of $V$ which keeps the rows
corresponding to indices in $I$.

######  Remark 81.

$\Phi$ strongly avoids $\operatorname{im}(V)$ if and only if
$\sigma_{min}^{G}(\\{(z_{i},p_{i})\\}_{i=1}^{n},V)>0$.

The following theorem shows how we can leverage all that we have introduced
thus far to reduce a coorbit filter bank with a nonconnected groups into a max
filter bank with the identity component of said group, by passing through the
buckets supplied by $S^{\\{p_{i}\\}_{i=1}^{n}}([x]_{0},[y]_{0})$ defined
below:

######  Theorem 82.

Given compact $G\leq\operatorname{O}(d)$, $V\in\mathbb{R}^{n\times k}$,
$z_{1},\ldots,z_{n}\in\mathbb{R}^{d}$ and
$p_{1},\ldots,p_{n}\in\\{1,\dots,|\pi_{0}(G)|\\}$, put

$S^{\\{p_{i}\\}_{i=1}^{n}}([x]_{0},[y]_{0}):=\cup_{i=1}^{n}S^{p_{i}}([x]_{0},[y]_{0})$

and put

$\alpha(\\{(z_{i},p_{i})\\}_{i=1}^{n},V,G):=\inf_{x,y\in\mathcal{O}(\\{(z_{i},p_{i})\\}_{i=1}^{n},G)}\max_{f\in\mathcal{F}(x,y)}\bigg{(}\sum_{w\in
S^{\\{p_{i}\\}_{i=1}^{n}}([x]_{0},[y]_{0})}\sigma_{\min{}}^{G_{0}}\big{(}\\{v_{i}(x)\\}_{i\in
f^{-1}(w)},V_{f^{-1}(w)}\big{)}^{2}\bigg{)}^{1/2},$

where $v_{i}(x)$ and $\mathcal{F}(x,y)$ are defined as in Corollary 79. The
coorbit filter bank $\Phi\colon\mathbb{R}^{d}/G\to\mathbb{R}^{n}$ defined by
$\Phi([x]):=\\{\Psi_{p_{i}}([z_{i}],[x])\\}_{i=1}^{n}$ satisfies

$\sigma_{\min{}}^{G}(\\{(z_{i},p_{i})\\}_{i=1}^{n},V)\geq\alpha(\\{(z_{i},p_{i})\\}_{i=1}^{n},V,G).$

###### Proof.

It suffices to prove

$\left\|\frac{\Phi([x])-\Phi([y])}{d([x],[y])}-v\right\|\geq\alpha(\\{(z_{i},p_{i})\\}_{i=1}^{n},V,G)$

for all $v\in\operatorname{im}(V)$ and
$x,y\in\mathcal{O}(\\{(z_{i},p_{i})\\}_{i=1}^{n},G)$ with $[x]\neq[y]$; this
follows from the continuity of the left-hand side and the density of
$\mathcal{O}(\\{(z_{i},p_{i})\\}_{i=1}^{n},G)$ in $\mathbb{R}^{d}$. As such,
we fix $v\in\operatorname{im}(V)$ and
$x,y\in\mathcal{O}(\\{(z_{i},p_{i})\\}_{i=1}^{n},G)$ with $[x]\neq[y]$, and we
select $f\in\mathcal{F}(x,y)$ that maximizes

$\sum_{[w]_{0}\in
S^{\\{p_{i}\\}_{i=1}^{n}}([x]_{0},[y]_{0})}\sigma_{\min{}}^{G_{0}}\big{(}\\{v_{i}(x)\\}_{i\in
f^{-1}(w)},V_{f^{-1}(w)}\big{)}^{2}.$

By Corollary 79, we have $\Psi_{p_{i}}([z_{i}],[x])=\langle\langle
v_{i}([x]_{0}),[x]_{0}\rangle\rangle_{G_{0}}$ and
$\Psi_{p_{i}}([z_{i}],[y])=\langle\langle
v_{i}([x]_{0}),f(i)\rangle\rangle_{G_{0}}$, and so

$\displaystyle\|\Phi([x])-\Phi([y])-d([x],[y])v\|^{2}$
$\displaystyle=\sum_{i=1}^{n}\big{(}\langle\langle
v_{i}([x]_{0}),[x]_{0}\rangle\rangle_{G_{0}}-\langle\langle
v_{i}([x]_{0}),f(i)\rangle\rangle_{G_{0}}-d([x],[y])v_{i}\big{)}^{2}$
$\displaystyle=\sum_{[w]_{0}\in
S^{\\{p_{i}\\}_{i=1}^{n}}([x]_{0},[y]_{0})}\sum_{i\in
f^{-1}(w)}\big{(}\langle\langle
v_{i}([x]_{0}),[x]_{0}\rangle\rangle_{G_{0}}-\langle\langle
v_{i}([x]_{0}),[w]_{0}\rangle\rangle_{G_{0}}-d([x],[y])v_{i}\big{)}^{2}$
$\displaystyle=\sum_{[w]_{0}\in
S^{\\{p_{i}\\}_{i=1}^{n}}([x]_{0},[y]_{0})}\sum_{i\in
f^{-1}(w)}\bigg{(}\frac{\langle\langle
v_{i}([x]_{0}),[x]_{0}\rangle\rangle_{G_{0}}-\langle\langle
v_{i}([x]_{0}),[w]_{0}\rangle\rangle_{G_{0}}}{d_{G_{0}}([x]_{0},[w]_{0})}-\frac{d([x],[y])}{d_{G_{0}}([x]_{0},[w]_{0})}v_{i}\bigg{)}^{2}\cdot
d_{G_{0}}([x]_{0},[w]_{0})^{2}$ $\displaystyle\geq\sum_{[w]_{0}\in
S^{\\{p_{i}\\}_{i=1}^{n}}([x]_{0},[y]_{0})}\sigma_{\min{}}^{G_{0}}\big{(}\\{v_{i}(x)\\}_{i\in
f^{-1}(w)},V_{f^{-1}(w)}\big{)}^{2}\cdot d_{G_{0}}([x]_{0},[w]_{0})^{2}$
$\displaystyle\geq\alpha(\\{(z_{i},p_{i})\\}_{i=1}^{n},V,G)^{2}\cdot
d([x],[y])^{2},$

as desired. ∎

Next, we pass through the worst-case scenario

######  Definition 83.

Suppose $G\leq\operatorname{O}(d)$ is compact and let
$p_{1},\dots,p_{n}\in\\{1,\dots,|\pi_{0}(G)|\\}$. The component Voronoi
characteristic of $G$ corresponding to $\\{p_{i}\\}_{i=1}^{n}$ is given by

$\chi_{\pi_{0}}^{\\{p_{i}\\}_{i=1}^{n}}(G):=\max_{x,y\in
P_{\pi_{0}}(G)}|S^{\\{p_{i}\\}_{i=1}^{n}}([x]_{0},[y]_{0})|,$

where $P_{\pi_{0}}(G)$ and $S^{i}([x]_{0},[y]_{0})$ are defined in Definitions
24 and 76. The total Voronoi characteristic is defined by

$\chi_{\pi_{0}}^{T}(G):=\chi_{\pi_{0}}^{\\{i\\}_{i=1}^{|\pi_{0}(G)|}}(G).$

In addition, given $V\in\mathbb{R}^{n\times k}$,
$z_{1},\ldots,z_{n}\in\mathbb{R}^{d}$ and
$p_{1},\dots,p_{n}\in\\{1,\dots,|\pi_{0}(G)|\\}$, we define

$\tilde{\alpha}(\\{(z_{i},p_{i})\\}_{i=1}^{n},V,G):=\min_{\begin{subarray}{c}I\subseteq\\{1,\ldots,n\\}\\\
|I|\geq
n/\chi_{\pi_{0}}^{\\{p_{i}\\}_{i=1}^{n}}(G)\end{subarray}}\min_{\\{K_{i}\\}_{i\in
I}\in(\pi_{0}(G))^{I}}\sigma_{\min{}}^{G_{0}}\big{(}\\{K_{i}z_{i}\\}_{i\in
I},V_{I}\big{)}.$

######  Remark 84.

$\chi_{\pi_{0}}^{\\{p_{i}\\}_{i=1}^{n}}(G)\leq\chi_{\pi_{0}}^{T}(G)\leq|\pi_{0}(G)|$
and by the pigeonhole principle,
$\tilde{\alpha}(\\{(z_{i},p_{i})\\}_{i=1}^{n},V,G)\leq\alpha(\\{(z_{i},p_{i})\\}_{i=1}^{n},V,G)$.

###### Proof of Theorems 75 and 74.

Fix sort indices $p_{1},\dots,p_{n}\in\\{1,\dots,|\pi_{0}(G)|\\}$. For
$z_{1},\ldots,z_{m}\in\mathbb{R}^{d}$, let $\Phi$ denote the corresponding
coorbit filter bank, and let
$\Phi_{0}\colon\mathbb{R}^{d}/G_{0}\to\mathbb{R}^{m}$ denote the max filter
bank defined by
$\Phi_{0}([x]_{0}):=\\{\langle\langle[z_{i}]_{0},[x]_{0}\rangle\rangle_{G_{0}}\\}_{i=1}^{m}$.
Fix $V\in\mathbb{R}^{n\times k}$. Consider the semialgebraic sets

$M_{V}:=\\{\\{z_{i}\\}_{i=1}^{m}\in(\mathbb{R}^{d})^{m}:\Phi_{0}\text{ fails
to strongly avoid }\operatorname{im}(V)\\}$

and

$N_{V}:=\\{\\{z_{i}\\}_{i=1}^{n}\in(\mathbb{R}^{d})^{n}:\Phi\text{ fails to
strongly avoid }\operatorname{im}(V)\\}.$

It suffices to show that for $n\in\mathbb{N}$,

$nd-\dim(N_{V})\geq\min_{\begin{subarray}{c}I\subseteq\\{1,\ldots,n\\}\\\
|I|\geq
n/\chi_{\pi_{0}}^{\\{p_{i}\\}_{i=1}^{n}}(G)\end{subarray}}|I|d-\dim(M_{V_{I}})\geq\min_{\begin{subarray}{c}I\subseteq\\{1,\ldots,n\\}\\\
|I|\geq n/\chi_{\pi_{0}}^{T}(G)\end{subarray}}|I|d-\dim(M_{V_{I}}).$

Fix arbitrary $\\{z_{i}\\}_{i=1}^{n}\in(\mathbb{R}^{d})^{n}$. Let
$I\subseteq[n]$ and $\\{K_{i}\\}_{i\in I}\in(\pi_{0}(G))^{I}$ be such that
$|I|\geq n/\chi_{\pi_{0}}^{\\{p_{i}\\}_{i=1}^{n}}(G)$ and
$\tilde{\alpha}(\\{(z_{i},p_{i})\\}_{i=1}^{n},V,G)=\sigma_{\min{}}^{G_{0}}(\\{K_{i}z_{i}\\}_{i\in
I},V_{I})$. Then, by Theorems 82 and 84, we get

$\sigma_{\min{}}^{G}(\\{(z_{i},p_{i})\\}_{i=1}^{n},V)\geq\alpha(\\{(z_{i},p_{i})\\}_{i=1}^{n},V,G)\geq\tilde{\alpha}(\\{(z_{i},p_{i})\\}_{i=1}^{n},V,G)=\sigma_{\min{}}^{G_{0}}(\\{K_{i}z_{i}\\}_{i\in
I},V_{I}).$

As such, if $\\{z_{i}\\}_{i=1}^{n}\in N_{V}$, then $\\{K_{i}z_{i}\\}_{i\in
I}\in M_{V_{I}}$ and so $\\{z_{i}\\}_{i\in I}\in(K_{i}^{-1})_{i\in I}\cdot
M_{V_{I}}$. It follows that

$N_{V}\subseteq\bigcup_{\begin{subarray}{c}I\subseteq\\{1,\ldots,n\\}\\\
|I|\geq
n/\chi_{\pi_{0}}^{\\{p_{i}\\}_{i=1}^{n}}(G)\end{subarray}}\bigcup_{\\{K_{i}\\}_{i\in
I}\in(\pi_{0}(G))^{I}}\Big{\\{}\\{z_{i}\\}_{i=1}^{n}\in(\mathbb{R}^{d})^{n}:\\{z_{i}\\}_{i\in
I}\in\\{K_{i}^{-1}\\}_{i\in I}\cdot M_{V_{I}}\Big{\\}}.$

The union is finite and so we bound $\dim(\\{K_{i}^{-1}\\}_{i\in I}\cdot
M_{V_{I}})$ for fixed $I$ and $\\{K_{i}\\}_{i\in I}$. By $G_{0}$-invariance of
$M_{V_{I}}$ and for any $k_{i}\in G$ such that $G_{0}k_{i}=K_{i}$, we have
$\dim(\\{K_{i}^{-1}\\}_{i\in I}\cdot M_{V_{I}})=\dim((k_{i}^{-1})_{i\in
I}\cdot M_{V_{I}})=\dim(M_{V_{I}})$ where the last step follows since the left
action of $(k_{i}^{-1})_{i\in I}$ is an isometry of $\mathbb{(}R^{d})^{I}$.
Then, $\dim(N_{V})\leq(n-|I|)d+\dim(M_{V_{I}})$ and so

$\dim(N_{V})\leq\max_{\begin{subarray}{c}I\subseteq\\{1,\ldots,n\\}\\\ |I|\geq
n/\chi_{\pi_{0}}^{T}(G)\end{subarray}}(n-|I|)d+\dim(M_{V_{I}}).$

The result now follows by rearrangment. ∎

######  Remark 85.

The action of $G$ on $\mathbb{R}^{d}$ induces an action of $\pi_{0}(G)$ on
$\mathbb{R}^{d}/G$ given by metric space isometries. We label the orbit of
$[x]_{0}\in\mathbb{R}^{d}/G$ under $\pi_{0}(G)$ by $\pi_{0}([x])$. The Voronoi
decomposition $V^{i}_{[x]_{0}}$ in $\mathbb{R}^{d}$ descends into a Voronoi
decomposition of $\mathbb{R}^{d}/G_{0}$ compatible with the action of
$\pi_{0}(G)$ where the coorbit map is thought of through sorting quotient
distances in ascending top-to-bottom order i.e. smallest goes first.

##  10 Minimal Reduction for Generic Max Filtering Avoidance

In this section, we show that the problem of strong avoidance for max
filtering with a group $G$ is equivalent to the same problem when $G$ is
replaced by its minimal reduction:

######  Proposition 86 (Section 1.2 in [19]).

Suppose $G\leq\operatorname{O}(d)$ is compact. Then, there exists $H\leq O(p)$
such that $H$ has trivial principal isotropy and $\mathbb{R}^{d}/G$ is
isometric to $\mathbb{R}^{p}/H$.

######  Definition 87.

When $H$ has minimal dimension in Proposition 86, we call $H$ a minimal
reduction of $G$.

The main results are stated in the following lemma and corollary. The
following lemma shows that max filtering is an orbit space isometry invariant

######  Lemma 88.

For $j\in\\{1,2\\}$, suppose $G_{j}\leq\operatorname{O}(d_{j})$ are compact.
Suppose there exists an isometry
$\psi\colon\mathbb{R}^{d_{1}}/G_{1}\to\mathbb{R}^{d_{2}}/G_{2}$. Let $n\geq
1$, $k\geq 0$ and fix $V\in\mathbb{R}^{n\times k}$. For
$[z_{1}],\dots,[z_{n}]\in\mathbb{R}^{d_{j}}/G_{j}$ and $G$-invariant
semialgebraic sets $Y_{j}$, consider the following statements:

  * •

$P_{j}([Y_{j}],\\{[z_{i}]\\}_{i=1}^{n})$: The max filter bank
$\Phi_{G_{j}}\colon\mathbb{R}^{d_{j}}/G\to\mathbb{R}^{n}$ defined by
$\Phi_{G_{j}}([x]):=\\{\langle\langle[x],[z_{i}]\rangle\rangle_{G_{j}}\\}_{i=1}^{n}$
locally avoids $\operatorname{im}(V)$ at every $[y]\in[Y_{j}]$.

  * •

$W_{j}(\\{[z_{i}]\\}_{i=1}^{n})$: The max filter bank
$\Phi_{G_{j}}\colon\mathbb{R}^{d_{j}}/G\to\mathbb{R}^{n}$ defined by
$\Phi_{G_{j}}([x]):=\\{\langle\langle[x],[z_{i}]\rangle\rangle_{G_{j}}\\}_{i=1}^{n}$
weakly avoids $\operatorname{im}(V)$.

Then,

  1. (a)

$P_{1}([Y_{1}],\\{[z_{i}]\\}_{i=1}^{n})\Longleftrightarrow
P_{2}(\psi([Y_{1}]),\\{\psi([z_{i}])\\}_{i=1}^{n})$.

  2. (b)

$W_{1}(\\{[z_{i}]\\}_{i=1}^{n})\Longleftrightarrow
W_{2}(\\{\psi([z_{i}])\\}_{i=1}^{n})$.

The following corollary shows that genericity of strong avoidance of max
filtering is invariant to orbit space isometry:

######  Corollary 89.

In addition to the notation and assumptions in Lemma 88, suppose that
$\psi([Y_{1}])=[Y_{2}]$. Then, $P_{1}([Y_{1}],\\{[z_{i}]\\}_{i=1}^{n})$ (resp.
$W_{1}(\\{[z_{i}]\\}_{i=1}^{n})$) holds for generic
$z_{1},\dots,z_{n}\in\mathbb{R}^{d_{1}}$ if and only if
$P_{2}([Y_{2}],\\{[z_{i}]\\}_{i=1}^{n})$ (resp.
$W_{2}(\\{[z_{i}]\\}_{i=1}^{n})$) holds for generic
$z_{1},\dots,z_{n}\in\mathbb{R}^{d_{2}}$.

Before providing the proofs, we need

######  Lemma 90.

For $j\in\\{1,2\\}$, fix $G_{j}\leq\operatorname{O}(d_{j})$ and suppose that
there exists a homeomorphism
$\varphi\colon\mathbb{R}^{d_{1}}/G_{1}\to\mathbb{R}^{d_{2}}/G_{2}$. Let
$S_{j}\subseteq\mathbb{R}^{d_{j}}$ be semialgebraic and $G_{j}$-invariant. If
$[S_{2}]=\operatorname{im}(\varphi|_{[S_{1}]})$, then $\dim(S_{1})<d_{1}$ if
and only if $\dim(S_{2})<d_{2}$.

###### Proof.

By semialgebraicity and invariance, we have

$\displaystyle\dim(S_{j})=d_{j}$ $\displaystyle\iff$ $\displaystyle
S_{j}\text{ contains an open set}$ $\displaystyle\iff$
$\displaystyle[S_{j}]\text{ contains an open set}.$

The result now follows from continuity of $\varphi$ and $\varphi^{-1}$. ∎

###### Proof of Lemma 88.

For $w\in\mathbb{R}^{d_{j}}$, denote the orbit of $w$ by $[w]_{j}$. By Section
5.1 in [19], we may assume $\psi([0]_{1})=[0]_{2}$. By 29(a), we have for
$x,y\in\mathbb{R}^{d_{1}}$

$\displaystyle 2\langle\langle[x]_{1},[y]_{1}\rangle\rangle$
$\displaystyle=\|x\|^{2}+\|y\|^{2}-d^{2}([x]_{1},[y]_{1})$
$\displaystyle=d^{2}([x]_{1},[0]_{1})+d^{2}([y]_{1},[0]_{1})-d^{2}([x]_{1},[y]_{1})$
$\displaystyle=d^{2}(\psi([x]_{1}),[0]_{2})+d^{2}(\psi([y]_{1}),[0]_{2})-d^{2}(\psi([x]_{1}),\psi([x]_{2}))$
$\displaystyle=2\langle\langle\psi([x]_{1}),\psi([y]_{1})\rangle\rangle.$

As such, max filtering is $\psi$-invariant and the result follows. ∎

###### Proof of Corollary 89.

By Lemma 15, the sets
$C_{Y_{j}}:=\\{\\{[z_{i}]\\}_{i=1}^{n}\in(\mathbb{R}^{d_{j}})^{n}:P_{j}([Y_{j}],\\{[z_{i}]\\}_{i=1}^{n})\\}$
are semialgebraic. The result now follows by applying Lemma 90 to the
component-wise actions of $G_{j}^{n}$ over $(\mathbb{R}^{d_{j}})^{n}$ with

$S_{1}:=\\{\\{[z_{i}]\\}_{i=1}^{n}\in(\mathbb{R}^{d_{1}}/G_{1})^{n}:P_{j}([Y_{1}],\\{[z_{i}]\\}_{i=1}^{n})\\},$
$S_{2}:=\\{\\{[z_{i}]\\}_{i=1}^{n}\in(\mathbb{R}^{d_{2}}/G_{2})^{n}:P_{j}([Y_{2}],\\{[z_{i}]\\}_{i=1}^{n})\\},$

and
$\varphi\colon(\mathbb{R}^{d_{1}})^{n}/G_{1}^{n}\to(\mathbb{R}^{d_{2}})^{n}/G_{2}^{n}$
is the $n$-fold product of $\psi$. A similar argument follows for
$W_{j}(\\{[z_{i}]\\}_{i=1}^{n})$. ∎

##  11 Max Filtering Local Avoidance at Regular Orbits

######  Definition 91.

Suppose $G\leq\operatorname{O}(d)$ is compact with cohomogeneity $c$. The set
of regular points is defined by

$R(G):=\\{x\in\mathbb{R}^{d}:\dim([x])=d-c\\}.$

Equivalently, for $x\in\mathbb{R}^{d}$ and for a principal isotropy group
$G_{p}\leq G_{x}$, we have $x\in R(G)$ if and only if $\dim(G_{x}/G_{p})=0$.

In this section, we leverage minimal reduction (Definition 87) to show that
with enough templates, max filtering locally avoids a fixed subspace at every
regular point. In the case of coorbit filter banks, we refer to Section 9 for
a reduction to max filter banks.

######  Theorem 92.