---
abstract: 'Let $f=(f_1,\ldots,f_n)$ be a system of $n$ complex homogeneous polynomials in $n$ variables of degree $d\geq 2$. We call $(\zeta,\eta)\in {\mathbb{P}}^n\backslash{\left\{[0:1]\right\}}$ an *h-eigenpair* of $f$ if $f(\zeta)=\eta^{d-1} \zeta$. We describe a randomized algorithm to compute approximations of h-eigenpairs of polynomial systems. Assuming random input, the average number of arithmetic operations it performs is polynomially bounded in the input size.'
bibliography:
- 'literature.bib'
title: '[An adaptive linear homotopy method to approximate eigenpairs of homogeneous polynomial systems]{}'
---

[**[An adaptive linear homotopy method to approximate eigenpairs of homogeneous polynomial systems]{}\
**]{} Paul Breiding [^1]

[**AMS subject classifications:**]{} 15A18, 15A69; 15A72; 60D05; 65F15

[**Key words:**]{} tensors, eigenvalues, eigenvalue distribution, random polynomials, computational algebraic geometry

Introduction
============

Inspired by the spectral theory of tensors [@sturmfels-cartwright; @qi3; @lim1; @lim2; @qi2; @qi1], in [@distr] we defined $\lambda\in{\mathbb{C}}$ to be an *eigenvalue* of $f=(f_1,\ldots,f_n)$, a system of $n$ homogeneous polynomials of degree $d$ in $n$ variables, if there exists some $v\in{\mathbb{C}}^n\backslash{\left\{0\right\}}$ with $f(v)=\lambda v$. We call $v$ an *eigenvector* and $(v,\lambda)$ an *eigenpair* of $f$.

Solving for eigenvalues appears to be a hard problem [@lim3]. In [@distr] our approach to overcome this hardness was to endow the space of eigenvalues with a probability distribution of which we computed the density function and gave a method to sample from it. In this paper we want to describe numerical methods to compute eigenpairs. In particular we describe an algorithm that finds approximations of what we call *h-eigenpairs* and that terminates almost surely, see \[main\_thm\]. This also is one of the first contributions to Open Problem 15 in [@condition].

For the case $d=1$, e.g., for the matrix case, in [@armentano] Armentano defines a condition number for the matrix eigenpair problem and, by using this definition, describes an algorithm to approximate eigenpairs of matrices. In [@matrix_eigenpair] Armentano et al. provide a smoothed analysis for this algorithm. The goal of this work is to extend their methods to higher degrees $d\geq 2$. For technical reasons we will also assume that $n\geq 2$.

In [@BSS sec. 14.1, Def. 1] one finds Smale’s notion of an *approximate zero* of a system ${\mathcal{F}}=({\mathcal{F}}_1,\ldots,{\mathcal{F}}_n)$ of $n$ homogeneous polynomials of degree $d$ in $n+1$ variables. We want to use this concept to describe an algorithm that finds approximations of eigenpairs of polynomial systems of degree $d\geq 2$.

For any $s\in{\mathbb{C}}^\times$ it is easy to see that $(v,\lambda)$ is an eigenpair of a polynomial system $f$ if and only if $(sv,s^{d-1}\lambda)$ is an eigenpair of $f$. We call eigenpairs that are related in this way *equivalent*. As already mentioned in [@sturmfels-cartwright] one can view equivalence classes of eigenpairs as elements in the *weighted projective space* ${\mathbb{P}}(1,\ldots,1,d-1)$. However, we lack a throughough complex analysis of this space. We avoid this by homogenizing the equation defining eigenpairs (although the following is not homogenizing in the classical sense we still find this naming appropriate).

For $n,d\geq 2$ let ${\mathcal{H}}_{n,d}$ denote the vector space of homogeneous polynomials of degree $d$ in $n$ variables $X=(X_1,\ldots,X_n)$. We define $\eta\in{\mathbb{C}}$ to be a *homogeneous eigenvalue* of $f\in{\mathcal{H}}_{n,d}^n$, if there exists $\zeta\in{\mathbb{C}}^n\backslash{\left\{0\right\}}$ with $f(\zeta)=~\eta^{d-1} \zeta$. This equation is homogeneous of degree $d$, so we can view $(\zeta,\eta)$ as an element in the *punctured projective space* ${\mathscr{P}}:={\mathbb{P}}^n\backslash{\left\{[0:1]\right\}}$. We call $(\zeta,\eta)\in{\mathscr{P}}$ an *h-eigenpair* of $f$. Using an auxiliary variable $\Lambda$, we associate to $f$ the homogeneous polynomial system ${\mathcal{F}}_f\in{\mathcal{H}}_{n+1,d}^ n$, where $$\label{dfn_F_f}
{\mathcal{F}}_f:{ {\mathbb{C}}^n\times{\mathbb{C}}}\to {\mathbb{C}}^n, \;(X,\Lambda)\mapsto f(X)-\Lambda^{d-1}X.$$ Clearly, $(\zeta,\eta)$ is an h-eigenpair of $f$ if and only if ${\mathcal{F}}_f(\zeta,\eta)=0$. We say that $(v,\lambda)\in{\mathscr{P}}$ is an *approximate eigenpair* of $f$, if $(v,\lambda)$ is an approximate zero of ${\mathcal{F}}_f\in{\mathcal{H}}_{n+1,d}^ n$ in the sense of [@BSS sec. 14.1, Def. 1] and the associated zero $(\zeta,\eta)$ is an h-eigenpair of $f$, that is $(\zeta,\eta)\in{\mathscr{P}}$. In this case we call $(\zeta,\eta)$ the associated eigenpair of $(v,\lambda)$ (see also \[def\_approx\_eigenpair\]). We conclude from [@distr Prop. 3.8] that the number of h-eigenpairs of a generic system $f$ is ${\mathcal{D}}(n,d):=d^n-1$. Our model of complexity counts arithmetic operations, where taking square roots and drawing from a gaussian distribution are included. The main result, that we will prove at the end of Section \[se:newton\], is as follows.

\[main\_thm\] There is a randomized algorithm that for on input $f\in{\mathcal{H}}_{n,d}^n$ almost surely returns an approximate eigenpair of $f$. Its average number of arithmetic operations is ${\mathcal{O}}(dnN+n^\frac{5}{2}N^2)$, where $N=\dim_{\mathbb{C}}{\mathcal{H}}_{n,d}^n = n\binom{n+d-1}{n-1}$.

In \[approx\_rem\] we discuss that the algorithm of \[main\_thm\] not only approximates h-eigenpairs, but also approximates eigenvectors.

We denote h-eigenpairs with symbols $(\zeta,\eta)$ and eigenpairs with symbols $(v,\lambda)$. We will also denote approximate eigenpairs with $(v,\lambda)$.

Moreover, we will often use the same symbols for elements in ${\mathscr{P}}$ and their representatives in $({\mathbb{C}}^n\backslash{\left\{0\right\}})\times {\mathbb{C}}$. All this should not cause much confusion

The adaptive homotopy method for the h-eigenpair problem
--------------------------------------------------------

The main tool used in [@beltran_pardo1; @BSS; @on_a_problem_smale; @condition] to approximate zeros of homogeneous polynomial systems is the *adaptive homotopy method*. It roughly works as follows. Let ${\mathcal{G}}\in{\mathcal{H}}_{n+1,d}^n$ be a system of which a zero is known. If ${\mathcal{F}}\in{\mathcal{H}}_{n+1,d}^n$ is another system that one wants to solve, one connects ${\mathcal{G}}$ with ${\mathcal{F}}$ by a continuous path. This path is discretized and the zero of ${\mathcal{G}}$ is continued along that discretized path using *Newton’s method*. The fineness of the discretization is determined by a *condition number*.

In [@condition sec. 17.1, algorithm 17.1] Bürgisser and Cucker present the algorithm <span style="font-variant:small-caps;">alh</span>, which computes approximate zeros of arbitrary homogeneous polynomial systems ${\mathcal{F}}\in~{\mathcal{H}}_{d,n+1}^n$. We show in \[sec:1.2\] below, that this algorithm, however, does not work efficiently for the structured set of polynomial systems ${\left\{{\mathcal{F}}_f\mid f\in{{\mathcal{H}}}\right\}} \subset {\mathcal{H}}_{d,n+1}^n$.

The main problem in our situation is that Newton’s method does not distinguish between eigenvectors and eigenvalues and simply sees eigenpairs as points in projective space. We need to make sure *a priori* that we do not get too close to the point $[0:1]\in{\mathbb{P}}^n$. Applying Newton’s method there gives us the trivial solution $f(0)=1\cdot 0$.

Let ${\left\lVert \cdot \right\rVert}$ denote the norm induced by the Bombieri-Weyl inner product on ${\mathcal{H}}_{n,d}^n$ (for details see \[se:geo-framework\]) and let ${\mathbb{S}}({\mathcal{H}}_{n,d}^n):={\left\{f\in{\mathcal{H}}_{n,d}^n\mid {\left\lVert f \right\rVert}=1\right\}}$. In \[useful\_lemma2\] we show that, if $f\in{\mathbb{S}}({\mathcal{H}}_{n,d}^n)$, then for all h-eigenpairs $(\zeta,\eta)$ of $f$ we have ${\left\lvert \eta \right\rvert}/{\left\lvert \zeta \right\rvert}\leq 1$. This shows that all h-eigenpairs of such an $f$ are sufficiently far away from $[0:1]$. Moreover, if we approximate carefully, all approximations of all h-eigenpairs of such an $f$ are sufficiently far away from $[0:1]$; cf. \[fig1\]. This restriction enables us to adapt the ideas from [@condition sec. 16-17] and [@matrix_eigenpair; @armentano; @beltran_pardo1; @on_a_problem_smale] to describe a homotopy method for the h-eigenpair problem.

Given two systems $f,g\in{\mathbb{S}}({\mathcal{H}}_{n,d}^n)$, let $E_{f,g}\subset {\mathbb{S}}({\mathcal{H}}_{n,d}^n)$ denote the geodesic path from $f$ to $g$. The corresponding path from ${\mathcal{F}}_f$ to ${\mathcal{F}}_g$ is ${\left\{{\mathcal{F}}_q\mid q \in E_{f,g}\right\}}$.

The problem of solving for eigenpairs comes with two notions of condition, depending on how one defines the output. Defining the output as elements in ${\mathscr{P}}$ respects the architecture of Newton’s method, while defining the output as elements in ${ {\mathbb{S}}({\mathbb{C}}^n)\times{\mathbb{C}}}$ respects the geometry of the h-eigenpair problem. We will describe both notions in a moment. Let us denote the derivative of ${\mathcal{F}}_f$ at $(v,\lambda)$ by $D{\mathcal{F}}_f(v,\lambda)$. Furthermore, we denote $(v,\lambda)^\perp:=\{(w,\gamma)\in { {\mathbb{C}}^n\times{\mathbb{C}}}\mid(v,\lambda)^T\;\overline{(w,\gamma)}=0\}$ and $v^\perp\times {\mathbb{C}}:=\{(w,\gamma)\in { {\mathbb{C}}^n\times{\mathbb{C}}}\mid v^T\;\overline{w}=0\}.$

\[mu\_def\]

1.  For $(f,\zeta,\eta)\in {\mathcal{H}}_{n,d}^n\times{\mathscr{P}}$ we define the *(absolute) condition number for the h-eigenpair problem with output in ${\mathscr{P}}$* as $$\mu(f,v,\lambda):={\left\lVert v \right\rVert}^{d-1}{\left\lVert {\ensuremath{\left.D{\mathcal{F}}_f(v,\lambda)\right|_{(v,\lambda)^\perp}}}^{-1} \right\rVert},$$ if ${\ensuremath{\left.D{\mathcal{F}}_f(v,\lambda)\right|_{(v,\lambda)^\perp}}}$ is invertible and $\mu(f,v,\lambda):=\infty$ otherwise. Here $(v,\lambda)\in({\mathbb{C}}^n\backslash{\left\{0\right\}})\times {\mathbb{C}}$ denotes some representative of $(v,\lambda)\in~{\mathscr{P}}$ (compare [@condition eq. (16.6)], where a *relative* condition number is defined.)

2.  For $(f,v,\lambda)\in{\mathcal{H}}_{n,d}^n\times{ {\mathbb{S}}({\mathbb{C}}^n)\times{\mathbb{C}}}$ we define the *(relative) condition number for the h-eigenpair problem with output in ${ {\mathbb{S}}({\mathbb{C}}^n)\times{\mathbb{C}}}$* as $$\label{mu_def2}
    {\widehat{\mu}}(f,v,\lambda):={\left\lVert \begin{bmatrix} {\left\lVert f \right\rVert} I_{n}&0\\0&{\left\lVert f \right\rVert}^\frac{d-2}{d-1}\end{bmatrix} {\ensuremath{\left.D{\mathcal{F}}_f(v,\lambda)\right|_{v^\perp\times {\mathbb{C}}}}}^{-1} \right\rVert},$$ if ${\ensuremath{\left.D{\mathcal{F}}_f(v,\lambda)\right|_{v^\perp\times {\mathbb{C}}}}}$ is invertible and ${\widehat{\mu}}(f,v,\lambda):=\infty$ otherwise. Here $I_n$ denotes the $n\times n$ identity matrix.

Observe that for all $s\in{\mathbb{C}}^\times$ we have $\mu(f,v,\lambda)=\mu(f,sv,s\lambda)$. This shows that the definition of $\mu(f,v,\lambda)$ is independent of the choice of a representative of $(v,\lambda)\in{\mathscr{P}}$ and hence it is well defined on ${\mathcal{H}}_{n,d}^n \times {\mathscr{P}}$.

The two condition numbers are connected in the following way. In \[condition\_for\_eigenpairs\] we show that for $(f,\zeta,\eta)\in {\mathbb{S}}({\mathcal{H}}_{n,d})^n\times{\mathscr{P}}$ and $(\zeta,\eta)\in{ {\mathbb{S}}({\mathbb{C}}^n)\times{\mathbb{C}}}$ also denoting a representative of $(\zeta,\eta)$ we have $$\frac{1}{\sqrt{2}}\,{\widehat{\mu}}(f,\zeta,\eta)\leq \mu(f,\zeta,\eta) \leq {\widehat{\mu}}(f,\zeta,\eta)$$ Observe that this relation is reasonable only when ${\left\lVert f \right\rVert}=1$, because $\mu(f,v,\lambda)$ is an absolute condition number, but ${\widehat{\mu}}(f,v,\lambda)$ is a relative condition number.

The motivation for the two definitions is provided in \[se:condition\], in particular in \[condition\_for\_eigenpairs\]. As mentioned before, the two definitions reflect the two possibilities of interpreting the output of the h-eigenpair problem: as elements in ${\mathscr{P}}$ or as elements in ${ {\mathbb{S}}({\mathbb{C}}^n)\times{\mathbb{C}}}$. It turns out that under the restriction $f\in {\mathbb{S}}({\mathcal{H}}_{n,d}^n)$ the condition number $\mu$ can be used to describe a homotopy method for the eigenpair problem, see \[Theorem\_4.4\]. But $\mu$ does not scale properly with $f$, see \[rem2\] for details. This is why we define $\mu$ to be absolute.

By contrast, ${\widehat{\mu}}$ is invariant under scaling of $f$: $$\forall s\in{\mathbb{C}}^\times: {\widehat{\mu}}(s^{d-1}f,v,s\lambda)={\widehat{\mu}}(f,sv,s\lambda),$$ see \[2dmu\](5). We will make use of this property of ${\widehat{\mu}}(f,v,\lambda)$ when giving a probabilistic analysis for our algorithm, see \[mu\_expectation0\]. However, ${\widehat{\mu}}(f,v,\lambda)$ cannot be used to construct a homotopy method that works properly. The reason for this is discussed in \[rem1\].

Summarizing, we need the condition number $\mu(f,v,\lambda)$ to construct the algorithm and the condition number ${\widehat{\mu}}(f,v,\lambda)$ to analyze this algorithm.

(-[0.6 cm]{},0cm) – ([0.6 cm]{},0cm) node\[right,fill=white\] [$\zeta$]{}; (0cm,0cm) – (0cm,0.65cm) node\[above,fill=white\] [$\eta$]{}; (0cm,0cm) – (0:[0.4 cm]{}) arc (0:180:[0.4 cm]{}); (0cm,0cm) – (0:[0.4 cm]{}) arc (0:45:[0.4 cm]{}); (0cm,0cm) – (135:[0.4 cm]{}) arc (135:180:[0.4 cm]{}); ([0.4 cm]{},0) – ([0.4 cm]{},[0.6 cm]{}) node\[above=1pt\] [$\underbrace{{\left\lVert v \right\rVert}={\left\lVert \zeta \right\rVert}=1}$]{}; (0cm,0cm) – ([0.4 cm]{},0.3cm) node\[right=1pt\][$(\zeta,\eta)$]{}; (0cm,0cm) – ([0.4 cm]{},0.5cm) node\[right=1pt\][$(v,\lambda)$]{}; (0cm,[0.4 cm]{}) node\[above left=1pt\][$[0:1]$]{}; (0cm,[0.4 cm]{}) circle(0.4pt);

Why the homotopy method for general homogeneous polynomial systems is not a good choice {#sec:1.2}
---------------------------------------------------------------------------------------

The algorithm <span style="font-variant:small-caps;">alh</span> in [@condition Algorithm 17.1] is designed to approximate zeros for polynomial systems in ${\mathcal{H}}_{n+1,d}^n$. It is clear that this algorithm ignores the geometric situation of the h-eigenpair problem and this is what causes algorithm <span style="font-variant:small-caps;">alh</span> to perform poorly on ${\mathcal{F}}({\mathcal{H}}_{n,d}^n) := {\left\{ {\mathcal{F}}_f\mid f\in{\mathcal{H}}_{n,d}^n\right\}}\subset {\mathcal{H}}_{n+1,d}^n.$

In [@condition sec. 17-18] Bürgisser and Cucker analyze the algorithm <span style="font-variant:small-caps;">alh</span> with respect to the Bombieri-Weyl product on ${\mathcal{H}}_{n+1,d}^n$. Our structured set of polynomials ${\mathcal{F}}({\mathcal{H}}_{n,d}^n)$ is an affine linear subspace within ${\mathcal{H}}_{n+1,d}^n$. The inner product we choose on ${\mathcal{F}}({\mathcal{H}}_{n,d}^n)$ is the inner product induced by the Bombieri-Weyl product on ${\mathcal{H}}_{n,d}^n$. So small angles in ${\mathcal{F}}({\mathcal{H}}_{n,d}^n)$ may lead to ${\mathcal{H}}_{n+1,d}^n$, c.f. \[fig2\].

To be explicit let $f,g\in{\mathcal{H}}_{n,d}^n$ and $(\zeta,\eta)$ be an h-eigenpair of $g$. We denote by $K(f,(g,\zeta,\eta))$ the number of steps that the algorithm <span style="font-variant:small-caps;">alh</span> performs on input $f$ and $(g,\zeta,\eta)$. In section \[proof\_Proposition\_1.4\] we show the following.

\[Proposition\_1.4\] If the real and imaginary parts of the coeffients of $f$ and $g$ are independent centered gaussian random variables with variance $\sigma^2=~\frac{1}{2}$, and $(\zeta,\eta)$ is chosen uniformly at random from the $D(n,d)=d^n-1$ many h-eigenpairs of $g$, then $\operatorname*{\mathrm{Prob}}{\left\{K\geq  \frac{74}{\sqrt{2}}\; \frac{n}{\sqrt{d}}\;2^{2(d-1)}\; \right\}}>0.14.$

We get that the probability of $K$ being exponentially large in $d$ is at least $14\%$. Hence, on the average, we expect <span style="font-variant:small-caps;">alh</span> to perform a very large number of steps on instances of the h-eigenpair problem.

\[tdplot\_main\_coords, affine/.style=[thick,black]{}, axis/.style=[-&gt;,thick,gray]{}\]

(0,0,0) – (0.5,1,3); (0,0,0) – (0,4,3); (0,0,3) – (0.5,1,3); (0,0,3) – (0,4,3); (0.5,1,3) – (0,4,3); in [-1.5,2]{} in [-1.2,5]{} [ (,-1.2,3) – (,5,3); (-1.5,,3) – (2,,3); ]{} (0,0,0) – (2,0,0) node\[anchor= north west\]; (0,0,0) – (0,3,0) node\[anchor=west\]; (0,0,0) – (0,0,5) node\[anchor=west\];

(0,0,3) circle (0.15) node\[anchor=east\][${\mathcal{F}}_0\;$]{}; (0,0,0) circle (0.1) node\[anchor=south east\][$0$]{}; (-1.5,-1.2,3) circle (0) node\[anchor=south west\][${\mathcal{F}}({\mathcal{H}}_{n,d}^n)$]{}; (2,-1,0) circle (0) node\[anchor=south west\][${\mathcal{H}}_{n+1,d}^n$]{};

;

Organization
------------

The organization of the paper is as follows. We first establish in Section \[se:geo-framework\] the geometric framework for the eigenpair problem. Our concepts and notations are close to the ones from [@condition sec. 16] and some of our results in [@distr] will be transferred to the h-eigenpair scenario. In Section \[se:condition\] we derive the condition of solving for h-eigenpairs using the geometric framework for condition numbers given in [@condition sec. 14]. This will justify \[mu\_def\]. In Section \[se:newton\] we describe the homotopy method that uses the condition number to approximate h-eigenpairs and construct from it a randomized algorithm, that proves \[main\_thm\]. In the remaining sections and in the appendix we give further proofs.

Acknowledgements
----------------

The basis of this work was laid during the program “Algorithms and Complexity in Algebraic Geometry” at the Simons Institute for the Theory of Computing. We are grateful for the Simons Institute for the stimulating environment and the financial support.

We further want to emphasize that this work would not have been possible without the help and support of Peter Bürgisser. We are very thankful for all the discussions and advice. They have been pivotal in shaping the current form of the sections and proofs.

Geometric framework {#se:geo-framework}
===================

Let $n,d\geq 2$. On ${\mathbb{C}}^n$ we choose the standard hermitian inner product $\langle x,y\rangle =x^T\overline{y}$. We furthermore denote the sphere in ${\mathbb{C}}^n$ by ${\mathbb{S}}({\mathbb{C}}^n):={\left\{x\in{\mathbb{C}}^n\mid {\left\lVert x \right\rVert}=1\right\}}$ and by ${\mathbb{P}}({\mathbb{C}}^n)$ we denote the projective space over ${\mathbb{C}}^n$. The real sphere is denoted by ${\mathbb{S}}({\mathbb{R}}^n):={\left\{y\in{\mathbb{R}}^n\mid y^Ty=1\right\}}$.

Let $x,y\in{\mathbb{R}}^n\backslash{\left\{0\right\}}$. We define the spherical distance between $x$ and $y$, denoted by $d_{\mathbb{S}}(x,y)$, as the angle between the rays ${\mathbb{R}}_{>0}x$ and ${\mathbb{R}}_{>0}y$. In particular, $\cos d_{\mathbb{S}}(x,y)=  (x^Ty) \cdot {\left\lVert x \right\rVert}^ {-1}{\left\lVert y \right\rVert}^ {-1}.$

If $x,y\in{\mathbb{C}}^n\backslash{\left\{0\right\}}$, we define $d_{\mathbb{S}}(x,y)$ as the angle between the rays ${\mathbb{R}}_{>0}x$ and ${\mathbb{R}}_{>0}y$, where $x$ and $y$ are interpreted as elements in ${\mathbb{R}}^{2n}$. In particular, $\cos d_{\mathbb{S}}(x,y)=  \Re(x^T\overline{y})\cdot {\left\lVert x \right\rVert}^ {-1}{\left\lVert y \right\rVert}^ {-1}.$ Moreover, for $x,y\in{\mathbb{P}}({\mathbb{C}}^n)$ we define the projective distance between $x$ and $y$ as $d_{\mathbb{P}}(x,y)={\left\lvert \langle x,y\rangle \right\rvert}\cdot {\left\lVert x \right\rVert}^ {-1}{\left\lVert y \right\rVert}^ {-1}$. It is well known that $d_{\mathbb{P}}$ is the riemannian metric on ${\mathbb{P}}({\mathbb{C}}^n)$.

As in the introduction we denote by ${\mathcal{H}}_{n,d}$ the space of homogeneous polynomials of degree $d$ in the $n$ variables $X=(X_1,\ldots,X_n)$. The Bombieri-Weyl product $\langle\;,\;\rangle$ on ${\mathcal{H}}_{n,d}$ is defined as follows. For $f=\sum_\alpha f_\alpha \sqrt{\binom{d}{\alpha}}  X^\alpha$ and $g=\sum_\alpha g_\alpha \sqrt{\binom{d}{\alpha}}  X^\alpha$ we put $\langle f,g\rangle = \sum_\alpha f_\alpha\overline{g_\alpha}$. Further, for $f=(f_1,\ldots,f_n)$, $g=(g_1,\ldots,g_n)\in{\mathcal{H}}_{n,d}^n$ we define $\langle f,g\rangle:=\sum_{i=1}^n\langle f_i,g_i,\rangle$. The Bombieri-Weyl norm is ${\left\lVert f \right\rVert}=\sqrt{\langle f,f\rangle}$.

For $x\in({\mathbb{C}}^n\backslash{\left\{0\right\}})$ let $Z(x):={\left\{f\in{\mathcal{H}}_d\mid f(x)=0\right\}}$. By [@condition Prop. 16.16] the space ${\mathcal{H}}_d$ decomposes orthogonally as $$\label{orthogonal_decomposition}
    {\mathcal{H}}_d = C(x)\oplus L(x) \oplus R(x),$$ where $R(x):={\left\{f\in{\mathcal{H}}_d\mid f(x)=0, Df(x)=0\right\}}$, $L(x):=R(x)^\perp \cap Z(x)$ and $C(x):=Z(x)^\perp$. Moreover, the map $x^\perp \to L(x),\; a \mapsto \sqrt{d}\; \langle X,x\rangle^ {d-1} a^T X$ is an isometry, that is ${\left\lVert  \sqrt{d}\; \langle X,x\rangle^ {d-1} a^T X \right\rVert} = {\left\lVert a \right\rVert}$.

In the following we abbreviate ${{\mathcal{H}}}:={\mathcal{H}}_{n,d}^n$.

Recall from \[dfn\_F\_f\] that to $f\in{{\mathcal{H}}}$ we associate the polynomial system ${\mathcal{F}}_f\in{\mathcal{H}}_{n+1,d}^n$, where $\Lambda$ is an auxiliary variable, via ${\mathcal{F}}_f:{\mathbb{C}}^n\times{\mathbb{C}}\to {\mathbb{C}}^n,$ $(v,\lambda)\mapsto f(v)-\lambda^{d-1}v.$ Further, recall from the introduction that we have put ${\mathscr{P}}={\mathbb{P}}({\mathbb{C}}^n\times {\mathbb{C}})\backslash{\left\{[0:1]\right\}}$.

For $(f,(\zeta,\eta))\in {\mathcal{H}}\times{\mathscr{P}}$ we write $(f,\zeta,\eta):=(f,(\zeta,\eta))$ by abuse of notation.

We define the *solution varieties* as $$\begin{aligned}
{{\bf V}}&:={\left\{(f,\zeta,\eta)\in {{\mathcal{H}}}\times {\mathscr{P}}\mid  {\mathcal{F}}_f(\zeta,\eta)=0\right\}}.\\
\text{and}\quad{\widehat{{\bf V}}}&:={\left\{(f,\zeta,\eta)\in {{\mathcal{H}}}\times { {\mathbb{S}}({\mathbb{C}}^n)\times{\mathbb{C}}}\mid  {\mathcal{F}}_f(\zeta,\eta)=0\right\}}.\end{aligned}$$ Observe, that our choice of representatives for ${\mathscr{P}}$ is not as usual. Instead of using the sphere ${\mathbb{S}}({\mathbb{C}}^n\times{\mathbb{C}})$ we use the product ${\mathbb{S}}({\mathbb{C}}^n)\times {\mathbb{C}}$: We normalize ${\left\lVert \zeta \right\rVert}=1$ instead of ${\left\lVert \zeta,\eta \right\rVert}=1$. Since $[0:1]\not\in{\mathscr{P}}$, this is always possible. As mentioned in the introduction this normalization reflects the need for bounding the ratio $\frac{{\left\lvert \eta \right\rvert}}{{\left\lVert \zeta \right\rVert}}$.

We define the sets of *well-posed triples* as $$\begin{aligned}
{{\bf W}}&:={\left\{(f,\zeta,\eta)\in {{\bf V}}\mid  {\mathrm{rk}\,}D{\mathcal{F}}_f(\zeta,\eta)=n\right\}}\\
\text{and}\quad{\widehat{{\bf W}}}&:={\left\{(f,\zeta,\eta)\in {\widehat{{\bf V}}}\mid  {\mathrm{rk}\,}D{\mathcal{F}}_f(\zeta,\eta)=n\right\}},\end{aligned}$$ and the sets of *ill-posed triples* ${\mathbf{\Sigma}}\,':={{\bf V}}\backslash{{\bf W}},$ ${\widehat{\mathbf{\Sigma}}}\,':={\widehat{{\bf V}}}\backslash{\widehat{{\bf W}}}.$

Euler’s formula for homogeneous functions implies $ D{\mathcal{F}}_f(\zeta,\eta)(\zeta,\eta)^T=0$. Hence, ${\mathrm{rk}\,}D{\mathcal{F}}_f(\zeta,\eta)=n$ is equivalent to ${\ensuremath{\left.D{\mathcal{F}}_f(\zeta,\eta)\right|_{(\zeta,\eta)^\perp}}}$ being invertible. Since $(\zeta,\eta)\cap \zeta^\perp \times{\mathbb{C}}= {\left\{0\right\}}$, the property ${\mathrm{rk}\,}D{\mathcal{F}}_f(\zeta,\eta)=n$ is also equivalent to ${\ensuremath{\left.D{\mathcal{F}}_f(\zeta,\eta)\right|_{\zeta^\perp\times {\mathbb{C}}}}}$ being invertible.

Let ${\mathcal{U}}(n)$ denote the group of unitary linear maps ${\mathbb{C}}^n\to{\mathbb{C}}^n$. We define a group action on ${{\mathcal{H}}}$ via $U.f:=U\circ f\circ U^{-1}$ and a group action on ${{\bf V}}$ and ${\widehat{{\bf V}}}$ via $U.(f,\zeta,\eta):=(U.f,U\zeta,\eta)$, respectively. We note that ${{\bf W}}$ is ${\mathcal{U}}(n)$-invariant and that ${\mathcal{U}}(n)$ acts on ${{\mathcal{H}}}$ by isometries; see [@condition Theorem 16.3].

The sets above come with a couple of projections $$\begin{aligned}
\pi_1: {{\bf V}}\to{{\mathcal{H}}},\; (f,\zeta,\eta)\mapsto f,\quad &\pi_2: {{\bf V}}\to{\mathscr{P}},\; (f,\zeta,\eta)\mapsto (\zeta,\eta),\\
{\widehat{\pi}}_1: {\widehat{{\bf V}}}\to{{\mathcal{H}}},\; (f,\zeta,\eta)\mapsto f,\quad &{\widehat{\pi}}_2: {\widehat{{\bf V}}}\to{ {\mathbb{S}}({\mathbb{C}}^n)\times{\mathbb{C}}},\; (f,\zeta,\eta)\mapsto (\zeta,\eta).\end{aligned}$$ Clearly, all $\pi_1,\pi_2,{\widehat{\pi}}_1,{\widehat{\pi}}_2$ are ${\mathcal{U}}(n)$-equivariant. We define the *extended eigendiscriminant variety* ${\mathbf{\Sigma}}\subset{\mathcal{H}}_d^n$ as the Zariski closure of $\pi_1({\mathbf{\Sigma}}\,')=\pi_1({\widehat{\mathbf{\Sigma}}}\,')$.

In [@distr sec. 3.4] we introduced the eigendiscriminant variety $\Sigma\subset{{\mathcal{H}}}$, whose naming is taken from [@sturmfels-seigal sec. 4]. In section \[sec: eigenpairs\] we show that ${\mathbf{\Sigma}}$ is the union of $\Sigma$ and all $f\in{{\mathcal{H}}}$ that have $0$ as eigenvalue.

As mentioned earlier in the introduction, the special structure of the polynomial system ${\mathcal{F}}_f(X,\Lambda)$ requires us to bound the norm of $f$. We define $$\begin{aligned}
{{\bf V}}_{\mathbb{S}}&:={\left\{(f,\zeta,\eta)\in {\mathbb{S}}({{\mathcal{H}}})\times {\mathscr{P}}\mid  f(\zeta)=\eta^{d-1}\cdot \zeta\right\}},\\
\text{and}\quad{\widehat{{\bf V}}}_{\mathbb{S}}&:={\left\{(f,\zeta,\eta)\in {\mathbb{S}}({{\mathcal{H}}})\times { {\mathbb{S}}({\mathbb{C}}^n)\times{\mathbb{C}}}\mid  f(\zeta)=\eta^{d-1}\cdot \zeta\right\}},\end{aligned}$$ and ${{\bf W}}_{\mathbb{S}}$, ${\widehat{{\bf W}}}_{\mathbb{S}}$, correspondingly.

\[useful\_lemma2\] Let $(f,\zeta,\eta)\in {\widehat{{\bf V}}}_{\mathbb{S}}$. Then ${\left\lvert \eta \right\rvert}\leq 1$.

Suppose $f=(f_1,\ldots,f_n)\in{\mathbb{S}}({\mathcal{H}})$. For any $1\leq i\leq n$ we have ${\left\lvert f_i(\zeta) \right\rvert}={\left\lvert \eta \right\rvert}^{d-1}{\left\lvert \zeta_i \right\rvert}$. By [@condition Lemma 16.5] we have ${\left\lvert f_i(\zeta) \right\rvert}\leq {\left\lVert f_i \right\rVert}\cdot {\left\lVert \zeta \right\rVert}^{d}$. This implies $${\left\lvert \eta \right\rvert}^{2(d-1)}=\sum_{i=1}^n{\left\lvert \eta \right\rvert}^{2(d-1)} {\left\lvert \zeta_i \right\rvert}^2 \leq \sum_{i=1}^n{\left\lVert f_i \right\rVert}^{2} {\left\lVert \zeta \right\rVert}^{2d}=1.$$

Eigenpairs vs. h-eigenpairs {#sec: eigenpairs}
---------------------------

In [@distr] we defined a pair $(v,\lambda)\in{ {\mathbb{S}}({\mathbb{C}}^n)\times{\mathbb{C}}}$ to be an eigenpair of a homogeneous polynomial system $f\in{{\mathcal{H}}}$, if $f(v)=\lambda v$. We moreover defined the polynomial system $F_f(X,\Lambda)=f(X)-\Lambda X$, the solution variety $V = {\left\{(f,v,\lambda)\in{{\mathcal{H}}}\times{ {\mathbb{S}}({\mathbb{C}}^n)\times{\mathbb{C}}}\mid F_f(v,\lambda)=0\right\}},$ the set of well-posed triples $W = {\left\{(f,v,\lambda)\in V\mid {\mathrm{rk}\,}DF_f(v,\lambda)=n\right\}}$ and the set of ill-posed triples $\Sigma\,'=V\backslash W$. Consider the surjective differentiable map $$\psi: {\widehat{{\bf V}}}\to V,\quad (f,\zeta,\eta)\mapsto (f,\zeta,\eta^{d-1}).$$ Derivating both sides of the equation $F_f(\zeta,\eta^{d-1})={\mathcal{F}}_f(\zeta,\eta)$ shows that we have $${\widehat{\mathbf{\Sigma}}}\,'=\psi^{-1}(\Sigma')\cup{\left\{(f,\zeta,\eta)\in{\widehat{{\bf V}}}\mid \eta=0\right\}}$$ and $\psi({\widehat{{\bf W}}})\subset W.$ The following is implied by [@distr Prop. 3.8].

\[prop\_eigendiscriminant\]

1.  The set ${\mathbf{\Sigma}}$ is a proper subvariety of ${\mathcal{H}}$.

2.  If $f\not\in {\mathbf{\Sigma}}$, $f$ has ${\mathcal{D}}(n,d)=d^n-1$ many h-eigenpairs.

We moreover have the following.

\[tangent\_space\] The tangent space of ${{\bf V}}$ at $(f,\zeta,\eta)\in {{\bf W}}$ equals $${\left\{(\dot{f},\dot{\zeta},\dot{\eta})\in {{\mathcal{H}}}\times T_{(\zeta,\eta)}{\mathscr{P}}\mid (\dot{\zeta},\dot{\eta})=-D{\mathcal{F}}_f(\zeta,\eta)|_{(\zeta,\eta)^\perp}^{-1}\cdot\dot{f}(\zeta)\right\}}.$$ The tangent space of ${\widehat{{\bf V}}}$ at $(f,\zeta,\eta)\in{\widehat{{\bf W}}}$ equals $${\left\{(\dot{f},\dot{\zeta}+ri\zeta,\dot{\eta})\in {{\mathcal{H}}}\times (\zeta^\perp\oplus {\mathbb{R}}i\zeta)\times {\mathbb{C}}\mid (\dot{\zeta},\dot{\eta})=-D{\mathcal{F}}_f(\zeta,\eta)|_{\zeta^\perp\times{\mathbb{C}}}^{-1}\cdot\dot{f}(\zeta)\right\}}.$$

Let $\Pi:{\widehat{{\bf V}}}\to {{\bf V}}$ denote the canonical projection. Then $\Pi= {\mathrm{id}}\times p$, where $p:  {\mathbb{S}}({\mathbb{C}}^n) \times {\mathbb{C}}\to {\mathscr{P}}$ is the canonical projection. Hence $$\label{Dp}
D\Pi(f,\zeta,\eta) = {\mathrm{id}}_{{{\mathcal{H}}}} \times Dp(\zeta,\eta).$$ From [@condition eq. (14.10)] we know that we can identify $T_{(\zeta,\eta)}{\mathscr{P}}$ with $(\zeta,\eta)^\perp$. From [@condition Lemma 14.9] we get the orthogonal decomposition $T_{(\zeta,\eta)}{\mathbb{S}}({\mathbb{C}}^n) = \zeta^\perp \oplus {\mathbb{R}}i\zeta $. This shows that $Dp(\zeta,\eta)$ decomposes as $$\label{Dp2}
Dp(\zeta,\eta): (\zeta^\perp\oplus {\mathbb{R}}i\zeta)\times {\mathbb{C}}\to \zeta^\perp \times{\mathbb{C}}\stackrel{\sim}{\to} (\zeta,\eta)^\perp;$$ the first map being the orthogonal projection and the second the isomorphism that results from the orthogonal projection $ \zeta^\perp \times{\mathbb{C}}\to (\zeta,\eta)^\perp$. Since $T_{\Pi(f,\zeta,\eta)}{{\bf V}}= D\Pi(f,\zeta,\eta) T_{(f,\zeta,\eta)}{\widehat{{\bf V}}}$, the first claim follows from the second.

We now show the second claim. The derivative of $\psi$ at $(f,\zeta,\eta)$ is $$D\psi(f,\zeta,\eta): T_{(f,\zeta,\eta)} {\widehat{{\bf V}}}\to T_{\psi(f,\zeta,\eta)}V,\quad (\dot{f},\dot{\zeta},\dot{\eta})\mapsto (\dot{f},\dot{\zeta},(d-1)\eta^{d-2}\dot{\eta}).$$ Since $(f,\zeta,\eta)\in{\widehat{{\bf W}}}$ we have $\eta\neq 0$, so $D\psi(f,\zeta,\eta)$ is a ${\mathbb{C}}$-linear isomorphism, which implies $T_{(f,\zeta,\eta)} {\widehat{{\bf V}}}=  D\psi(f,\zeta,\eta)^{-1}T_{\psi(f,\zeta,\eta)}V.$ Further, $(f,\zeta,\eta)\in{\widehat{{\bf W}}}$ implies $\psi(f,\zeta,\eta)\in W$. Let us write $\psi= {\mathrm{id}}_{{{\mathcal{H}}}}\times{\mathrm{id}}_{{\mathbb{S}}({\mathbb{C}}^n)}\times\psi'$ and put $v:=\zeta$, $\lambda:=\psi'(\eta)=\eta^{d-1}$. In [@distr Cor. 3.5] we have shown that

$$T_{(f,v,\lambda)} W = {\left\{(\dot{f},\dot{v}+riv,\dot{\lambda})\in {{\mathcal{H}}}\times (\zeta^\perp\oplus {\mathbb{R}}iv) \times {\mathbb{C}}\mid (\dot{v},\dot{\lambda})=-DF_f(v,\lambda)|_{v^\perp\times{\mathbb{C}}}^{-1}\cdot\dot{f}(v)\right\}}.$$ Put $A:= {\mathrm{id}}\times D\psi'(\eta)$ and $(\dot{\zeta},\dot{\eta}):=A^{-1}(\dot{v},\dot{\lambda})$. One verifies that $$(\dot{\zeta},\dot{\eta})=-A^{-1}DF_f(v,\lambda)|_{v^\perp\times{\mathbb{C}}}^{-1}\cdot\dot{f}(v)= -{\ensuremath{\left.D{\mathcal{F}}_f(\zeta,\eta)\right|_{\zeta^\perp\times{\mathbb{C}}}}}^{-1}\dot{f}(\zeta),$$ from which the claim follows.

\[cor\_jacobian\_proj\] Let $\mathrm{NJ}$ denote the normal jacobian, see [@condition sec. 17.3] or \[A4\].

1.  For $(f,\zeta,\eta)\in {\widehat{{\bf V}}}$ we have $\frac{\mathrm{NJ}({\widehat{\pi}}_1)(f,\zeta,\eta)}{\mathrm{NJ}({\widehat{\pi}}_2)(f,\zeta,\eta)} = {\left\lvert \det {\ensuremath{\left.D{\mathcal{F}}_f(\zeta,\eta)\right|_{\zeta^\perp\times {\mathbb{C}}}}} \right\rvert}^2.$

2.  Let $\Pi: {\widehat{{\bf V}}}\to {{\bf V}}$ denote the canonical projection. Then we have $\mathrm{NJ}(\pi_1)\left(\Pi(f,\zeta,\eta)\right)\,\mathrm{NJ}(\Pi)(f,\zeta,\eta)  = \mathrm{NJ}({\widehat{\pi}}_1)(f,\zeta,\eta).$

For (1) we use \[tangent\_space\], \[NJ\_smale\_lemma\] and the ${\mathcal{U}}(n)$-equivariance of the projections ${\widehat{\pi}}_1,{\widehat{\pi}}_2$ and proceed as in the proof of [@distr Lemma 3.6].

Let us prove (2). Let $(f,\zeta,\eta)\in{\widehat{{\bf V}}}$. By definition we have ${\widehat{\pi}}_1 = \pi_1\circ \Pi$, so that $$\label{Dp_eq}
D{\widehat{\pi}}_1(f,\zeta,\eta)  = D\pi_1 (\Pi(f,\zeta,\eta))\; D \Pi(f,\zeta,\eta).$$ Let $\widehat{A}:=D{\widehat{\pi}}_1(f,\zeta,\eta)$, $A:=D\pi_1(\Pi(f,\zeta,\eta))$ and $\widehat{U}:=\ker \widehat{A}$, $U:=\ker A$ and $W:=\ker D \Pi(f,\zeta,\eta)$. From \[Dp,Dp2\] (the essential point here is that the map in \[Dp2\] preserves orthogonality) we get that $A^\perp= {\ensuremath{\left.D \Pi(f,\zeta,\eta)\right|_{W^\perp}}} \widehat{A}^\perp$. Hence, by \[Dp\_eq\], ${\ensuremath{\left.D{\widehat{\pi}}_1(f,\zeta,\eta)\right|_{\widehat{A}^\perp}}}  = {\ensuremath{\left.D\pi_1 (\Pi(f,\zeta,\eta))\right|_{A^\perp}}}\, {\ensuremath{\left.D \Pi(f,\zeta,\eta)\right|_{W^\perp}}}.$ Taking determinants on both sides shows the claim.

Condition of solving for h-eigenpairs {#se:condition}
=====================================

The two notions of condition
----------------------------

Suppose that $(f,\zeta,\eta)\in {{\bf W}}$, that is, $D\pi_1(f,\zeta,\eta)$ has full rank. The implicit function theorem tells us that $\pi_1$ is locally invertible in a neighborhood $U\subset~{{\bf V}}$ of $(f,\zeta,\eta)$. Let us denote the inverse map by ${\mathbb{G}}_{(f,\zeta,\eta)}:\pi_1(U)\to U$ and define the *solution map* $G_{(f,\zeta,\eta)} := \pi_2\circ {\mathbb{G}}_{(f,\zeta,\eta)}$. We define ${\left\lVert DG_{(f,\zeta,\eta)}(f) \right\rVert}$ as the *condition number of solving for h-eigenpairs with output in ${\mathscr{P}}$*.

If on the other hand $(f,\zeta,\eta)\in {\widehat{{\bf W}}}$, by the same reasoning, ${\widehat{\pi}}_1$ is locally invertible in neighborhood $\widehat{U}\subset{\widehat{{\bf V}}}$ of $(f,\zeta,\eta)$. Let $\widehat{{\mathbb{G}}}_{(f,\zeta,\eta)}:{\widehat{\pi}}_1(\widehat{U})\to \widehat{U}$ be the inverse map and similiarly as above define $\widehat{G}_{(f,\zeta,\eta)} := {\widehat{\pi}}_2\circ\widehat{{\mathbb{G}}}_{(f,\zeta,\eta)}$. We define ${\left\lVert D\widehat{G}_{(f,\zeta,\eta)}(f) \right\rVert}$ as the *condition number of solving for h-eigenpairs with output in ${ {\mathbb{S}}({\mathbb{C}}^n)\times{\mathbb{C}}}$*.

\[condition\_for\_eigenpairs\]

1.  Let $(f,\zeta,\eta)\in {{\bf W}}$ and $(\zeta,\eta)\in({\mathbb{C}}^n\backslash{\left\{0\right\}})\times{\mathbb{C}}$ denote a representative. We have $${\left\lVert DG_{(f,\zeta,\eta)}(f) \right\rVert}
    =  \frac{{\left\lVert \zeta \right\rVert}^d}{{\left\lVert \zeta,\eta \right\rVert}} {\left\lVert {\ensuremath{\left.D{\mathcal{F}}_f(\zeta,\eta)\right|_{(\zeta,\eta)^\perp}}}^{-1} \right\rVert} = \frac{{\left\lVert \zeta \right\rVert}}{{\left\lVert \zeta,\eta \right\rVert}} \mu(f,\zeta,\eta).$$

2.  For $(f,\zeta,\eta)\in {\widehat{{\bf W}}}$ we have $${\left\lVert D\widehat{G}_{(f,\zeta,\eta)}(f) \right\rVert}
    =  {\left\lVert {\ensuremath{\left.D{\mathcal{F}}_f(\zeta,\eta)\right|_{\zeta^\perp\times{\mathbb{C}}}}}^{-1} \right\rVert}$$ and, if ${\left\lVert f \right\rVert}=1$, the latter equals ${\widehat{\mu}}(f,\zeta,\eta)$.

3.  For all $(f,\zeta,\eta)\in{{\bf W}}_{\mathbb{S}}$ we have $${\left\lVert DG_{(f,\zeta,\eta)}(f) \right\rVert} \leq \mu(f,\zeta,\eta)\leq \sqrt{2}\cdot {\left\lVert DG_{(f,\zeta,\eta)}(f) \right\rVert}$$

4.  Let $\Pi:{ {\mathbb{S}}({\mathbb{C}}^n)\times{\mathbb{C}}}\to{\mathscr{P}}$ denote the canonical projection. For any $(f,\zeta,\eta)\in{\widehat{{\bf W}}}_{\mathbb{S}}$ we have $$\frac{1}{\sqrt{2}}\,{\widehat{\mu}}(f,\zeta,\eta)\leq \mu(f,\Pi(\zeta,\eta)) \leq {\widehat{\mu}}(f,\zeta,\eta)$$

\[rem1\]

1.  It is a useful exercise to check from \[condition\_for\_eigenpairs\] that ${\left\lVert DG_{(f,\zeta,\eta)}(f) \right\rVert}= {\left\lVert DG_{(f,s\zeta,s\eta)}(f) \right\rVert}$ for all $s\in{\mathbb{C}}^\times$.

2.  The homotopy method works with approximations of eigenpairs. This is why in the introduction we defined $\mu(f,v,\lambda)$ and ${\widehat{\mu}}(f,v,\lambda)$ for any triple $(f,v,\lambda)\in{{\mathcal{H}}}\times{\mathscr{P}}$ and $(f,v,\lambda)\in{{\mathcal{H}}}\times{ {\mathbb{S}}({\mathbb{C}}^n)\times{\mathbb{C}}}$, respectively (see \[mu\_def\]).

3.  We could have defined $\mu'(f,\zeta,\eta) ={\left\lVert DG_{(f,\zeta,\eta)}(f) \right\rVert} = \frac{{\left\lVert \zeta \right\rVert}}{{\left\lVert \zeta,\eta \right\rVert}} \mu(f,\zeta,\eta)$ to be the condition number, as well. The reason for our definition of $\mu(f,\zeta,\eta)$ is that it is easier to work with when proving the Lipschitz estimates, see \[lipschitz\_sec\].

4.  The statement in (4) requires ${\left\lVert f \right\rVert}=1$, because $\mu(f,v,\lambda)$ is defined to be an *absolute* condition number, whereas ${\widehat{\mu}}(f,v,\lambda)$ is a *relative* condition number.

5.  Proving a Lipschitz estimate for ${\widehat{\mu}}$ as in \[lipschitz\_sec\] is determined to fail. For $(f,\zeta,\eta)\in{\widehat{{\bf W}}}$ we have $\ker D{\mathcal{F}}_f(\zeta,\eta)^\perp=(\zeta,\eta)^\perp$ by Euler’s formular for homogeneous functions. Let $(v,1)\in \zeta^\perp\times {\mathbb{C}}$. Then on the one hand, since $\cos d_{\mathbb{P}}((\zeta,\eta),(v,1))= {\left\lvert \eta \right\rvert}/({\left\lvert v,1 \right\rvert}\sqrt{1+{\left\lvert \eta \right\rvert}}),$ the angle between $(\zeta,\eta)$ and $(v,1)$ can be arbitrarily small. On the other hand we have $(\zeta,\eta)\in v^\perp \times {\mathbb{C}}$ and hence ${\ensuremath{\left.D{\mathcal{F}}_f(\zeta,\eta)\right|_{v^\perp\times{\mathbb{C}}}}}$ is not invertible. This shows that small a small pertubation in $(\zeta,\eta)$ may lead to a large pertubation in ${\widehat{\mu}}(f,\zeta,\eta)$.

We prove the first claim. Put $G:=G_{(f,\zeta,\eta)}$, such that we have $DG: {{\mathcal{H}}}\to T_{(\zeta,\eta)}{\mathscr{P}}$. From \[tangent\_space\] we know that the tangent space of ${{\bf V}}$ at $(f,\zeta,\eta)$ equals $${\left\{(\dot{f},\dot{\zeta},\dot{\eta})\in {{\mathcal{H}}}\times T_{(\zeta,\eta)}{\mathscr{P}}\mid (\dot{\zeta},\dot{\eta})=-D{\mathcal{F}}_f(\zeta,\eta)|_{(\zeta,\eta)^\perp}^{-1} \dot{f}(\zeta)\right\}}.$$ Let $(\zeta,\eta)\in{ ({\mathbb{C}}^n\backslash{\left\{0\right\}})\times{\mathbb{C}}}$ denote a representative for $(\zeta,\eta)\in{\mathscr{P}}$. By [@condition eq. (14.10)] the induced norm on $T_{(\zeta,\eta)}{\mathscr{P}}$ is ${\left\lVert v \right\rVert}_{(\zeta,\eta)}= {\left\lVert v \right\rVert}/{\left\lVert \zeta,\eta \right\rVert}$. This shows that $${\left\lVert DG(f) \right\rVert}=\max\limits_{{\left\lVert \dot{f} \right\rVert} =1} {\left\lVert DG(f)\dot{f}\; \right\rVert}= {\left\lVert \zeta,\eta \right\rVert}^{-1} \max\limits_{{\left\lVert \dot{f} \right\rVert} =1} {\left\lVert D{\mathcal{F}}_f(\zeta,\eta)|_{(\zeta,\eta)^\perp}^{-1} \dot{f}(\zeta) \right\rVert}.$$ We get from [@condition Lemma 16.6] that the map ${{\mathcal{H}}}\to{\mathbb{C}}^n$, $\dot{f}\mapsto \dot{f}(\zeta)$ maps the unit ball in ${{\mathcal{H}}}$ onto the unit ball with radius ${\left\lVert \zeta \right\rVert}^d$ in ${\mathbb{C}}^n$. This shows the first assertion.

For the second assertion we can proceed similarly. \[tangent\_space\] tells us that the tangent space of ${\widehat{{\bf V}}}$ at $(f,\zeta,\eta)\in{\widehat{{\bf W}}}$ equals $${\left\{(\dot{f},\dot{\zeta}+ri\zeta,\dot{\eta})\in {{\mathcal{H}}}\times (\zeta^\perp\oplus {\mathbb{R}}i\zeta)\times {\mathbb{C}}\mid (\dot{\zeta},\dot{\eta})=-D{\mathcal{F}}_f(\zeta,\eta)|_{\zeta^\perp\times{\mathbb{C}}}^{-1}\cdot\dot{f}(\zeta)\right\}}.$$ Hence, ${\left\lVert D\widehat{G}(f) \right\rVert}=\max\limits_{{\left\lVert \dot{f} \right\rVert} =1} {\left\lVert D\widehat{G}(f)\dot{f}\; \right\rVert}= {\left\lVert D{\mathcal{F}}_f(\zeta,\eta)|_{\zeta^\perp\times{\mathbb{C}}}^{-1} \right\rVert},$ for the same reason as above.

For (3) we have ${\left\lVert \zeta,\eta \right\rVert}\,{\left\lVert DG_{(f,\zeta,\eta)}(f) \right\rVert} = {\left\lVert \zeta \right\rVert}\,\mu(f,\zeta,\eta)$ by part (1). The claim follows then from \[useful\_lemma2\].

For the fourth claim, abusing notation, we put $(\zeta,\eta):=\Pi(\zeta,\eta)$. We have $$\mu(f,\zeta,\eta) = {\left\lVert 
{\ensuremath{\left.D{\mathcal{F}}_f(\zeta,\eta)\right|_{(\zeta,\eta)^\perp}}}^{-1} \right\rVert}\leq {\left\lVert 
{\ensuremath{\left.D{\mathcal{F}}_f(\zeta,\eta)\right|_{\zeta^\perp \times {\mathbb{C}}}}}^{-1} \right\rVert} = {\widehat{\mu}}(f,\zeta,\eta),$$ the inequality by \[projection\_lemma\](3). Note that we have $\zeta^\perp \times {\mathbb{C}}= (\zeta,0)^\perp$. Then $${\widehat{\mu}}(f,\zeta,\eta) = {\left\lVert 
{\ensuremath{\left.D{\mathcal{F}}_f(\zeta,\eta)\right|_{\zeta^\perp\times {\mathbb{C}}}}}^{-1} \right\rVert}\leq \frac{1}{\cos \delta}\, {\left\lVert 
{\ensuremath{\left.D{\mathcal{F}}_f(\zeta,\eta)\right|_{(\zeta,\eta)^\perp}}}^{-1} \right\rVert} = \frac{\mu(f,\zeta,\eta)}{\cos \delta},$$ by \[projection\_lemma\], where $$\cos \delta=\cos d_{\mathbb{P}}((\zeta,0),(\zeta,\eta)) =  \frac{{\left\lvert \left\langle (\zeta,0),(\zeta,\eta)\right\rangle \right\rvert}}{{\left\lVert \zeta,0 \right\rVert}\,{\left\lVert \zeta,\eta \right\rVert}} = \frac{{\left\lVert \zeta \right\rVert}^2}{{\left\lVert \zeta \right\rVert}\,\sqrt{{\left\lVert \zeta \right\rVert}^2+{\left\lvert \eta \right\rvert}^2}}.$$ We have ${\left\lVert \zeta \right\rVert}=1$ and, since $(f,\zeta,\eta)\in{\widehat{{\bf W}}}_{\mathbb{S}}$, by \[useful\_lemma2\], we also have ${\left\lvert \eta \right\rvert}\leq~1$. This shows $\cos\delta \geq \frac{1}{\sqrt{2}}$.

We finish this subsection by giving some useful properties of the condition numbers $\mu(f,v,\lambda)$ and ${\widehat{\mu}}(f,v,\lambda)$.

\[2dmu\]

1.  For $(f,\zeta,\eta)\in{{\bf W}}_{\mathbb{S}}$ we have $1\leq 2d\,\mu(f,\zeta,\eta)$.

2.  For $(f,\zeta,\eta)\in{\widehat{{\bf W}}}$ we have$$1\leq d\,\left({\left\lVert f \right\rVert}+\max{\left\{{\left\lvert \eta \right\rvert}^{d-1},{\left\lvert \eta \right\rvert}^{d-2}\right\}}\right){\left\lVert {\ensuremath{\left.D{\mathcal{F}}_f(\zeta,\eta)\right|_{(\zeta,\eta)^\perp}}}^{-1} \right\rVert}.$$

3.  If $t\to (f_t,\zeta_t,\eta_t)$ is a curve in ${{\bf W}}_{\mathbb{S}}$, then ${\left\lVert \dot{\zeta_t},\dot{\eta_t} \right\rVert}\leq \mu(f,\zeta,\eta){\left\lVert \dot{f_t} \right\rVert}$.

4.  Let $U\in{\mathcal{U}}(n)$ . For all $(f,\zeta,\eta)\in{{\bf W}}$ we have $\mu(U.(f,\zeta,\eta))=\mu(f,\zeta,\eta)$ and for all $(f,\zeta,\eta)\in{\widehat{{\bf W}}}$ we have ${\widehat{\mu}}(U.(f,\zeta,\eta))={\widehat{\mu}}(f,\zeta,\eta)$

5.  For all $s\in{\mathbb{C}}^\times$ we have ${\widehat{\mu}}(s^{d-1}f,\zeta,s\eta)= {\widehat{\mu}}(f,\zeta,\eta)$.

The first claim follows from the second by choosing a representative $(\zeta,\eta)\in { {\mathbb{S}}({\mathbb{C}}^n)\times{\mathbb{C}}}$ and using from \[useful\_lemma2\] that ${\left\lvert \eta \right\rvert}\leq {\left\lVert \zeta \right\rVert}=1$.

Let us show the second assertion. From the submultiplicativity of the spectral norm we get $$1\leq {\left\lVert {\ensuremath{\left.D{\mathcal{F}}_f(\zeta,\eta)\right|_{(\zeta,\eta)^\perp}}}^{-1} \right\rVert} {\left\lVert D{\mathcal{F}}_f(\zeta,\eta) \right\rVert}$$ (see \[A3\]). Let $\partial_X$, $\partial_\Lambda$ denote the partial derivatives at $X$ and $\Lambda$, respectively. Then $$\begin{aligned}
{\left\lVert D{\mathcal{F}}_f(\zeta,\eta) \right\rVert}
&={\left\lVert \begin{bmatrix}\partial_X {\mathcal{F}}_f(X,\Lambda),& \partial_\Lambda {\mathcal{F}}_f(X,\Lambda\end{bmatrix} \right\rVert}_{(X,\Lambda)=(\zeta,\eta)}\nonumber\\
&={\left\lVert \begin{bmatrix}Df(\zeta)-\eta^{d-1}I_n,& -(d-1)\eta^{d-2}\zeta\end{bmatrix} \right\rVert}\nonumber\\
&\leq {\left\lVert Df(\zeta) \right\rVert} + {\left\lvert \eta \right\rvert}^{d-1} +(d-1){\left\lvert \eta \right\rvert}^{d-2}\label{2dmu.1};\end{aligned}$$ for the last line we have used the triangle inequality. From [@condition Lemma 16.46] we get ${\left\lVert Df(\zeta) \right\rVert}\leq d{\left\lVert f \right\rVert}$. This shows the second claim.

For (3) we take derivatives on both sides of $G_{(f_t,\zeta_t,\eta_t)}(f_t)=(\zeta_t,\eta_t)$ to get $DG_{(f_t,\zeta_t,\eta_t)}(f_t)(\dot{f_t}) = (\dot{\zeta_t},\dot{\eta_t})$, such that $${\left\lVert \dot{\zeta_t},\dot{\eta_t} \right\rVert} = {\left\lVert DG_{(f_t,\zeta_t,\eta_t)}(f_t)(\dot{f_t}) \right\rVert} \leq  {\left\lVert DG_{(f_t,\zeta_t,\eta_t)}(f_t) \right\rVert}\; {\left\lVert \dot{f_t} \right\rVert}.$$ Using \[condition\_for\_eigenpairs\](3) shows (2). Part (4) is a straightforward calculation.

Let us prove the fifth claim. First observe that ${\widehat{\mu}}(f,v,\lambda)<\infty$ if and only if ${\widehat{\mu}}(s^{d-1}f,v,s\lambda)<\infty$. From \[2dmu.1\] we have $$\begin{aligned}
D{\mathcal{F}}_{s^{d-1}f}(v,s\lambda)
&= \begin{bmatrix}s^{d-1}Df(v)-s^{d-1}\lambda^{d-1}I_n,& -(d-1)s^{d-2}\lambda^{d-2}v\end{bmatrix}\\
&=D{\mathcal{F}}_{f}(v,\lambda)\,\begin{bmatrix}
s^{d-1}I_{n}&0\\
0&s^{d-2}
\end{bmatrix}.\end{aligned}$$ Using that $$\label{eq_muhat}
D{\mathcal{F}}_{f}(v,\lambda) {\ensuremath{\left.\begin{bmatrix}
s^{d-1}I_{n}&0\\
0&s^{d-2}
\end{bmatrix}\right|_{v^\perp\times{\mathbb{C}}}}} ={\ensuremath{\left.D{\mathcal{F}}_{f}(v,\lambda)\right|_{v^\perp\times{\mathbb{C}}}}}
{\ensuremath{\left.\begin{bmatrix}
s^{d-1}I_{n}&0\\
0&s^{d-2}
\end{bmatrix}\right|_{v^\perp\times{\mathbb{C}}}}}$$ we obtain that $$\begin{aligned}
{\widehat{\mu}}(s^{d-1}f,\zeta,s\eta)=&{\left\lVert \begin{bmatrix}
{\left\lVert s \right\rVert}^{d-1}{\left\lVert f \right\rVert}I_{n}&0\\
0&{\left\lVert s \right\rVert}^{d-2}{\left\lVert f \right\rVert}^\frac{d-2}{d-1}
\end{bmatrix}
{\ensuremath{\left.D{\mathcal{F}}_{s^{d-1}f}(vs,\lambda)\right|_{v^\perp\times{\mathbb{C}}}}}^{-1} \right\rVert}\\
=&{\left\lVert \begin{bmatrix}
{\left\lVert f \right\rVert}I_{n}&0\\
0&{\left\lVert f \right\rVert}^\frac{d-2}{d-1}
\end{bmatrix}
{\ensuremath{\left.D{\mathcal{F}}_{f}(v,\lambda)\right|_{v^\perp\times{\mathbb{C}}}}}^{-1} \right\rVert}\\[0.2cm]
 = &\;{\widehat{\mu}}(f,\zeta,\eta).\end{aligned}$$

\[rem2\] The proof above shows why the condition number $\mu(f,v,\lambda)$ does not scale properly with $f$. In fact, we cannot adapt equation \[eq\_muhat\] to $\mu(f,v,\lambda)$. In general we have $$D{\mathcal{F}}_{f}(v,\lambda) {\ensuremath{\left.\begin{bmatrix}
s^{d-1}I_{n}&0\\
0&s^{d-2}
\end{bmatrix}\right|_{(v,\lambda)^\perp}}} \neq {\ensuremath{\left.D{\mathcal{F}}_{f}(v,\lambda)\right|_{(v,\lambda)^\perp}}}
{\ensuremath{\left.\begin{bmatrix}
s^{d-1}I_{n}&0\\
0&s^{d-2}
\end{bmatrix}\right|_{v^\perp\times{\mathbb{C}}}}}$$

Lifting of paths in ${\mathcal{H}}$.
------------------------------------

Suppose that we are given some $(f,\zeta,\eta)\in {{\bf V}}$ and $g\in{{\mathcal{H}}}$. Let $E_{f,g}$ be a path connecting $f$ and $g$. If $E_{f,g}\cap \Sigma=\emptyset$, then the solution map ${\mathbb{G}}$ is defined everywhere on $E_{f,g}$. If this is the case, there exists a unique path $L_{f,g}\subset {{\mathcal{H}}}\times{\mathbb{P}}({\mathbb{C}}^n\times {\mathbb{C}})$, called the *lifting*, connecting $(f,\zeta,\eta)$ with some $(g,\xi,\nu)$, where ${\mathcal{F}}_g(\xi,\nu)=0$. The following shows that $L_{f,g}$ does not contain the trivial solution, that is $[0:1]\not\in \pi_2(L_{f,g})$.

\[prop\_approx\_eigenpairs\] Let $(f,\zeta,\eta)\in {{\bf W}}$ and $g\in{\mathbb{S}}({{\mathcal{H}}})$. Let $E_{f,g}$ be some path connecting $f$ and $g$ and suppose that $E_{f,g}\cap\Sigma=\emptyset$. Let $L_{f,g}$ be the lifting of $E_{f,g}$ to ${{\bf V}}$ at $(f,\zeta,\eta)$. Then $L_{f,g}\subset{{\bf V}}$.

As before, one easily verifies that for any $f\in{{\mathcal{H}}}$ we have $D{\mathcal{F}}_f(0,1)=[-I_n,0]$, which is a matrix of full rank. Hence, the solution map ${\mathbb{G}}$ at $(f,0,1)$ is defined. \[prop\_approx\_eigenpairs\] follows from the fact that $G:=\pi_2\circ{\mathbb{G}}$ is constant, which we prove next.

 

\[derivative\_G\] Let $f\in ({\mathcal{H}}_d)^n\backslash{\mathbf{\Sigma}}$ and ${\mathbb{G}}$ be the local inverse of $\pi_1$ at $(f,0,1)$. Put $G:=\pi_2\circ {\mathbb{G}}$. Then $DG(f)=0$.

We obtain $\frac{\partial {\mathcal{F}}_f}{\partial f}(f,0,1) + [-I_n,0]  DG(f) =0$ by derivating the equation ${\mathcal{F}}_f(G(f))=0$ at $f$. Observe that $\frac{\partial {\mathcal{F}}_f}{\partial f}(f,0,1)=0$. This shows that $[-I_n,0]DG(f)=0$. However, $DG(f)$ is a map from ${{\mathcal{H}}}\to (0,1)^\perp$. Since $(0,1)^\perp \cap ({\left\{0\right\}}\times{\mathbb{C}})={\left\{0\right\}}$ we see that actually $DG(f)=0$.

 

The adaptive linear homotopy method {#se:newton}
===================================

Newton method and approximate eigenpairs
----------------------------------------

Let $f\in{{\mathcal{H}}}$. The Newton operator for the h-eigenpair problem with respect to $f$ is the usual Newton operator associated to ${\mathcal{F}}_f:{\mathbb{C}}^n\times{\mathbb{C}}\to {\mathbb{C}}^n$, that is $$\begin{aligned}
    N&_f: \quad{\mathscr{P}}\to {\mathscr{P}}\\
    &(v,\lambda)\mapsto\begin{cases}(v,\lambda)-D{\mathcal{F}}_f(v,\lambda)|_{(v,\lambda)^\perp}^ {-1} {\mathcal{F}}_f(v,\lambda),&\text{if } D{\mathcal{F}}_f(v,\lambda)|_{(v,\lambda)^\perp} \text{ invertible} \\ (v,\lambda),&\text{else}.\end{cases}
    \end{aligned}$$ It is an easy exercise to show that $N_f$ is well defined rational map and that the image of $N_f$ is contained in ${\mathscr{P}}$. The following definition was already made in the introduction and is [@condition Def. 16.34] specialized to our scenario.

\[def\_approx\_eigenpair\] Let $(f,\zeta,\eta)\in{{\bf V}}$. We say that $(v,\lambda)\in{\mathscr{P}}$ is an *approximate eigenpair* of $f$ with associated h-eigenpair $(\zeta,\eta)$, if $$\forall i\geq 0: \; d_{\mathbb{P}}((v_i,\lambda_i),(\zeta,\eta))\leq \frac{1}{2^{2^i-1}} d_{\mathbb{P}}((v,\lambda),(\zeta,\eta)).$$ where $(v_0,\lambda_0)=(v,\lambda)$ and $(v_i,\lambda_i)=N_f(v_{i-1},\lambda_{i-1}), i\geq 1$.

In fact approximate eigenpairs are approximate zeros of $f$ (in the sense of [@condition Def. 16.34]) whose associated zero is an h-eigenpair.

We can measure the size of basins of attraction of the Newton method by the use of the following functions. As in [@condition p. 316] we define $$\label{psi}
\Psi_\delta(u):=(1+\cos\delta)(1-u)^2-1,\; u,\delta\in{\mathbb{R}}.$$ For $0<r<\pi/2$ we define $$\label{u_and_delta}
\delta(r):=\min\limits_{\delta>0} {\left\{\sin\delta =r\cdot \delta\right\}}\;\text{and}\;u(r):=\min\limits_{u>0}{\left\{ 2u=r\Psi_{\delta(r)}(u)\right\}}.$$ The following theorem is [@condition Theorem 16.38] specialized to our scenario.

\[gamma\_thm\] Fix $\frac{2}{\pi} \leq r < 1$. Let $(f,\zeta,\eta)\in {{\bf W}}$ and $(v,\lambda)\in{\mathscr{P}}$ be such that $d_{\mathbb{P}}((\zeta,\eta),(v,\lambda)) \leq \delta(r)$ and $d_{\mathbb{P}}((\zeta,\eta),(v,\lambda))\; \gamma(f,\zeta,\eta)\leq u(r),$ where $$\gamma(f,\zeta,\eta):={\left\lVert \zeta,\eta \right\rVert}\;\max\limits_{k\geq 2} {\left\lVert \frac{1}{k!}\; D{\mathcal{F}}_f(\zeta,\eta)|_{(\zeta,\eta)^\perp}^{-1} \; D^k{\mathcal{F}}_f(\zeta,\eta) \right\rVert}^\frac{1}{k-1}.$$ Then $(v,\lambda)$ is an approximate eigenpair of $(\zeta,\eta)$.

Note that this is the same $\gamma$ as in [@condition Def. 16.35], the only difference being the naming $\gamma(f,\zeta,\eta)$, which in [@condition Def. 16.35] would be called $\gamma({\mathcal{F}}_f,(\zeta,\eta))$.

It turns out that, if ${\left\lVert f \right\rVert}=1$, then $\gamma(f,\zeta,\eta)$ can be bounded from above by the condition number, that we introduced in \[mu\_def\]. The following is a version of the higher derivative estimate, compare [@condition Theorem 16.1]. Its proof is postponed to \[condition\_number\_thm\_proof\].

\[Theorem\_4.3\] For $(f,\zeta,\eta)\in{{\bf V}}_{\mathbb{S}}$ we have $\gamma(f,\zeta,\eta)\leq \mu(f,\zeta,\eta) \; d^2 \; \sqrt{2n} .$

The algorithm <span style="font-variant:small-caps;">e-alh</span>
-----------------------------------------------------------------

Let $\Theta(\epsilon)$ denote the function $[0,1) \to {\mathbb{R}},\; \epsilon\mapsto \epsilon+(1-\epsilon)^{-2}-\cos(\epsilon/4)$ and for $f,g\in{\mathbb{S}}({{\mathcal{H}}})$, $f\neq -g$, let $E_{f,g}$ denote the geodesic path between $f$ and $g$.

[|ll|]{}\
\
\
1. & $\epsilon \leftarrow 0.04$,$\omega\leftarrow 2\Theta(\epsilon)-1$.\
2. & $\tau\leftarrow 0,\quad q\leftarrow g,\quad v\leftarrow \zeta,\quad \lambda\leftarrow \eta,\quad \alpha\leftarrow d_{\mathbb{S}}(f,g)$.\
3. & [**repeat**]{}\
4. & $\Delta\, \tau \leftarrow \epsilon (1-\epsilon)^4 \omega \Theta(\epsilon)/ \left[4\;d^{2} \sqrt{n}\; \mu^2(q,v,\lambda)\;\alpha\right]$\
5. & $\tau\leftarrow\min{\left\{1,\tau+\Delta\,\tau\right\}}$.\
6. & $q\leftarrow$ point on the geodesic path from $f$ to $g$ with $d_{\mathbb{S}}(f,g)=\tau\alpha$.\
7. & $(v,\lambda) \leftarrow N_q(v,\lambda)$.\
8. & [**until**]{} $t=1$.\
9. & [**return**]{} $(v,\lambda)$ [**and halt.**]{}\
\
\

 \
We denote by $K(f,(g,\zeta,\eta))$ the number of iterations that <span style="font-variant:small-caps;">e-alh</span> performs on inputs $f\in{{\mathcal{H}}}$, $(g,\zeta,\eta)\in {{\bf V}}_{\mathbb{S}}$.

\[Theorem\_4.4\] If $E_{f,g}\cap{\mathbf{\Sigma}}=\emptyset$, algorithm <span style="font-variant:small-caps;">alh</span> terminates and the output $(v,\lambda)$ is an approximate eigenpair of $f$. $$K(f,(g,\zeta,\eta))\leq 246\;d^2\sqrt{n}\; d_{\mathbb{S}}(f,g)\;\int_0^1\mu^2(q_\tau,\zeta_\tau,\eta_\tau) {\mathrm{d}}\tau,$$ where ${\left\{(q_\tau,\zeta_\tau,\eta_\tau)\mid 0\leq \tau\leq 1\right\}}$ denotes the lifting of $E_{f,g}$ at $(g,\zeta,\eta)$.

The proof of \[Theorem\_4.4\] is postponed to \[ALH-proof\].

\[notation\_C\] We denote ${\mathcal{C}}(f,(g,\zeta,\eta)) :=\int_0^1\mu^2(q_\tau,\zeta_\tau,\eta_\tau) {\mathrm{d}}\tau,$ where $f$ and $(g,\zeta,\eta)$ are as in \[Theorem\_4.4\].

\[approx\_rem\] Algorithm <span style="font-variant:small-caps;">e-alh</span> not only can find approximations of h -eigenpairs, but also approximations of eigenvectors. To see this, let $(f,\zeta,\eta)\in{{\bf V}}_{\mathbb{S}}$ be the input of algorithm <span style="font-variant:small-caps;">e-alh</span> and suppose that we have found $(v,\lambda)\in {\mathbb{P}}({\mathbb{C}}^n\times{\mathbb{C}})$ with $\delta:=d_{\mathbb{P}}((\zeta,\eta),(v,\lambda)) < \frac{\pi}{16}.$ Let $(\zeta,\eta),(v,\lambda)\in{ {\mathbb{S}}({\mathbb{C}}^n)\times{\mathbb{C}}}$ also denote representatives with $\delta= d_{\mathbb{S}}((\zeta,\eta),(v,\lambda))$. We have ${\left\lvert \eta \right\rvert}\leq 1$ by \[useful\_lemma2\] and \[real\_geometry\_prop\] implies $\delta\geq \frac{{\left\lVert \zeta-v,\eta-\lambda \right\rVert}}{\sqrt{8}} \geq \frac{{\left\lVert \zeta-v \right\rVert}}{\sqrt{8}}.$ Since $\zeta,\eta\in{\mathbb{S}}({\mathbb{C}}^n)$, we have ${\left\lVert \zeta-v \right\rVert}\geq \sin d_{\mathbb{S}}(\zeta,\eta)\geq \sin d_{\mathbb{P}}(\zeta,\eta)$. Using that for all $0\leq \phi\leq \frac{\pi}{2}$ we have $\sin\phi \geq \frac{2}{\pi}\phi$, we obtain $$d_{\mathbb{P}}((\zeta,\eta),(v,\lambda))=\delta \geq \frac{2}{\pi\sqrt{8}}\; d_{\mathbb{P}}(\zeta,\eta).$$ In other words, if $(v,\lambda)$ approximates $(\zeta,\eta)$, then $v$ approximates $\zeta$.

The algorithm <span style="font-variant:small-caps;">lv e-alh</span>
--------------------------------------------------------------------

For a randomized version of algorithm <span style="font-variant:small-caps;">e-alh</span> we need to define a probability distribution on ${{\bf V}}_{\mathbb{S}}$. We proceed as in [@distr sec. 3.5], where we adapted the ideas from [@condition sec. 17.5]. \[prop\_eigendiscriminant\] tells us that, if $f\not\in{\mathbf{\Sigma}}$, then $f$ has ${\mathcal{D}}(n,d)=d^n-1$ many h-eigenpairs, and that ${\mathbf{\Sigma}}$ is a proper algebraic subvariety of ${{\mathcal{H}}}$. Thus almost surely a random polynomial system has ${\mathcal{D}}(n,d)$ many h-eigenpairs. The procedure

1.  Choose $g\in{\mathbb{S}}({\mathcal{H}}_d^n)$ uniformly at random.

2.  Choose $(\zeta,\eta)$ uniformly from the ${\mathcal{D}}(n,d)$ many eigenpairs of $g$.

therefore yields a probability distribution on ${{\bf V}}_{\mathbb{S}}$, whose density we denote by $\rho$. As in [@condition sec. 17.5] one shows $$\rho(g,\zeta,\eta)= \frac{\mathrm{NJ}(\pi_1)(g,\zeta,\eta)}{{\mathcal{D}}(n,d) \;  \mathrm{vol}\;{\mathbb{S}}({{\mathcal{H}}})}.$$ Here $\mathrm{NJ}$ denotes the normal jacobian, see [@condition sec. 17.3] or \[A4\]. The algorithm <span style="font-variant:small-caps;">las vegas e-alh</span> or <span style="font-variant:small-caps;">lv e-alh</span>, shortly, is as follows.

[|ll|]{}\
\
\
1. & Choose $(g,\zeta,\eta)\in{{\bf V}}$ with density $\rho$.\
2. & Start algorithm <span style="font-variant:small-caps;">e-alh</span> with inputs $(g,\zeta,\eta)$ and $f$.\
3.& Set $(v,\lambda) \leftarrow$.\
4.& **return** $(v,\lambda)$.\
\
\

 \

\[postconditions\] \[prop\_eigendiscriminant\] tells us that ${\mathbf{\Sigma}}$ is a projective variety of real codimension at least 2. So the geodesic path between two random points $f,g\in{\mathbb{S}}({{\mathcal{H}}})$ almost surely does not intersect ${\mathbf{\Sigma}}$. This shows that for almost all inputs $f\in {\mathbb{S}}({{\mathcal{H}}})$ the postconditions of <span style="font-variant:small-caps;">lv e-alh</span> are fulfilled.

A little care should be taken here. We have not given an algorithm to draw from $\rho$. And, unfortunately, we are not able to provide such an algorithm. But we can provide an average analysis for it and this will be relevant for the analysis of the subsequent true randomized algorithm <span style="font-variant:small-caps;">lv-alh</span>\*, see \[Theorem\_4.8\].

The proof of the following theorem is postponed to \[sec:avg\_anal\].

\[Theorem\_4.6\] We have $$\operatorname*{\mathbb{E}}\limits_{f \sim\mathrm{Unif}\;{\mathbb{S}}({\mathcal{H}}_d^n)}\; \operatorname*{\mathbb{E}}\limits_{(g,\zeta,\eta)\sim\rho} \; {\mathcal{C}}(f,(g,\zeta,\eta)) <   \frac{80\,nN}{d}.$$ Here $\mathrm{Unif}\;{\mathbb{S}}({{\mathcal{H}}})$ denotes the uniform distribution on ${\mathbb{S}}({{\mathcal{H}}})$ and ${\mathcal{C}}$ is as in \[notation\_C\].

The algorithm <span style="font-variant:small-caps;">lv e-alh</span>\*
----------------------------------------------------------------------

Let $W$ denote some hermitian vector space. We say that a random variable $z\in W$ is distributed according to the *standard distribution*, denoted by $N(W)$, if it is distributed with density $$\label{dens_W}
    \pi^{-k} \exp(-{\left\lVert z \right\rVert}^2),\;k:=\dim_{\mathbb{C}}W,$$ see also \[A1\].

Let $e_1:=(1,0,\ldots,0)\in{\mathbb{C}}^n$. We now describe an algorithm that defines another probability density function on ${{\bf V}}$, which we denote by $\rho^*$. The idea for this algorithm is an adaption of [@matrix_eigenpair sec. 10.1].

[|ll|]{}\
\
\
1.& Draw ${\mathbbm{f}}\sim N({\mathcal{H}}_{n,d}^{n-1})$ and $\zeta\in{\mathbb{P}}({\mathbb{C}}^n)$ from the $d^{n-1}$ many zeros of ${\mathbbm{f}}$.\
2.& Draw $a \sim N(\zeta^\perp)$ and $h\sim N(R(\zeta))$, where $R(\zeta)$ is as in \[orthogonal\_decomposition\].\
3.& Draw $U\in{\mathcal{U}}(n)$, such that $Ue_1=\zeta$, uniformly at random.\
4. & Draw $R$ with density $e^{-R}\;\mathbf{1}_{{\left\{R\geq 0\right\}}}(R)$.\
5. & Choose $\phi\in[0,2\pi)$ uniform at random.\
6. & Put $\eta:=R^\frac{1}{2(d-1)} \exp(i\phi)$.\
7. & Define $P_\zeta^\perp$ as the orthogonal projection onto $\zeta^\perp$.\
8. & [**if**]{} ${\left\lVert D\,{\mathbbm{f}}(\zeta)+\eta^{d-1}P_{\zeta^\perp} \right\rVert}_F \geq {\left\lVert D\,{\mathbbm{f}}(\zeta) \right\rVert}_F$\
9. & Delete $\eta,\phi$ and $R$ and go to 4.\
10. & [**else**]{}\
11. & Put ${\mathbbm{f}}_0:=\eta^{d-1} \;\langle X,\zeta\rangle^d + \sqrt{d}\;\langle X,\zeta\rangle^{d-1} a^T X + h$.\
12.& Put $f:=U\cdot \begin{bmatrix}  {\mathbbm{f}}_0,& {\mathbbm{f}}\end{bmatrix}^T$.\
13.& [**return:**]{} $(f,\zeta,\eta)\in {{\bf V}}$.\

 \
We have constructed ${\mathbbm{f}}$, such that by \[orthogonal\_decomposition\], ${\mathbbm{f}}_0(\zeta)=\eta^{d-1}$ and therefore $f(\zeta)=U \zeta^{d-1}e_1=\eta^{d-1}\zeta$. This shows that algorithm <span style="font-variant:small-caps;">draw-from-</span>$\rho^*$ works correctly. The advantage of $\rho^*$ when compared to $\rho$ is that we can implement drawing from $\rho^*$ efficiently using a random number generator that can draw from the standard normal distribution $N({\mathbb{C}})$.

The proof of the following is postponed to \[sec:Theorem\_4.7\].

\[Theorem\_4.7\] We assume to have random number generator that can draw von $N({\mathbb{C}})$ in ${\mathcal{O}}(1)$. We count this draws as arithmetic operations. Then the algorithm <span style="font-variant:small-caps;">draw-from-</span>$\rho^*$ can be implemented such that its expected number of arithmetic operations is ${\mathcal{O}}(dnN)$, where $N:=\dim_{\mathbb{C}}({{\mathcal{H}}})$.

The algorithm <span style="font-variant:small-caps;">draw-from-</span>$\rho^*$ can be used to generate a starting system for the algorithm <span style="font-variant:small-caps;">e-alh</span>. We call the resulting algorithm <span style="font-variant:small-caps;">lv e-alh</span>\*.\

[|ll|]{}\
\
\
1. & Run <span style="font-variant:small-caps;">draw-from-</span>$\rho^*$.\
2. & Set $(g,\zeta,\eta)\leftarrow $ output of <span style="font-variant:small-caps;">draw-from-</span>$\rho^*$.\
3. & Start algorithm <span style="font-variant:small-caps;">e-alh</span> with inputs $({\left\lVert g \right\rVert}^{-1}g,\zeta,{\left\lVert g \right\rVert}^\frac{-1}{d-1}\eta)$ and $f$\
& (algorithm <span style="font-variant:small-caps;">e-alh</span> requires $g\in{\mathbb{S}}({\mathcal{H}})$ as input.).\
4. & Set $(v,\lambda) \leftarrow$ output of <span style="font-variant:small-caps;">e-alh</span>.\
5. & **return** $(v,\lambda)$.\
\
\

 \
We can use the average analysis of algorithm <span style="font-variant:small-caps;">lv e-alh</span> given in \[Theorem\_4.6\] to analyze <span style="font-variant:small-caps;">lv e-alh</span>\*. The proof of \[Theorem\_4.8\] below is postponed to \[sec:rho\_star\].

\[Theorem\_4.8\] We have $$\begin{aligned}
&\operatorname*{\mathbb{E}}\limits_{f \sim \mathrm{Unif}\,{\mathbb{S}}({{\mathcal{H}}})}\operatorname*{\mathbb{E}}\limits_{(g,\zeta,\eta)\sim \rho^*} {\mathcal{C}}(f,(g,\zeta,\eta))\leq \frac{5\sqrt{\pi}\,n}{d}\operatorname*{\mathbb{E}}\limits_{f\sim \mathrm{Unif}\,{\mathbb{S}}({{\mathcal{H}}})}\operatorname*{\mathbb{E}}\limits_{(g,\zeta,\eta)\sim \rho} {\mathcal{C}}(f,(g,\zeta,\eta)).\end{aligned}$$

Now we have gathered all the ingredients to prove \[main\_thm\].

We prove that algorithm <span style="font-variant:small-caps;">lv e-alh</span>\* has the properties stated. First, note that from \[postconditions\] we get that algorithm <span style="font-variant:small-caps;">lv e-alh</span>\* terminates almost surely.

By \[Theorem\_4.7\] the expected number of arithmetic operations of algorithm <span style="font-variant:small-caps;">draw-from-</span>$\rho^*$ is ${\mathcal{O}}(dnN)$.

Now we turn to the analysis of algorithm <span style="font-variant:small-caps;">e-alh</span>. The cost of every iteration in algorithm <span style="font-variant:small-caps;">e-alh</span> is dominated by the costs of evaluating $N_f(v,\lambda)$, which by [@condition Prop. 16.32] is ${\mathcal{O}}(N)$. Combining \[Theorem\_4.8\] with \[Theorem\_4.6\] we see that $$\operatorname*{\mathbb{E}}\limits_{f \sim \mathrm{Unif}\,{\mathbb{S}}({{\mathcal{H}}})}\operatorname*{\mathbb{E}}\limits_{(g,\zeta,\eta)\sim \rho^*} {\mathcal{C}}(f,(g,\zeta,\eta)) \leq  \frac{400\sqrt{\pi}\,n^2N}{d^2}.$$ From \[Theorem\_4.4\] we get that the expected number of iterations algorithm <span style="font-variant:small-caps;">e-alh</span> is at most $$\begin{aligned}
    &\operatorname*{\mathbb{E}}\limits_{f \sim \mathrm{Unif}\,{\mathbb{S}}({{\mathcal{H}}})}\operatorname*{\mathbb{E}}\limits_{(g,\zeta,\eta)\sim \rho^*} K(f,(g,\zeta,\eta))\\
    \leq \hspace{0.5cm}&246\;d^2\sqrt{n}\; d_{\mathbb{S}}(f,g)\, \operatorname*{\mathbb{E}}\limits_{f \sim \mathrm{Unif}\,{\mathbb{S}}({{\mathcal{H}}})}\operatorname*{\mathbb{E}}\limits_{(g,\zeta,\eta)\sim \rho^*} {\mathcal{C}}(f,(g,\zeta,\eta))   \\
    \leq \hspace{0.5cm}& 98400 \sqrt{\pi}\,n^\frac{5}{2}\,N\,d_{\mathbb{S}}(f,g)
    \end{aligned}$$ Using that $d_{\mathbb{S}}(f,g)\leq \frac{\pi}{2}$ we see that the expected number of iterations of <span style="font-variant:small-caps;">e-alh</span> is ${\mathcal{O}}(n^\frac{5}{2}N)$ and hence the expected number of arithmetic operations of algorithm <span style="font-variant:small-caps;">e-alh</span> is ${\mathcal{O}}(n^\frac{5}{2}N^2)$.

We have shown that the expected number of arithmetic operations of <span style="font-variant:small-caps;">lv e-alh</span>\* is ${\mathcal{O}}(dnN+n^\frac{5}{2}N^2)$.

Integration on the solution manifold
====================================

In this section we prove a technical lemma, that is used several times throughout the paper.

For a measurable map $\Xi:{{\bf V}}\to {\mathbb{R}}$ we put $$\label{f_av_dfn}
\Xi_\mathrm{\;av}(f):=\frac{1}{{\mathcal{D}}(n,d)}\; \sum_{(\zeta,\eta)\in{\mathscr{P}}: f(\zeta)=\eta^{d-1}\eta} \Xi(f,\zeta,\eta).$$ The following is similiar to [@distr Lemma 3.10].

\[integration\] Suppose that $\Xi:{{\bf V}}\to{\mathbb{R}}$ is a measurable and unitarily invariant function; that is, for all $U\in{\mathcal{U}}(n)$ we have $\Xi(U.(f,\zeta,\eta))=\Xi(f,\zeta,\eta).$ Let $I_{n-1}$ denote the $(n-1)\times(n-1)$ identity matrix. Then $$\operatorname*{\mathbb{E}}\limits_{f\sim N({{\mathcal{H}}})}\Xi_\text{av}(f)
= \frac{(d-1)^2\mathrm{vol}\;{\mathbb{S}}({\mathbb{C}}^n)}{2\pi^{n+1}{\mathcal{D}}(n,d)} \int\limits_{\eta\in{\mathbb{C}}} E(\eta)\; {\left\lvert \eta \right\rvert}^{2(d-2)}\; e^{-{\left\lvert \eta \right\rvert}^{2(d-1)}} {\mathrm{d}}\eta,$$ where $$E(\eta):= \operatorname*{\mathbb{E}}\limits_{A,a,h}\; \Xi(f,e_1,\eta) {\left\lvert \det(\sqrt{d}A-\eta^{d-1}I_{n-1}) \right\rvert}^2,$$ with $A\sim N({\mathbb{C}}^{(n-1)\times(n-1)})$, $a\sim N({\mathbb{C}}^{n-1})$ an $h\sim N(R(e_1)^n)$ and $f$ is given as $$f= \eta^{d-1}X_1^d e_1 + \sqrt{d}X_1^{d-1}\begin{bmatrix} a^T\\ A\end{bmatrix} (X_2,\ldots,X_n)^T + h.$$

Let ${\mathcal{D}}:={\mathcal{D}}(n,d)=d^n-1$. Applying the coarea formula (\[coarea\_formula\]) to the projection $\pi_1:{{\bf V}}\to {{\mathcal{H}}}$ we have $$\begin{aligned}
\operatorname*{\mathbb{E}}\limits_{f\sim N({{\mathcal{H}}})}\Xi_\text{av}(f)\stackrel{\text{ by definition}}{=} &\int\limits_{f\in{{\mathcal{H}}}}\; \Xi_\mathrm{av}(f)\;\varphi_{{{\mathcal{H}}}}(f) {\mathrm{d}}{{\mathcal{H}}}\\
=\hspace{0.7cm}&\frac{1}{{\mathcal{D}}}\int\limits_{(f,\zeta,\eta)\in{{\bf V}}}\; \Xi(f,\zeta,\eta)\;\mathrm{NJ}\pi_1(f,\zeta,\eta)\;\varphi_{{{\mathcal{H}}}}(f) {\mathrm{d}}{{\bf V}}.\end{aligned}$$ Let $\Pi: {\widehat{{\bf V}}}\to {{\bf V}}$ denote the canonical projection. For any $f\in{{\mathcal{H}}}\backslash{\mathbf{\Sigma}}$ the preimage $(\pi_1\circ\Pi)^{-1}(f)$ consists of ${\mathcal{D}}:={\mathcal{D}}(n,d)$ disjoint circles, each of which has volume $2\pi$. From \[cor\_jacobian\_proj\](2) we know that $$\mathrm{NJ}(\pi_1)\Pi(f,\zeta,\eta)\mathrm{NJ}(\Pi)(f,\zeta,\eta)  = \mathrm{NJ}({\widehat{\pi}}_1)(f,\zeta,\eta).$$ Applying the coarea formula to $\Pi: {\widehat{{\bf V}}}\to {{\bf V}}$ therefore yields $$\label{integration1}
    \operatorname*{\mathbb{E}}\limits_{f\sim N({{\mathcal{H}}})}\Xi_\text{av}(f) = \frac{1}{2\pi{\mathcal{D}}} \int\limits_{(f,\zeta,\eta)\in{\widehat{{\bf V}}}} \Xi(f,\zeta,\eta) \; \mathrm{NJ}(\hat\pi_1)(f,\zeta,\eta) \; \varphi_{{{\mathcal{H}}}}(f) {\mathrm{d}}{\widehat{{\bf V}}}.$$ We know that $\mathrm{NJ}(\hat\pi_1)(f,\zeta,\eta)\; \mathrm{NJ}(\hat\pi_2)(f,\zeta,\eta)^{-1}  = {\left\lvert \det {\ensuremath{\left.D{\mathcal{F}}_f(\zeta,\eta)\right|_{\zeta^\perp\times {\mathbb{C}}}}} \right\rvert}^2$ from \[cor\_jacobian\_proj\](1). Applying the coarea formula to the projection ${\widehat{\pi}}_2$ yields

$$\begin{aligned}
\label{integration2}
\int\limits_{(f,\zeta,\eta)\in{\widehat{{\bf V}}}} \Xi(f,\zeta,\eta)  \mathrm{NJ}(\hat\pi_1)(f,\zeta,\eta) \varphi_{{{\mathcal{H}}}}(f) {\mathrm{d}}{\widehat{{\bf V}}}=&\int\limits_{\stackrel{(\zeta,\eta)\in}{{ {\mathbb{S}}({\mathbb{C}}^n)\times{\mathbb{C}}}}} K(\zeta,\eta) {\mathrm{d}}({ {\mathbb{S}}({\mathbb{C}}^n)\times{\mathbb{C}}})\end{aligned}$$

where $$\label{integration4}
K(\zeta,\eta):= \int\limits_{f\in {\widehat{\pi}}_2^{-1}(\zeta,\eta)} \Xi(f,\zeta,\eta) \, {\left\lvert \det {\ensuremath{\left.D{\mathcal{F}}_f(\zeta,\eta)\right|_{\zeta^\perp\times {\mathbb{C}}}}} \right\rvert}^2 \, \varphi_{{{\mathcal{H}}}}(f)\, {\mathrm{d}}{\widehat{\pi}}_2^{-1}(\zeta,\eta).$$

For $(\zeta,\eta)\in{\mathbb{S}}({\mathbb{C}}^n)\times {\mathbb{C}}$ we have $$\label{integration5}
    K(\zeta,\eta)=\frac{(d-1)^2}{\pi^n}\; E(\eta)\;{\left\lvert \eta \right\rvert}^{2(d-2)}\;e^{-{\left\lvert \eta \right\rvert}^{2(d-1)}}.$$

If the claim is true, observe that the expectation in \[integration5\] is independent of $\zeta$. We plug into \[integration2\] and the result into \[integration1\] and integrate over $\zeta\in{\mathbb{S}}({\mathbb{C}}^n)$ to obtain $$\operatorname*{\mathbb{E}}\limits_{f\sim N({{\mathcal{H}}})}\Xi_\text{av}(f)
=  \frac{(d-1)^2 \;\mathrm{vol}\;{\mathbb{S}}({\mathbb{C}}^n)}{2\pi^{n+1}{\mathcal{D}}} \int\limits_{\eta\in{\mathbb{C}}}E(\eta)\;{\left\lvert \eta \right\rvert}^ {2(d-1)}\;e^{-{\left\lvert \eta \right\rvert}^{2(d-1)}} {\mathrm{d}}\eta,$$ which shows the assertion.

<span style="font-variant:small-caps;">Proof of the claim</span> By assumption $\Xi$ is unitarily invariant. Moreover, $\hat\pi_1,\hat\pi_2$ are ${\mathcal{U}}(n)$-equivariant and we have $\varphi_{{\mathcal{H}}}(U.f) = \varphi_{{\mathcal{H}}}(f)$, because ${\mathcal{U}}(n)$ acts by isometries. This shows that $K(\zeta,\eta)=K(e_1,\eta)$.

Let $R:={\left\{h\in {\mathcal{H}}\mid h(e_1)=0, Dh(e_1)=0\right\}}$ be the space of systems vanishing to higher order at $e_1$. By \[orthogonal\_decomposition\] for any $f\in{\widehat{\pi}}_2^{-1}(e_1,\eta)$ there exist uniquely determined $h\in R^n$ and $M\in {\mathbb{C}}^{n \times (n-1)}$ such that we can orthogonally decompose $f$ as $$\label{aa2}
    f = \eta^{d-1} X_1^d e_1 + X_1^{d-1} \sqrt{d}M   (X_2,\ldots,X_n)^T +h,$$ and ${\left\lVert f \right\rVert}^2 = {\left\lvert \eta \right\rvert}^{2(d-1)} + {\left\lVert M \right\rVert}^2_F+ {\left\lVert h \right\rVert}^2$. Recall from \[dens\_W\] that for $k\in{\mathbb{N}}$ and $z\in{\mathbb{C}}^k$ our definition $\varphi(z):=\pi^{-k}\exp(-{\left\lVert z \right\rVert}^2)$. In particular \[aa2\] implies

$$\forall f\in{\widehat{\pi}}_2^{-1}(e_1,\eta): \; \varphi_{{\mathcal{H}}}(f) = \pi^{-n}\exp(-{\left\lvert \eta \right\rvert}^{2(d-1)})\, \varphi(M) \,\varphi(h).$$

Let $a\in{\mathbb{C}}^{n-1}$ denote the first row of $M$ and let $A\in{\mathbb{C}}^{(n-1)\times(n-1)}$ be the matrix obtained from $M$ by removing $a$. Note that $a\sim N({\mathbb{C}}^{n-1})$ and that $A\sim N({\mathbb{C}}^{(n-1)\times (n-1})$. From \[aa2\] we get $$Df(e_1,\eta)= \begin{bmatrix} d\eta^{d-1} & \sqrt{d}a^T \\ 0 & \sqrt{d}A\end{bmatrix},$$ and therefore $$\begin{aligned}
\label{derivative_expansion}
    D{\mathcal{F}}_f(e_1,\eta)&= \begin{bmatrix} \partial_X {\mathcal{F}}_f(X,\Lambda), &  \partial_\Lambda (-\Lambda^{d-1}X) \end{bmatrix}_{(X,\Lambda)=(e_1,\eta)}\nonumber\\
    &= \begin{bmatrix}Df(e_1,\eta) - \eta^{d-1}I_n,& -(d-1)\eta^{d-2}e_1 \end{bmatrix}\nonumber\\
    &=\begin{bmatrix} (d-1)\eta^{d-1}&   \sqrt{d}a^T & -(d-1)\eta^{d-2} \\0& \sqrt{d}A-\eta^{d-1}I_{n-1} & 0\end{bmatrix}.
    \end{aligned}$$ This shows that $$\label{det_expansion}
    {\left\lvert \det {\ensuremath{\left.D{\mathcal{F}}_f(e_1,\eta)\right|_{e_1^\perp\times {\mathbb{C}}}}} \right\rvert}^2 = (d-1)^2{\left\lvert \eta \right\rvert}^{2(d-2)} {\left\lvert \det (\sqrt{d}A-\eta^{d-1}I_{n-1}) \right\rvert}^2.$$ Plugging this into \[integration4\] we see that $K(\zeta,\eta)$ equals $$\frac{(d-1)^2}{\pi^n} \int\limits_{\eta} \left[ \operatorname*{\mathbb{E}}_{A,a,h} \,\Xi(f,e_1,\eta)\, {\left\lvert \det (\sqrt{d}A-\eta^{d-1}I_{n-1}) \right\rvert}^2\right]{\left\lvert \eta \right\rvert}^{2(d-2)} e^{-{\left\lvert \eta \right\rvert}^{2(d-1)}} {\mathrm{d}}\eta,$$ where $A\sim N({\mathbb{C}}^{(n-1)\times(n-1)})$, $a\sim N({\mathbb{C}}^{n-1})$, $h\sim N(R^n)$ and $f$ is as in \[aa2\]. Taking into account the definition of $E(\eta)$ the claim follows.

Average analysis of algorithm LV E-ALH
======================================

This section aims at proving \[Theorem\_4.6\]. The proof itself is contained in \[sec:avg\_anal\]. \[Theorem\_4.4\] indicates, that the average number of steps of algorithm <span style="font-variant:small-caps;">lv e-alh</span> is closely connected to the expectation of the condition number $\mu(f,\zeta,\eta)$. In \[condition\_for\_eigenpairs\] we show that the expectation of $\mu(f,\zeta,\eta)$ can be bounded by the expectation of ${\widehat{\mu}}(f,\zeta,\eta)$. This is why we first compute the expectation of ${\widehat{\mu}}(f,\zeta,\eta)$.

The condition number ${\widehat{\mu}}$ has small expectation {#se:expectation_mu}
------------------------------------------------------------

Let $f\in{{\mathcal{H}}}$. Similarly to \[f\_av\_dfn\] we put $${\widehat{\mu}}_{\mathrm{av}}^2(f) = \frac{1}{{\mathcal{D}}(n,d)} \sum_{(\zeta,\eta)\in{ {\mathbb{S}}({\mathbb{C}}^n)\times{\mathbb{C}}}: f(\zeta)=\eta^{d-1}\zeta} {\widehat{\mu}}^2(f,\zeta,\eta).$$ In this section we prove the following.

\[mu\_expectation0\] $\operatorname*{\mathbb{E}}\limits_{q\sim\mathrm{Unif}\;{\mathbb{S}}({{\mathcal{H}}})}   {\widehat{\mu}}_{\mathrm{av}}^2(q) < 80\,nN d^{-1} $.

The first task on the way to prove \[mu\_expectation0\] is to use [@condition Cor. 2.23] to replace $\mathrm{Unif}\;{\mathbb{S}}({{\mathcal{H}}})$ by the standard normal distribution $N({{\mathcal{H}}})$ (see \[A1\] for details). The advantage of the latter is the independence of the coefficients of $f\sim N({{\mathcal{H}}})$. For $(f,\zeta,\eta)\in{\widehat{{\bf W}}}$ we put $$\widehat{\nu}(f,\zeta,\eta):=  {\left\lVert {\ensuremath{\left.D{\mathcal{F}}_f(\zeta,\eta)\right|_{\zeta^\perp\times{\mathbb{C}}}}}^{-1} \right\rVert}.$$ Clearly, if $f\in{\mathbb{S}}({{\mathcal{H}}})$, we have ${\widehat{\mu}}(f,\zeta,\eta)=\widehat{\nu}(f,\zeta,\eta)$.

The number $\widehat{\nu}$ can be regarded as an absolute version of the condition number ${\widehat{\mu}}$.

\[mutilde\] For all $f\in{{\mathcal{H}}}$ we have ${\widehat{\mu}}_{\mathrm{av}}(f) \leq \max{\left\{{\left\lVert f \right\rVert},{\left\lVert f \right\rVert}^\frac{d-2}{d-1}\right\}} \widehat{\nu}_\mathrm{av}(f)$.

Use the submultiplicativity of the spectral norm.

From \[2dmu\](5) we see that ${\widehat{\mu}}_{\mathrm{av}}$ is scale invariant. We further get from \[2dmu\](3), that ${\widehat{\mu}}_{\mathrm{av}}$ is unitarily invariant. By [@condition Cor. 2.23] we can write $$\operatorname*{\mathbb{E}}\limits_{q\sim\mathrm{Unif}\;{\mathbb{S}}({{\mathcal{H}}})}   {\widehat{\mu}}_{\mathrm{av}}^2(q)=\operatorname*{\mathbb{E}}\limits_{q\sim N_{\sqrt{2N}}({{\mathcal{H}}})}   {\widehat{\mu}}_{\mathrm{av}}^2(q),$$ where $N_{\sqrt{2N}}({{\mathcal{H}}})$ is the *truncated normal distribution* [@condition eq. (17.25)].

Using \[mutilde\] we deduce that $$\operatorname*{\mathbb{E}}\limits_{q\sim N_{\sqrt{2N}}({{\mathcal{H}}})}   \mu_{\mathrm{av}}^2(q) \leq 2N \operatorname*{\mathbb{E}}\limits_{q\sim N_{\sqrt{2N}}({{\mathcal{H}}})}  \nu_\text{av}^2(q) \leq 4N \operatorname*{\mathbb{E}}\limits_{q\sim N({{\mathcal{H}}})}  \nu_\text{av}^2(q);$$ the second inequality by [@condition Lemma 17.25]. \[mu\_expectation0\] is now obtained as a corollary from the following.

$\operatorname*{\mathbb{E}}\limits_{q\sim N({{\mathcal{H}}})}  \nu_\mathrm{av}^2(q)\leq 20n d^{-1}$.

We are in the situation of \[integration\]. In particular, we obtain from it that $$\operatorname*{\mathbb{E}}\limits_{q\sim N({{\mathcal{H}}})}  \nu_\mathrm{av}^2(q)=\frac{\mathrm{vol}\;{\mathbb{S}}({\mathbb{C}}^n)}{2\pi^{n+1}{\mathcal{D}}(n,d)} \int\limits_{\eta\in{\mathbb{C}}} (d-1)^2\; E(\eta)\; {\left\lvert \eta \right\rvert}^{2(d-2)}\; e^{-{\left\lvert \eta \right\rvert}^{2(d-1)}} {\mathrm{d}}\eta,$$ where $$\label{gammaeq100}
    E(\eta)= \operatorname*{\mathbb{E}}\limits_{A,a,h} \nu^2(q,e_1,\eta) {\left\lvert \det(\sqrt{d}A-\eta^{d-1}I_{n-1}) \right\rvert}^2$$ and where $A\sim N({\mathbb{C}}^{(n-1)\times(n-1)})$, $a\sim N({\mathbb{C}}^{n-1})$, $h\sim N(R(e_1)^n)$ and where $$q= \eta^{d-1}X_1^d e_1 + \sqrt{d}X_1^{d-1}\begin{bmatrix} a^T\\ A\end{bmatrix} (X_2,\ldots,X_n)^T + h.$$

For $n\in{\mathbb{N}}$ and $x>0$ let $\Gamma(n,x):=\int_x^\infty t^{n-1}e^{-t}{\mathrm{d}}t$ denote the *upper incomplete Gamma function* (see also \[A2\]). We have $$\begin{aligned}
    &E(\eta)\;(d-1)^2 \;{\left\lvert \eta \right\rvert}^{2(d-2)}\\
    \leq \quad &d^{n-1}\; n\left(1+(d-1){\left\lvert \eta \right\rvert}^{2(d-2)}\right)\; \Gamma\Big(n,\frac{{\left\lvert  \eta \right\rvert}^{2(d-1)}}{d}\Big)\;\exp\left(\frac{{\left\lvert \eta \right\rvert}^{2(d-1)}}{d}\right).
    \end{aligned}$$

Suppose that the claim is true. Then $\operatorname*{\mathbb{E}}\limits_q\mu_{\mathrm{av}}^2(q)$ is less than or equal to $$\frac{nd^{n-1}\mathrm{vol}\;{\mathbb{S}}({\mathbb{C}}^n)}{2\pi^{n+1}{\mathcal{D}}} \int\limits_{\eta\in {\mathbb{C}}} (1+(d-1){\left\lvert \eta \right\rvert}^{2(d-2)}) \Gamma\Big(n,\frac{{\left\lvert  \eta \right\rvert}^{2(d-1)}}{d}\Big)e^{-(1-d^ {-1}){\left\lvert \eta \right\rvert}^{2(d-1)}}{\mathrm{d}}\eta,$$ where we have put ${\mathcal{D}}:={\mathcal{D}}(n,d)=d^n-1$. We get from \[auxiliary\_lemma\](1) that the expression above is equal to (note the cancellation in $\exp$) $$\frac{(n-1)!nd^{n-1}\mathrm{vol}\;{\mathbb{S}}({\mathbb{C}}^n)}{2\pi^{n+1}{\mathcal{D}}} \int\limits_{\eta\in {\mathbb{C}}} (1+(d-1){\left\lvert \eta \right\rvert}^{2(d-2)}) e^{-{\left\lvert \eta \right\rvert}^{2(d-1)}} \sum_{k=0}^{n-1} \frac{{\left\lvert  \eta \right\rvert}^{2(d-1)k}}{k! d^k}{\mathrm{d}}\eta.$$ Observe that the integrand is independent of the argument of $\eta$. Substituting $r:={\left\lvert \eta \right\rvert}$, that is ${\mathrm{d}}\eta = r\,{\mathrm{d}}r\, {\mathrm{d}}\theta$, shows that $\operatorname*{\mathbb{E}}\limits_{q}\mu_{\mathrm{av}}^2(q)$ is less than or equal to $$\frac{(n-1)!nd^{n-1}\mathrm{vol}\;{\mathbb{S}}({\mathbb{C}}^n)}{\pi^{n}{\mathcal{D}}} \int\limits_{r\geq 0} (r+(d-1)r^{2(d-2)+1}) e^{-r^{2(d-1)}} \sum_{k=0}^{n-1} \frac{r^{2(d-1)k}}{k! d^k}{\mathrm{d}}r.$$ Making the change of variables $t:=r^{2(d-1)}$, interchanging summation and integration and using the fact that $\mathrm{vol}\;{\mathbb{S}}({\mathbb{C}}^n) = 2\pi^n/(n-1)!$ yields $$\begin{aligned}
    \operatorname*{\mathbb{E}}\limits_{q\sim N(0,\frac{1}{2}I)}\mu_{\mathrm{av}}^2(q)
    \leq\; &\frac{ nd^{n-1}}{{\mathcal{D}}(d-1)} \sum_{k=0}^{n-1}\;\int\limits_{t\geq 0} \left(t^{\frac{1}{d-1}-1}+(d-1)\right)  \frac{t^{k}e^ {-t}}{k! d^k}\;{\mathrm{d}}t\nonumber\\
    \;=\;&\frac{ nd^{n-1}}{{\mathcal{D}}(d-1)} \sum_{k=0}^{n-1}\frac{\Gamma\big(k+\frac{1}{d-1}\big) + (d-1)\, \Gamma\big(k+1\big)}{d^k k!}\nonumber\\
\;=\;&\frac{ nd^{n-1}}{{\mathcal{D}}(d-1)}\left( \sum_{k=0}^{n-1}\frac{\Gamma\big(k+\frac{1}{d-1}\big)}{d^k k!}+ (d-1)\sum_{k=0}^{n-1}\frac{1}{d^k}\right)\label{gammaeq0}\end{aligned}$$ For $0<\epsilon<1$ and $k\geq 2$ we have $\Gamma(k+\epsilon)\leq \Gamma(k+1)=k!$ and hence $$\begin{aligned}
    \sum_{k=0}^{n-1}\frac{\Gamma\big(k+\frac{1}{d-1}\big)}{d^k k!} &\hspace{0.4cm}\leq \;\Gamma\left(\frac{1}{d-1}\right) +\frac{\Gamma\big(1+\frac{1}{d-1}\big)}{d} + \sum_{k=2}^n\frac{1}{d^k}\nonumber\\
    &\hspace{0.3cm}\stackrel{d\geq 2}{\leq}\;  \Gamma\left(\frac{1}{d-1}\right) +\frac{\Gamma\big(1+\frac{1}{d-1}\big)}{d} + \sum_{k=2}^n\frac{1}{2^k}\nonumber\\
    &\hspace{0.4cm}\leq\;\Gamma\left(\frac{1}{d-1}\right) +\frac{\Gamma\big(1+\frac{1}{d-1}\big)}{d} +\frac{1}{2}\nonumber\\
    &\stackrel{\text{\cref{gamma_lemma}}}{\leq}\;  (d-1)\frac{\sqrt{\pi}}{2} +\frac{\sqrt{\pi}}{2d} + \frac{1}{2} \leq 3d.\label{gammaeq1}
    \end{aligned}$$ Using that $d\geq 2$ we also have $ (d-1)\sum_{k=0}^{n-1}\frac{1}{d^k} \leq d \sum_{k=0}^{n-1}\frac{1}{2^k} \leq 2d$. Combining this with \[gammaeq1\] and plugging into \[gammaeq0\] we obtain $$\operatorname*{\mathbb{E}}\limits_{q\sim N(0,\frac{1}{2}I)}\mu_{\mathrm{av}}^2(q)
    \leq \frac{ 5nd^{n}}{{\mathcal{D}}(d-1)} =5n\, \frac{d^{n}}{(d^n-1)(d-1)}\, \stackrel{d\geq 2}{\leq}\, \frac{20n}{d}.$$ This shows the assertion. It remains to prove the claim.

<span style="font-variant:small-caps;">Proof of the claim.</span> The following proof follows ideas that we found in [@matrix_eigenpair sec. 7]. Recall from \[gammaeq0\] that for fixed $\eta\in{\mathbb{C}}$ we have $$E(\eta) 
     = \operatorname*{\mathbb{E}}\limits_{A,a,h} \nu^2(q,e_1,\eta) {\left\lvert \det(\sqrt{d}A-\eta^{d-1}I) \right\rvert}^2.$$ As in \[det\_expansion\] we have that $${\left\lvert \det(\sqrt{d}A-\eta^{d-1}I) \right\rvert}^2\;(d-1)^2 \;{\left\lvert \eta \right\rvert}^{2(d-2)} = {\left\lvert \det {\ensuremath{\left.D{\mathcal{F}}_q(e_1,\eta)\right|_{e_1^\perp\times {\mathbb{C}}}}} \right\rvert}^2.$$ Moreover, $\nu^2(q,e_1,\eta) ={\left\lVert {\ensuremath{\left.D{\mathcal{F}}_q(e_1,\eta)\right|_{e_1^\perp\times {\mathbb{C}}}}}^{-1} \right\rVert}^2\leq {\left\lVert {\ensuremath{\left.D{\mathcal{F}}_q(e_1,\eta)\right|_{e_1^\perp\times {\mathbb{C}}}}}^{-1} \right\rVert}^2_F$ by the fact that the spectral norm of a matrix is less than or equal to its Frobenius norm. Putting $S:={\ensuremath{\left.D{\mathcal{F}}_q(e_1,\eta)\right|_{e_1^\perp\times{\mathbb{C}}}}}$ we get $$\label{z3.1}E(\eta) \;(d-1)^2 {\left\lvert \eta \right\rvert}^{2(d-2)} \leq \operatorname*{\mathbb{E}}\limits_{A,a,h} \; {\left\lVert S^{-1} \right\rVert}_F^2{\left\lvert \det S \right\rvert}^2.$$ We next compute the expectation on the right.

Let us put $b:=\sqrt{d}a$ and $B:=\sqrt{d}A-\eta^{d-1}I$. Recall from \[derivative\_expansion\] that $$\label{derivative_expansion2}
    S =\begin{bmatrix}   \sqrt{d} a^T & -(d-1)\eta^{d-2} \\ \sqrt{d}A -\eta^{d-1}I & 0\end{bmatrix} =\begin{bmatrix}   b^T & -(d-1)\eta^{d-2} \\ B & 0\end{bmatrix}.$$ Note that $S$ is independent of $h$, so that in consequence we obtain from \[z3.1\] that $$\label{z3}E(\eta) \;(d-1)^2 {\left\lvert \eta \right\rvert}^{2(d-2)} \leq \operatorname*{\mathbb{E}}\limits_{A,a} \; {\left\lVert S^{-1} \right\rVert}_F^2{\left\lvert \det S \right\rvert}^2.$$ We enumerate the entries of $S$ with indices $0\leq i,j\leq n-1$, the entries of $B$ are enumerated with indices $1\leq i,j\leq n-1$. Let $S^{i,j}\in{\mathbb{C}}^{(n-1)\times(n-1)}$, $0\leq i,j\leq n-1$, denote the matrix that is obtained by removing from $S$ the $i-$ th row and the $j$-th column and define $B^{i,j},1\leq i,j\leq n-1$, correspondingly. By Cramer’s rule we have ${\left\lVert S^{-1} \right\rVert}_F^2{\left\lvert \det S \right\rvert}^2 = \sum_{0\leq i,j\leq n-1} {\left\lvert \det S^{i,j} \right\rvert}^2$. We deduce from \[derivative\_expansion2\] that $${\left\lvert \det S^{i,j} \right\rvert}^2 = 
\begin{cases}
0, &\text{if } i=0,\, j <n-1\\
{\left\lvert \det B \right\rvert}^2, &\text{if } i=0,\,j=n-1\\
(d-1)^2\eta^{2(d-2)} {\left\lvert \det B^{i,j} \right\rvert}^2, &\text{if } i>0,\,j<n-1\\
 {\left\lvert \det B(i:b) \right\rvert}^2, &\text{if } i>0,\, j=n-1
\end{cases},\label{cases}$$ where $B(i:b)$ is the matrix that is obtained from $B$ by replacing the $i$-th row of $B$ with $b$. We have $\mathrm{Var}(B_{i,j})= d\;\mathrm{Var}(A_{i,j})=d$ for $1\leq i,j\leq n-1$, so that from \[equation\_random\_matrix\] we get for fixed $1\leq i \leq n-1$ $$\label{r5}
d\sum_{j=1}^{n-1}  \operatorname*{\mathbb{E}}{\left\lvert \det B^{i,j} \right\rvert}^2=\sum_{j=1}^{n-1}  \mathrm{Var}(B_{i,j}) \operatorname*{\mathbb{E}}{\left\lvert \det B^{i,j} \right\rvert}^2 \leq \operatorname*{\mathbb{E}}{\left\lvert \det B \right\rvert}^2.$$ We moreover have $\operatorname*{\mathbb{E}}b =0$ and for $1\leq j\leq n-1$ we have $\mathrm{Var}(b_j)= d$. Using \[equation\_random\_matrix\] again, we obtain for $1\leq i \leq n-1$ $$\begin{aligned}
\label{r4}
\nonumber\operatorname*{\mathbb{E}}{\left\lvert \det B(i:b) \right\rvert}^2 &= \operatorname*{\mathbb{E}}{\left\lvert \det B(i:0) \right\rvert}^2+\sum_{j=1}^{n-1} \mathrm{Var}(b_j)\operatorname*{\mathbb{E}}{\left\lvert \det B^{i,j} \right\rvert}^2\\
&=  d \sum_{j=1}^{n-1} \operatorname*{\mathbb{E}}{\left\lvert \det B^{i,j} \right\rvert}^2 \;\stackrel{\cref{r5}}{\leq}\; \operatorname*{\mathbb{E}}{\left\lvert \det B \right\rvert}^2\end{aligned}$$ Combining \[cases\] with \[r5\] and \[r4\] we get $$\begin{aligned}
    &\operatorname*{\mathbb{E}}{\left\lVert S^{-1} \right\rVert}_F^2{\left\lvert \det S \right\rvert}^2\nonumber\\
    =\; &\operatorname*{\mathbb{E}}{\left\lvert \det B \right\rvert}^2 + (d-1)^2{\left\lvert \eta \right\rvert}^{2(d-2)}\sum_{1\leq i,j\leq n-1} \operatorname*{\mathbb{E}}{\left\lvert \det B^{i,j} \right\rvert}^2 + \sum_{i=1}^{n-1} \operatorname*{\mathbb{E}}{\left\lvert \det B(i:b) \right\rvert}^2\nonumber\\
    \leq\; &\operatorname*{\mathbb{E}}{\left\lvert \det B \right\rvert}^2 + \frac{(n-1)(d-1)^2{\left\lvert \eta \right\rvert}^{2(d-2)}}{d}\;\operatorname*{\mathbb{E}}{\left\lvert \det B \right\rvert}^2 + (n-1)\operatorname*{\mathbb{E}}{\left\lvert \det B \right\rvert}^2\nonumber\\
     \leq\; &  n\;\left(1+(d-1)\eta^{2(d-2)}\right) \operatorname*{\mathbb{E}}{\left\lvert \det B \right\rvert}^2.\label{z0}
    \end{aligned}$$ We have that $$\begin{aligned}
\operatorname*{\mathbb{E}}{\left\lvert \det B \right\rvert}^2 &= \operatorname*{\mathbb{E}}{\left\lvert \det(\sqrt{d}A-\eta^{d-1} I_{n-1}) \right\rvert}^2\nonumber\\
& = d^{n-1}\operatorname*{\mathbb{E}}{\left\lvert \det\left(A-\frac{\eta^{d-1}}{\sqrt{d}} I_{n-1}\right) \right\rvert}^2\label{z1}\end{aligned}$$ and by \[auxiliary\_lemma\](3) we have $$\label{z2}\operatorname*{\mathbb{E}}{\left\lvert \det\left(A-\frac{\eta^{d-1}}{\sqrt{d}} I_{n-1}\right) \right\rvert}^2 = \exp\left(\frac{{\left\lvert \eta \right\rvert}^{2(d-1)}}{d}\right)\Gamma\left(n,\frac{{\left\lvert \eta \right\rvert}^{2(d-1)}}{d}\right).$$ Combining \[z2,z1\] with \[z0\] and \[z3\] shows the claim.

Proof of \[Theorem\_4.6\] {#sec:avg_anal}
-------------------------

Let ${\mathcal{C}}(f):=\operatorname*{\mathbb{E}}\limits_{(g,\zeta,\eta)\sim\rho} {\mathcal{C}}(f,(g,\zeta,\eta))$ and $$\mu_{\mathrm{av}}^2(f) = \frac{1}{{\mathcal{D}}(n,d)} \sum_{(\zeta,\eta)\in{\mathscr{P}}: f(\zeta)=\eta^{d-1}\zeta} \mu^2(f,\zeta,\eta)$$ It is easy to check that $\left[\int_{0}^{1} \mu^2(q_\tau,\zeta_\tau,\eta_\tau){\mathrm{d}}\tau\right]_\mathrm{\;av} =  \int_{0}^{1} \mu_{\mathrm{\;av}}^2(q_\tau){\mathrm{d}}\tau,$ which implies that $$\operatorname*{\mathbb{E}}\limits_{f \sim\text{Unif}\;{\mathbb{S}}({\mathcal{H}}_d^n)} {\mathcal{C}}(f) =\operatorname*{\mathbb{E}}\limits_{f,g \sim\text{Unif}\;{\mathbb{S}}({\mathcal{H}}^n)}  \int_{q\in E_{f,g}} \mu^2_{\mathrm{\;av}}(q)\,{\mathrm{d}}E_{f,g}.$$ Here $E_{f,g}$ again denotes the geodesic path between $f$ and $g$. \[condition\_for\_eigenpairs\](4) implies that for all $q\in{\mathcal{H}}^n$ we have $\mu^2_{\mathrm{\;av}}(q) \leq {\widehat{\mu}}^2_{\mathrm{\;av}}(q) $ and hence $$\label{r6}
    \operatorname*{\mathbb{E}}\limits_{f \sim\text{Unif}\;{\mathbb{S}}({\mathcal{H}}_d^n)} {\mathcal{C}}(f) \leq \operatorname*{\mathbb{E}}\limits_{f,g \sim\text{Unif}\;{\mathbb{S}}({\mathcal{H}}^n)}  \int_{q\in E_{f,g}} {\widehat{\mu}}^2_{\mathrm{\;av}}(q)\,{\mathrm{d}}E_{f,g}.$$ The following is [@beltran_pardo1 eq. (4.3)].

\[beltran\_pardo\_lemma\] Let $N\in{\mathbb{N}}$ and ${\mathbb{S}}:={\mathbb{S}}({\mathbb{C}}^N)$. For any measurable function $\phi:{\mathbb{S}}\to{\mathbb{R}}$ we have that $$\operatorname*{\mathbb{E}}\limits_{f,g \sim\mathrm{Unif}({\mathbb{S}})}\; \int_{h\in E_{f,g}} \phi(h)\, {\mathrm{d}}E_{f,g}  = \pi/2  \operatorname*{\mathbb{E}}\limits_{h\sim\mathrm{Unif}({\mathbb{S}})} \;\phi(h)..$$

Combining \[r6\] with \[beltran\_pardo\_lemma\] we get that $$\operatorname*{\mathbb{E}}_{f \sim\mathrm{Unif}\;{\mathbb{S}}({\mathcal{H}}_d^n)} {\mathcal{C}}(f) \leq \operatorname*{\mathbb{E}}_{q \sim\text{Unif}\;{\mathbb{S}}({\mathcal{H}}_d^n)}   {\widehat{\mu}}^2_{\mathrm{\;av}}(q).$$ \[mu\_expectation0\] shows that $\operatorname*{\mathbb{E}}\limits_{q\sim\mathrm{Unif}\;{\mathbb{S}}({{\mathcal{H}}})}   {\widehat{\mu}}_{\mathrm{av}}^2(q) \leq 80\,nN d^{-1}$. This shows the assertion.

Proof of \[Theorem\_4.3\] {#condition_number_thm_proof}
=========================

In order to prove \[Theorem\_4.3\] we will need the following lemma.

\[condition\_number\_thm\_lemma\] For $d\geq 2$ and $2\leq k\leq d$ we have that $\frac{(d-1)!}{k!(d-k)!}\leq \left(\frac{d}{2}\right)^{k-1}$.

Combine $k!\geq 2^{k-1}$ with $\frac{(d-1)!}{(d-k)!} \leq d^{k-1}$.

The following is similar to the proof of [@condition Theorem 16.1].

We choose a representative $(\zeta,\eta)\in{\mathbb{S}}({\mathbb{C}}^n)\times{\mathbb{C}}$, so that $(f,\zeta,\eta)\in{\widehat{{\bf V}}}_{\mathbb{S}}$, by assumption. From \[useful\_lemma2\] we get ${\left\lVert \zeta,\eta \right\rVert}\leq \sqrt{2}$. Moreover, for any $2\leq k\leq d$, using the submultiplicativity of the spectral norm, we have $$\begin{aligned}
 {\left\lVert \frac{1}{k!} {\ensuremath{\left.D{\mathcal{F}}_f(\zeta,\eta)\right|_{(\zeta,\eta)^\perp}}}^{-1} \cdot D^k{\mathcal{F}}_f(\zeta,\eta) \right\rVert}
 &\leq\frac{1}{k!}\; {\left\lVert {\ensuremath{\left.D{\mathcal{F}}_f(\zeta,\eta)\right|_{(\zeta,\eta)^\perp}}}^{-1}  \right\rVert} {\left\lVert  D^k{\mathcal{F}}_f(\zeta,\eta) \right\rVert}\nonumber\\
 &= \frac{1}{k!}\;\mu(f,\zeta,\eta) {\left\lVert  D^k{\mathcal{F}}_f(\zeta,\eta) \right\rVert}.\label{gamma_to_condition0}
 \end{aligned}$$ By the triangle inequality we have $${\left\lVert  D^k{\mathcal{F}}_f(\zeta,\eta) \right\rVert} \leq {\left\lVert  D^kf(\zeta) \right\rVert} + {\left\lVert D^k(\Lambda^{d-1}X)(\zeta,\eta) \right\rVert}.\label{gamma_to_condition1}$$ Using ${\left\lVert f \right\rVert}={\left\lVert \zeta \right\rVert}=~1$ we get from [@condition Prop. 16.48] $$\label{gamma_to_condition2}
{\left\lVert D^kf(\zeta) \right\rVert} \leq \frac{d!}{(d-k)!}$$ One easily sees that ${\left\lVert D^k(\Lambda^{d-1}X)(\zeta,\eta) \right\rVert} \leq \left(\sum_{i=1}^n {\left\lVert D^k(\Lambda^{d-1}X_i)(\zeta,\eta) \right\rVert}^2\right)^\frac{1}{2}$. For $v_1,\ldots,v_k\in{\mathbb{C}}^n $ let $v_i^j$ be the $j$-th entry of $v_i$. Then $$\begin{aligned}
    {\left\lVert D^k(\Lambda^{d-1}X_i)(\zeta,\eta) \right\rVert}&= \max\limits_{v_1,\ldots,v_k\in{\mathbb{S}}({\mathbb{C}}^n)} \;{\left\lvert \sum_{1\leq i_1,\ldots,i_k\leq n} \frac{\partial^k (\Lambda^{d-1}X_i)}{\partial X_{i_1}\ldots\partial X_{i_k}}(\zeta,\eta) \prod_{j=1}^k v_j^{i_j} \right\rvert}\\
    &\leq \sum_{1\leq i_1,\ldots,i_k\leq n} {\left\lvert \frac{\partial^k (\Lambda^{d-1}X_i)}{\partial X_{i_1}\ldots\partial X_{i_k}}(\zeta,\eta) \right\rvert} 
    \end{aligned}$$ Oberve, that the only $k$-th order derivatives of $\Lambda^{d-1}X_i$, that are non-zero, are $\Lambda^{d-1-k} X_i~\prod\limits_{i=0}^{k-1}(d-1-i)$ and $ \Lambda^{d-k}\prod\limits_{i=0}^{k-2} (d-1-i)$. This implies $$\begin{aligned}
    {\left\lVert D^k(\Lambda^{d-1}X_i)(\zeta,\eta) \right\rVert} &\leq \frac{ (d-1)!}{(d-1-k)!} \; {\left\lvert \eta \right\rvert}^{d-1-k} {\left\lvert \zeta_i \right\rvert} +  k \; \frac{(d-1)!}{(d-k)!} \; {\left\lvert \eta \right\rvert}^{d-k}
    \leq \frac{ (d-1)!}{(d-k)!}\; (d-k+k) = \frac{ d!}{(d-k)!};
    \end{aligned}$$ where we have used from \[useful\_lemma2\] that ${\left\lvert \eta \right\rvert}\leq{\left\lVert \zeta \right\rVert}=1$. This shows that ${\left\lVert D^k(\Lambda^{d-1}X)(\zeta,\eta) \right\rVert} \leq \sqrt{n} \;\frac{ d!}{(d-k)!}$. Plugging this and \[gamma\_to\_condition2\] into \[gamma\_to\_condition1\] we get $${\left\lVert  D^k{\mathcal{F}}_f(\zeta,\eta) \right\rVert} \leq (\sqrt{n}+1)\;\frac{d!}{(d-k)!}.$$ Using \[gamma\_to\_condition0\] we obtain $$\begin{aligned}
 {\left\lVert \zeta,\eta \right\rVert}^{k-1}\; {\left\lVert  D{\mathcal{F}}_f(\zeta,\eta)|_{(\zeta,\eta)^\perp}^{-1} \; \frac{D^k{\mathcal{F}}_f(\zeta,\eta)}{k!} \right\rVert}
 &\leq  \sqrt{2}^{k-1}\;\mu(f,\zeta,\eta)\; \frac{(\sqrt{n}+1)\;d!}{(d-k)!\;k!}\\
     &\leq  \sqrt{2n}^{k-1}\; \mu(f,\zeta,\eta) \; \frac{2\;d!}{(d-k)!k!}\\
      &= \sqrt{2n}^{k-1}\; 2d\; \mu(f,\zeta,\eta) \; \frac{(d-1)!}{(d-k)!k!}.
 \end{aligned}$$ By \[condition\_number\_thm\_lemma\] we have $(d-1)!/(k!(d-k)!)\leq \left(\frac{d}{2}\right)^{k-1}$. By \[2dmu\] we have $1\leq 2d\,\mu(f,\zeta,\eta)$, so that $2d\,\mu(f,\zeta,\eta)\leq (2d\,\mu(f,\zeta,\eta))^{k-1}$. Hence $${\left\lVert \zeta,\eta \right\rVert}\; {\left\lVert \frac{1}{k!} D{\mathcal{F}}_f(\zeta,\eta)|_{(\zeta,\eta)^\perp}^{-1} D^k{\mathcal{F}}_f(\zeta,\eta) \right\rVert}^\frac{1}{k-1}
 \leq \mu(f,\zeta,\eta)\; d^2 \,\sqrt{2n},$$ from which the claim follows.

Proof of \[Theorem\_4.4\]
=========================

Before proving \[Theorem\_4.4\] we will have to quantify the behaviour of the condition number $\mu(f,v,\lambda)$ under small pertubations of both $f$ and $(v,\lambda)$. The following is similar to [@condition sec. 16.8].

A Lipschitz estimate for the condition number {#lipschitz_sec}
---------------------------------------------

\[lipschitz1\]

1.  Let $f,g\in{\mathbb{S}}({{\mathcal{H}}})$ and $(v,\lambda)\in {\mathscr{P}}$. If $d\, \mu(f,v,\lambda)\;d_{\mathbb{S}}(f,g)\leq \epsilon < 1,$ then $$\mu(g,v,\lambda)\leq \frac{1}{1-\epsilon}\; \mu(f,v,\lambda).$$

2.  Let $(f,\zeta,\eta)\in{{\bf W}}_{\mathbb{S}}$ and $(v,\lambda)\in{\mathscr{P}}$. If $$4\;d^2 \sqrt{n}\; \mu(f,\zeta,\eta)\; d_{\mathbb{P}}((v,\lambda),(\zeta,\eta))\leq \epsilon \leq \frac{1}{4},$$ then $$(1-\epsilon)^2\mu(f,\zeta,\eta)\leq \mu(f,v,\lambda)\leq \frac{1}{\vartheta(\epsilon)}\; \mu(f,\zeta,\eta),$$ where $\vartheta(\epsilon):=1-(1-\epsilon)^{-2}+\cos(\epsilon/4)$.

We can combine the statements in \[lipschitz1\] by using the function $\Theta: [0,1) \to {\mathbb{R}},\; \epsilon\mapsto \vartheta(\epsilon)-\epsilon .$ Observe that $$\label{theta_ineq} 
\forall \,0\leq\epsilon\leq 1/5:\; 0<\Theta(\epsilon)\leq 1\;\text{and}\; \epsilon<\vartheta(\epsilon).$$

\[lipschitz3\] Let $(f_1,\zeta_1,\eta_1),(f_2,\zeta_2,\eta_2)\in{{\bf W}}_{\mathbb{S}}$. If $$d\, \mu(f_1,\zeta_1,\eta_1)\; \max{\left\{ d_{\mathbb{S}}(f_1,f_2),  4\; d\sqrt{n}\; d_{\mathbb{P}}((\zeta_1,\eta_1),(\zeta_2,\eta_2)) \right\}} \leq \epsilon \leq \frac{1}{5},$$ then $$\Theta(\epsilon) \;\mu(f_1,\zeta_1,\eta_1)\leq \mu(f_2,\zeta_2,\eta_2) \leq \frac{1}{\Theta(\epsilon)} \;\mu(f_1,\zeta_1,\eta_1).$$

We may apply \[lipschitz1\](2) to obtain $$\label{lipschitz3.1}
    \mu(f_1,\zeta_2,\eta_2)\leq \frac{1}{\vartheta(\epsilon)} \; \mu(f_1,\zeta_1,\eta_1).$$ This yields $d \, \mu(f_1,\zeta_2,\eta_2)\;  d_{\mathbb{S}}(f,g) \leq \epsilon/\vartheta(\epsilon)=:\epsilon' < 1,$ by \[theta\_ineq\]. Applying \[lipschitz1\](1) yields $$\label{lipschitz3.2}
    \mu(f_2,\zeta_2,\eta_2) \leq \frac{1}{1-\epsilon'} \;  \mu(f_1,\zeta_2,\eta_2)$$ Combining \[lipschitz3.1\] and \[lipschitz3.2\] gives $$\mu(f_2,\zeta_2,\eta_2) \leq \frac{1}{(1-\epsilon')\vartheta(\epsilon)} \; \mu(f_1,\zeta_1,\eta_1) = \frac{1}{\vartheta(\epsilon)-\epsilon} \; \mu(f_1,\zeta_1,\eta_1)$$ This yields the right inequality. If $\mu(f_1,\zeta_1,\eta_1)\leq \mu(f_2,\zeta_2,\eta_2)$, the left inequality is trivial. If $\mu(f_2,\zeta_2,\eta_2)\leq \mu(f_1,\zeta_1,\eta_1)$, then $$\begin{aligned}
    &d \; \mu(f_2,\zeta_2,\eta_2)\;   \max{\left\{ d_{\mathbb{S}}(f_1,f_2),  4\; d\sqrt{n}\; d_{\mathbb{P}}((\zeta_1,\eta_1),(\zeta_2,\eta_2)) \right\}}\\
     \leq \;&d \; \mu(f_1,\zeta_1,\eta_1)\; \max{\left\{ d_{\mathbb{S}}(f_1,f_2),  4\; d\sqrt{n}\; d_{\mathbb{P}}((\zeta_1,\eta_1),(\zeta_2,\eta_2)) \right\}}\leq  \epsilon .
    \end{aligned}$$ and we may interchange the roles of $(f_1,\zeta_1,\eta_1)$ and $(f_2,\zeta_2,\eta_2)$ to conclude.

In order to prove \[lipschitz1\] we will need the following lemma, similiar to [@condition Lemma 16.41]. Recall from \[gamma\_thm\] the definition $$\gamma(f,\zeta,\eta) =  {\left\lVert \zeta,\eta \right\rVert}\, \max\limits_{k\geq 2} {\left\lVert \frac{1}{k!}\,D{\mathcal{F}}_f(\zeta,\eta)|_{(\zeta,\eta)^\perp}^{-1} \;  D^k{\mathcal{F}}_f(\zeta,\eta) \right\rVert}^\frac{1}{k-1}$$ and from \[psi\] the definition $$\Psi_\delta(u)=(1+\cos\delta)(1-u)^2-1,\; u,\delta\in{\mathbb{R}}.$$

\[lipschitz0\] Let $(f,\zeta,\eta)\in{\widehat{{\bf W}}}_{\mathbb{S}}$ and let $(v,\lambda)\in{ {\mathbb{S}}({\mathbb{C}}^n)\times{\mathbb{C}}}$. Put $\delta:=d_{\mathbb{S}}((v,\lambda),(\zeta,\eta))$ and $u:=\delta\gamma(f,\zeta,\eta)\sqrt{8}$. If $\delta<\pi/16$ and $ u <1$, then $${\left\lVert  D{\mathcal{F}}_f(\zeta,\eta)|_{(\zeta,\eta)^\perp}^{-1}\; D{\mathcal{F}}_f(v,\lambda)|_{(v,\lambda)^\perp} \right\rVert}\leq  \frac{1}{(1-u)^2}.$$ If further $\Psi_\delta(u)>0$, then $D{\mathcal{F}}_f(v,\lambda)|_{(v,\lambda)^\perp}$ is invertible and we have $${\left\lVert D{\mathcal{F}}_f(v,\lambda)|_{(v,\lambda)^\perp}^{-1} \;  D{\mathcal{F}}_f(\zeta,\eta)|_{(\zeta,\eta)^\perp} \right\rVert}\leq  \frac{(1-u)^2}{\Psi_\delta(u)}.$$

We denote by ${\mathcal{L}}({\mathbb{C}}^n\times {\mathbb{C}},{\mathbb{C}}^n)$ the vector space of ${\mathbb{C}}$-linear maps ${\mathbb{C}}^n\times {\mathbb{C}}\to{\mathbb{C}}^n$, compare \[A3\] and [@condition eq. (15.2), Lemma 15.9]. For any $f\in{\mathcal{H}}$ we define $$D{\mathcal{F}}_f: {\mathbb{C}}^n \times {\mathbb{C}}\to {\mathcal{L}}({\mathbb{C}}^n\times {\mathbb{C}},{\mathbb{C}}^n),\; (v,\lambda)\mapsto D{\mathcal{F}}_f(v,\lambda),$$ so that $D^2{\mathcal{F}}_f (v,\lambda):=D(D{\mathcal{F}}_f)(v,\lambda) \in {\mathcal{L}}({\mathcal{L}}({\mathbb{C}}^n\times {\mathbb{C}},{\mathbb{C}}^n),{\mathbb{C}}^n)$. Inductively we define $$D^k{\mathcal{F}}_f (v,\lambda)^{k-1}:= D^k{\mathcal{F}}_f (\underbrace{(v,\lambda),\ldots,(v,\lambda)}_{k\text{-times}}),\;k\geq 1.$$ The Taylor expansion of $D{\mathcal{F}}_f(v,\lambda)|_{(v,\lambda)^\perp}$ around $(\zeta,\eta)$ can then be expressed as $$D{\mathcal{F}}_f(v,\lambda)|_{(v,\lambda)^\perp} = \sum_{k=1}^d \frac{1}{(k-1)!}\;  D^k{\mathcal{F}}_f(\zeta,\eta)|_{(v,\lambda)^\perp} (v-\zeta,\lambda-\eta)^{k-1},$$ see also [@condition Lemma 16.41]. Then $D{\mathcal{F}}_f(\zeta,\eta)|_{(\zeta,\eta)^\perp}^{-1} \;  D{\mathcal{F}}_f(v,\lambda)|_{(v,\lambda)^\perp} = P + B$, where $$P=  D{\mathcal{F}}_f(\zeta,\eta)|_{(\zeta,\eta)^\perp}^{-1} \;  D{\mathcal{F}}_f(\zeta,\eta)|_{(v,\lambda)^\perp}$$ and $$B= \sum_{k=2}^d \frac{1}{(k-1)!} D{\mathcal{F}}_f(\zeta,\eta)|_{(\zeta,\eta)^\perp}^{-1} \;  D^k{\mathcal{F}}_f(\zeta,\eta)|_{(v,\lambda)^\perp} (v-\zeta,\lambda-\eta)^{k-1}.\label{B}$$ By \[projection\_lemma\] we have that ${\left\lVert P \right\rVert}\leq 1$. If in \[real\_geometry\_prop\] we put $x=(\zeta,\eta),y=(v,\lambda)$, we obtain ${\left\lVert v-\zeta,\lambda-\eta \right\rVert} \leq \delta\sqrt{8}$. Combining with \[B\] we obtain $$\begin{aligned}
{\left\lVert B \right\rVert}&\hspace{0.3cm}\leq\sum_{k=1}^d  k {\left\lVert \frac{1}{k!}\, D{\mathcal{F}}_f(\zeta,\eta)|_{(\zeta,\eta)^\perp}^{-1} \;  D^k{\mathcal{F}}_f(\zeta,\eta)(v-\zeta,\lambda-\eta)^{k-1} \right\rVert}\\
&\stackrel{\text{by} \cref{spectral_norm}}{\leq}  \sum_{k=1}^d  k {\left\lVert \frac{1}{k!}\, D{\mathcal{F}}_f(\zeta,\eta)|_{(\zeta,\eta)^\perp}^{-1} \;  D^k{\mathcal{F}}_f(\zeta,\eta) \right\rVert}\,{\left\lVert v-\zeta,\lambda-\eta \right\rVert}^{k-1}\\
&\hspace{0.1cm}\stackrel{{\left\lVert \zeta \right\rVert}=1}{\leq} \sum_{k=1}^d  k {\left\lVert \zeta,\eta \right\rVert}^\frac{1}{k-1}{\left\lVert \frac{1}{k!}D{\mathcal{F}}_f(\zeta,\eta)|_{(\zeta,\eta)^\perp}^{-1} D^k{\mathcal{F}}_f(\zeta,\eta) \right\rVert}{\left\lVert v-\zeta,\lambda-\eta \right\rVert}^{k-1}\\
&\hspace{0.3cm}\leq \sum_{k=2}^d  k\left(\gamma(f,\zeta,\eta)\,\delta\,\sqrt{8}\right)^{k-1} =   \sum_{k=2}^d  ku^{k-1}\leq (1- u)^{-2}-1;\end{aligned}$$ the first inequality by the triangle inequality. This implies $${\left\lVert D{\mathcal{F}}_f(\zeta,\eta)|_{(\zeta,\eta)^\perp}^{-1} \;  D{\mathcal{F}}_f(v,\lambda)|_{(v,\lambda)^\perp} \right\rVert} = {\left\lVert P+B \right\rVert} \leq {\left\lVert P \right\rVert}+{\left\lVert B \right\rVert} \leq (1-u)^{-2},$$ which is the first assertion.

It remains prove the second assertion. \[projection\_lemma\] tells us that $P$ is invertible and that ${\left\lVert P^ {-1} \right\rVert}\leq (\cos \delta)^{-1}.$ By our assumption $\Psi_\delta(u) > 0$ we have ${\left\lVert P^{-1} \right\rVert}{\left\lVert B \right\rVert} \leq (\cos\delta)^{-1}\; \left((1-u)^{-2}-1\right) < 1.$ From [@condition Lemma 15.7] we get that $P+B$ is invertible and that $${\left\lVert (P+B)^{-1} \right\rVert}\leq \frac{{\left\lVert P^{-1} \right\rVert}}{1-{\left\lVert B \right\rVert}{\left\lVert P^{-1} \right\rVert}} \leq \frac{(\cos \delta)^{-1}}{1- (\cos\delta)^{-1}\left((1-u)^{-2}-1\right)}.$$ One shows that the right hand side equals $ (1-u)^2/\Psi_\delta(u)$. This finishes the proof.

We prove the first assertion. We choose $(v,\lambda)\in {\mathbb{S}}({\mathbb{C}}^n)\times {\mathbb{C}}$ to be a representative for $(v,\lambda)\in{\mathscr{P}}$. By assumption we have $d\, \mu(f,v,\lambda) \,d_{\mathbb{S}}(f,g)\leq \epsilon < 1$. This implies that $\mu(f,v,\lambda)<\infty$, which means that $D{\mathcal{F}}_f(v,\lambda)|_{(v,\lambda)^\perp}$ is invertible.

Let $A:= D{\mathcal{F}}_f(v,\lambda)|_{(v,\lambda)^\perp}$ and hence $\mu(f,v,\lambda) = {\left\lVert A^{-1} \right\rVert}$. Futher, write $\Delta:= [D(g-f)(v),0]|_{(v,\lambda)^\perp}$, so $A + \Delta = D{\mathcal{F}}_g(v,\lambda)|_{(v,\lambda)^\perp}$. We have $${\left\lVert \Delta \right\rVert}\leq {\left\lVert [D(g-f)(v),0] \right\rVert}= {\left\lVert D(g-f)(v) \right\rVert}\leq d  {\left\lVert g-f \right\rVert};$$ the last inequality by [@condition Lemma 16.46]. Since ${\left\lVert f \right\rVert}={\left\lVert g \right\rVert}=1$, we have that ${\left\lVert f-g \right\rVert}\leq d_{\mathbb{S}}(f,g)$. Therefore,

$${\left\lVert A^{-1} \right\rVert}{\left\lVert \Delta \right\rVert} \leq d{\left\lVert A^{-1} \right\rVert} {\left\lVert g-f \right\rVert}\leq d\;\mu(f,v,\lambda)\; d_{\mathbb{S}}(f,g) \leq \epsilon < 1.$$ We can apply [@condition Lemma 15.7] to deduce that $A+\Delta$ is invertible and that $$\mu(g,v,\lambda) = {\left\lVert (A+\Delta)^{-1} \right\rVert}
    \leq \frac{{\left\lVert A^{-1} \right\rVert}}{1-{\left\lVert \Delta \right\rVert}{\left\lVert A^ {-1} \right\rVert}}
    \leq \frac{1}{1-\epsilon}\;\mu(f,v,\lambda).$$ This proves the first assertion.

To prove the second assertion for $(\zeta,\eta),(v,\lambda)\in{\mathscr{P}}$ choose representatives $(\zeta,\eta),(v,\lambda)\in{\mathbb{S}}({\mathbb{C}}^n)\times {\mathbb{C}}$, such that $\delta:=d_{\mathbb{P}}((\zeta,\eta),(\lambda,\eta))=d_{\mathbb{S}}((\zeta,\eta),(\lambda,\eta))$. Put $u:=\delta\gamma(f,\zeta,\eta)\sqrt{8}$. By \[Theorem\_4.3\] and by our assumption we have $$u\leq 4\;  \delta \;d^2\sqrt{n}  \;\mu(f,\zeta,\eta)\leq \epsilon\leq 1/4 <1.$$ Using that $d\geq 2$ and from \[2dmu\](1) that $2d\,\mu(f,\zeta,\eta)\geq 1$ we obtain $\delta\leq \epsilon/4<\pi/16.$ Recall that $\Psi_\delta(u)/(1-u)^2 = 1+\cos\delta - (1-u)^{-2}.$ The right hand side is decreasing in $\delta$ and in $u$. This implies $$\frac{\Psi_\delta(u)}{(1-u)^2}=1+\cos\delta - (1-u)^{-2} \geq 1+\cos (\epsilon/4) - (1-\epsilon)^{-2}=\vartheta(\epsilon).$$ We get $\Psi_\delta(u)/(1-u)^2\geq \vartheta(\epsilon) > 0,$ by \[theta\_ineq\]. Summarizing, we have $\delta<\pi/16$, $u <1$ and $\Psi_\delta(u)>0$ and can therefore apply \[lipschitz0\] to deduce that $\mu(f,v,\lambda)<\infty$ and, using the submultiplicativity of the spectral norm, that $$\begin{aligned}
    \mu(f,v,\lambda)&\hspace{0.6cm}= {\left\lVert D{\mathcal{F}}_f(v,\lambda)_{(v,\lambda)^\perp}^{-1}\; D{\mathcal{F}}_f(\zeta,\eta)_{(\zeta,\eta)^\perp}\; D{\mathcal{F}}_f(\zeta,\eta)_{(\zeta,\eta)^\perp}^{-1} \right\rVert}\\       
    &\hspace{0.6cm}\leq  {\left\lVert D{\mathcal{F}}_f(v,\lambda)_{(v,\lambda)^\perp}^{-1}\; D{\mathcal{F}}_f(\zeta,\eta)_{(\zeta,\eta)^\perp} \right\rVert}\; {\left\lVert D{\mathcal{F}}_f(\zeta,\eta)_{(\zeta,\eta)^\perp}^{-1} \right\rVert}\\    
&\stackrel{\text{\cref{lipschitz0}}}{\leq} \frac{(1-u)^2}{\Psi_\delta(u)}\; \mu(f,\zeta,\eta) \leq  \frac{1}{\vartheta(\epsilon)}\; \mu(f,\zeta,\eta).
    \end{aligned}$$ Similiary we obtain $$\begin{aligned}
    \mu(f,\zeta,\eta)&= {\left\lVert D{\mathcal{F}}_f(\zeta,\eta)_{(\zeta,\eta)^\perp}^{-1}\; D{\mathcal{F}}_f(v,\lambda)_{(v,\lambda)^\perp}\; D{\mathcal{F}}_f(v,\lambda)_{(v,\lambda)^\perp}^{-1} \right\rVert}\\      
&\leq \frac{1}{(1-u)^2}\; \mu(f,v,\lambda) \leq \frac{1}{(1-\epsilon)^2}\; \mu(f,v,\lambda).
    \end{aligned}$$ This finishes the proof.

Proof of \[Theorem\_4.4\] {#ALH-proof}
-------------------------

Recall that we have put $\Theta: [0,1) \to {\mathbb{R}},\; \epsilon\mapsto 1-(1-\epsilon)^{-2}+\cos(\epsilon/4)-\epsilon.$ We need the following lemma to prove \[Theorem\_4.4\].

\[ALH-lemma\] Let $(q,\zeta,\eta),(q',\zeta',\eta')\in {\widehat{{\bf W}}}_{\mathbb{S}}$, $q\neq -q'$, such that the geodesic path $E$ connecting $q$ and $q'$ does not intersect $\Sigma$. Let $\epsilon < 1/5$ and $\omega < 1$. Then $$d_{\mathbb{S}}(q,q') \leq  \frac{ \epsilon\omega\Theta(\epsilon)}{4 d^{2} \sqrt{n} \mu^2(q,\zeta,\eta)}\hspace{0.3cm}\Longrightarrow \hspace{0.3cm} d_{\mathbb{P}}((\zeta,\eta),(\zeta',\eta')) \leq  \frac{\epsilon\omega}{4d^{2} \sqrt{n}  \mu(q,\zeta,\eta)}.$$

Let $L={\left\{(q_\tau,\zeta_\tau,\eta_\tau)\mid 0\leq \tau \leq 1\right\}}$ be the lifting of $E$ at $(q,\zeta,\eta)$ (see \[se:condition\] for definition of the lifting). Suppose the assertion were false. Then there exists some $0\leq \tau^* < 1$, such that $$d_{\mathbb{P}}((\zeta,\eta),(\zeta_{\tau^*},\eta_{\tau^*}))=\int_0^{\tau^*} {\left\lVert \dot{\zeta}_\tau,\dot{\eta}_\tau \right\rVert}{\mathrm{d}}\tau  =  \frac{\epsilon\omega}{4d^{2} \sqrt{n} \mu(q,\zeta,\eta)}.$$ Let $0\leq \tau\leq \tau^*$. From \[2dmu\](2) we obtain ${\left\lVert \dot{\zeta}_\tau,\dot{\eta}_\tau \right\rVert} \leq \mu(q_\tau,\zeta_\tau,\eta_\tau) {\left\lVert \dot{q}_\tau \right\rVert}$ and hence $$\frac{\epsilon\omega}{4d^{2} \sqrt{n} \mu(q,\zeta,\eta)}\leq \int_0^{\tau^*} \mu(q_\tau,\zeta_\tau,\eta_\tau) {\left\lVert \dot{q}_\tau \right\rVert}{\mathrm{d}}\tau  .$$ Using $d_{\mathbb{P}}((\zeta,\eta),(\zeta_\tau,\eta_\tau))\leq d_{\mathbb{P}}((\zeta,\eta),(\zeta_{\tau^*},\eta_{\tau^*}))$, $d_{\mathbb{S}}(q,q_\tau)\leq d_{\mathbb{S}}(q,q')$, from \[2dmu\](1) that $2d\mu(q,\zeta,\eta)\geq 1$ and from \[theta\_ineq\] that $\Theta(\epsilon)\leq 1$ we have by assumption $$d\, \mu(q,\zeta,\eta)\; \max{\left\{ d_{\mathbb{S}}(q,q_\tau),  4\; d\sqrt{n}\; d_{\mathbb{P}}((\zeta,\eta),(\zeta_\tau,\eta_\tau)) \right\}} \leq \epsilon \leq \frac{1}{5}.$$ \[lipschitz3\] implies that $\mu(q_\tau,\zeta_\tau,\eta_\tau)\leq \Theta(\epsilon)^{-1} \mu(q,\zeta,\eta)$. Hence, $$\int_{0}^{\tau^*}{\left\lVert (\dot{\zeta}_\tau,\dot{\eta}_\tau) \right\rVert} {\mathrm{d}}\tau\leq \frac{\mu(q,\zeta,\eta)}{\Theta(\epsilon)} \int_{0}^{\tau^*}  {\left\lVert \dot{q}_\tau \right\rVert} {\mathrm{d}}\tau 
    <   \frac{\mu(q,\zeta,\eta)}{\Theta(\epsilon)} d_{\mathbb{S}}(q,q'),$$ contradicting our assumption.

The proof is adapted from [@condition p. 335 - 338].

Let $E:=E_{f,g}={\left\{q_\tau\mid 0\leq \tau\leq 1\right\}}$ be the geodesic path connecting $f$ and $g$ and let $$L:=L_{f,g}={\left\{(q_\tau,\zeta_\tau,\eta_\tau)\mid 0\leq \tau\leq 1\right\}}$$ be the lifting of $E$ at $(g,\zeta,\eta)$. We first note that \[prop\_approx\_eigenpairs\] implies that, if $E\cap{\mathbf{\Sigma}}=\emptyset$, then $L\subset{{\bf V}}$.

We denote by $$0=\tau_0 < \tau_1 <\ldots < \tau_K =1,\quad (\zeta,\eta)=(v_0,\lambda_0),\ldots,(v_K,\lambda_K)=(v,\lambda).$$ the sequence of $\tau$’s and $(v,\lambda)$’s generated by <span style="font-variant:small-caps;">e-alh</span>, respectively. Further, for $0\leq i\leq K$ we denote $q_i:=q_{\tau_i}$ and $(\zeta_i,\eta_i):=(\zeta_{\tau_i},\eta_{\tau_i})$. We put $$\epsilon:=0.04,\quad \Theta:=\Theta(\epsilon)\approx 0.87488,\quad \omega:=2\Theta-1 \approx 0.74976 < 1.$$

For all $i\in{\left\{0,\ldots,K\right\}}$ the following holds. $$\label{ALH1.1}
    4\;d^2\sqrt{n}\; \mu(q_i,\zeta_i,\eta_i)\; d_{\mathbb{P}}((v_i,\lambda_i),(\zeta_i,\eta_i)) \leq \epsilon$$

<span style="font-variant:small-caps;">Proof of the Claim</span> We will proceed by induction. By construction \[ALH1.1\] holds for $i=0$. Let us assume that \[ALH1.1\] holds for all $i\leq j$. From \[lipschitz1\](2) we get that $$\label{ALH1.11}
    (1-\epsilon)^2 \mu(q_j,\zeta_j,\eta_j)\leq \mu(q_j,v_j,\lambda_j).$$ The stepsize of the algorithm <span style="font-variant:small-caps;">e-alh</span> is defined such that $$d_{\mathbb{S}}(q_j,q_{j+1}) \leq  \frac{\epsilon(1-\epsilon)^4  \omega \Theta}{4\; d^{2} \sqrt{n}\; \mu^2(q_j,v_j,\lambda_j)} \stackrel{\cref{ALH1.11}}{\leq} \frac{\epsilon \omega  \Theta}{4\; d^{2} \sqrt{n}\; \mu^2(q_j,\zeta_j,\eta_j)}.$$ \[ALH-lemma\] implies that $d_{\mathbb{P}}((\zeta_j,\eta_j),(\zeta_{j+1},\eta_{j+1})) \leq \epsilon\omega/(4d^{2} \sqrt{n}\mu(q_j,\zeta_j,\eta_j))$. Using that $2d\;\mu(q_j,\zeta_j,\eta_j)\geq 1$, $d\geq 2$, $\Theta<1$ and $\omega<1$ we get $$d\,\mu(q_j,\zeta_j,\eta_j) \, \max{\left\{ d_{\mathbb{S}}(q_j,q_{j+1}),4\;d\sqrt{n}\; d_{\mathbb{P}}((\zeta_j,\eta_j),(\zeta_{j+1},\eta_{j+1}))\right\}} \leq \epsilon,$$ so that \[lipschitz3\] implies $$\label{ALH1.5}
     \Theta\; \mu(q_j,\zeta_j,\eta_j)\leq\mu(q_{j+1},\zeta_{j+1},\eta_{j+1}) \leq \frac{1}{\Theta}\; \mu(q_j,\zeta_j,\eta_j).$$ We use the triangle inequality to get $$\begin{aligned}
    &\;d_{\mathbb{P}}((v_j,\lambda_j),(\zeta_{j+1},\eta_{j+1}))\nonumber\\
    \leq& \;d_{\mathbb{P}}((v_j,\lambda_j),(\zeta_j,\eta_j))+d_{\mathbb{P}}((\zeta_j,\eta_j),(\zeta_{j+1},\eta_{j+1}))\nonumber\\
    \leq& \;\frac{\epsilon(1+\omega)}{4\;d^2\sqrt{n}\; \mu(q_j,\zeta_j,\eta_j)}= \frac{\epsilon \Theta}{2\;d^2\sqrt{n}\; \mu(q_j,\zeta_j,\eta_j)},\label{ALH1.6}
    \end{aligned}$$ so that $$\begin{aligned}
    d^2\sqrt{2n}\,  \mu(q_{j+1},\zeta_{j+1},\eta_{j+1}) d_{\mathbb{P}}((v_j,\lambda_j),(\zeta_{j+1},\eta_{j+1})&)
     \leq \frac{\epsilon \Theta}{\sqrt{2}}\, \frac{\mu(q_{j+1},\zeta_{j+1},\eta_{j+1})}{\mu(q_j,\zeta_j,\eta_j)}\\
     &\stackrel{\cref{ALH1.5}}{\leq}  \frac{\epsilon}{\sqrt{2}} \approx 0.02828;
    \end{aligned}$$ Together with \[Theorem\_4.3\] this implies $\gamma(q_{j+1},\zeta_{j+1},\eta_{j+1}) < 0.1$. Using that $d\geq 2$, from \[2dmu\](1) that $2d\,\mu(q_j,\zeta_j,\eta_j)\geq 1$ and $\Theta< 1$ we further get $d_{\mathbb{P}}((v_j,\lambda_j),(\zeta_{j+1},\eta_{j+1})) \leq \epsilon/2 =0.02$ from \[ALH1.6\]. Recall from \[u\_and\_delta\] the definitions of $u(r)$ and $\delta(r)$. For $r=0.999933...$ we have $u(r)> 0.1$ and $\delta(r)= 0.02$. Using \[def\_approx\_eigenpair\] and \[gamma\_thm\] we see that $(v_j,\lambda_j)$ is an approximate eigenpair of $q_{j+1}$ with associated eigenpair $(\zeta_{j+1},\eta_{j+1})$. Applying Newton’s method with respect to $q_{j+1}$ to $(v_j,\lambda_j)$ halves the distance to $(\zeta_{j+1},\eta_{j+1})$, so $$\begin{aligned}
    d_{\mathbb{P}}((v_{j+1},\lambda_{j+1}),(\zeta_{j+1},\eta_{j+1})) &\hspace{0.15cm}\stackrel{\text{\cref{gamma_thm}}}{\leq} \frac{1}{2} \; d_{\mathbb{P}}((v_{j},\lambda_{j}),(\zeta_{j+1},\eta_{j+1}))\\
     &\hspace{0.7cm}\stackrel{\cref{ALH1.6}}{\leq}\frac{\epsilon\,\Theta }{4\;d^2\sqrt{n}\, \mu(q_j,\zeta_j,\eta_j)}\\
     &\hspace{0.7cm}\stackrel{\cref{ALH1.5}}{\leq}\frac{\epsilon }{4\,d^2\sqrt{n}\, \mu(q_{j+1},\zeta_{j+1},\eta_{j+1})}
     \end{aligned}$$ which is \[ALH1.1\] for $i=j+1$. The correctness of <span style="font-variant:small-caps;">e-alh</span> also follows from this.

It remains to estimate $K$, the number of iterations. In the same way we deduced \[ALH1.5\], we can deduce that for any $0\leq i\leq K-1$ and $\tau_i\leq\tau\leq \tau_{i+1}$ we have $\Theta\; \mu(q_i,\zeta_i,\eta_i)\leq\mu(q_{\tau},\zeta_{\tau},\eta_{\tau})$. Hence $$\int_{\tau_i}^{\tau_{i+1}} \mu^2(q_\tau,\zeta_\tau,\eta_\tau){\mathrm{d}}\tau \geq   \int_{\tau_i}^{\tau_{i+1}} \Theta^2 \mu^2(q_i,\zeta_i,\eta_i) {\mathrm{d}}\tau = \Theta^2 \;\mu^2(q_i,\zeta_i,\eta_i)\; (\tau_{i+1}-\tau_i)$$ We have set $(\tau_{i+1}-\tau_i) \leq \epsilon(1-\epsilon)^4\omega / \left[4\;d^{2} \sqrt{n}\; \mu^2(q_i,v_i,\lambda_i)\;d_{\mathbb{S}}(f,g)\right]$ as the stepsize. Further, \[ALH1.1\] and \[lipschitz1\](2) imply that for any $0\leq i\leq K$ we have $\vartheta(\epsilon)\; \mu(q_i,v_i,\lambda_i)\leq  \mu(q_i,\zeta_i,\eta_i).$ Thus $$\int_{\tau_i}^{\tau_{i+1}} \mu^2(q_\tau,\zeta_\tau,\eta_\tau){\mathrm{d}}\tau \geq  \frac{\Theta^2(1-\epsilon)^4\epsilon\vartheta(\epsilon)^2\omega}{ 4 \; d^{2} \sqrt{n}\;d_{\mathbb{S}}(f,g)},$$ which implies $$\int_{0}^{1} \mu^2(q_\tau,\zeta_\tau,\eta_\tau){\mathrm{d}}\tau \geq   K\; \frac{\Theta^2(1-\epsilon)^4\epsilon\vartheta(\epsilon)^2\omega}{ 4\;  d^{2}\sqrt{n}\;d_{\mathbb{S}}(f,g)},$$ For $\epsilon=0.04$ we have $\Theta^2(1-\epsilon)^4\epsilon\vartheta(\epsilon)^2\omega/4 \geq  1/246$ and therefore $$K\leq 246 \;d^2\sqrt{n}\;d_{\mathbb{S}}(f,g)\; \int_{0}^{1} \mu^2(q_\tau,\zeta_\tau,\eta_\tau){\mathrm{d}}\tau$$ as claimed.

Proof of \[Theorem\_4.7\] {#sec:Theorem_4.7}
=========================

We show that algorithm <span style="font-variant:small-caps;">draw-from-</span>$\rho^*$ has an average running time of ${\mathcal{O}}(dnN)$, where $N:=\dim_{\mathbb{C}}({{\mathcal{H}}})$.

Step 1. of algorithm <span style="font-variant:small-caps;">draw-from-</span>$\rho^*$ can be done via Beltran-Pardo randomization [@condition sec. 17.6]. By [@condition Prop. 17.21] this can be implemented with ${\mathcal{O}}(N)$ draws from $N({\mathbb{C}})$ and ${\mathcal{O}}(dnN)$ arithmetic operations.

For Step $2.$ draw $B\sim N({\mathbb{C}}^{(n-1)\times(n-1)})$. Let $Q$ be the $Q$-factor in the $QR$-decomposition of $B$. Then we put $U'=\mathrm{diag}(r_{ii}/{\left\lvert r_{ii} \right\rvert})\,Q$, where the $r_{ii}$ are the diagonal elements of the $R$ factor in the $QR$ decomposition of $B$. By [@matrix_eigenpair Sec. 9.1] we have $U'\sim {\mathcal{U}}(n-1)$ uniformly at random. Compute $V\in{\mathcal{U}}(n)$ with $Ve_1=\zeta$, for instance via Gram-Schmidt algorithm. Putting $U=\begin{bmatrix} \zeta, & V \begin{bmatrix} 0\\U'\end{bmatrix}\end{bmatrix}$ we have $U\in{\mathcal{U}}(n)$, such that $Ue_1=\zeta$, uniformly at random. The dominating complexity here is the $QR$ decomposition, which required ${\mathcal{O}}(n^3)$ arithmetic operations.

Given $\zeta\in{\mathbb{P}}({\mathbb{C}}^n)$ we can draw $a \sim N(\zeta^\perp)$ by drawing $a'\sim N({\mathbb{C}}^{n-1})$ and then put $a=U(0,a')^T$. This requires ${\mathcal{O}}(n)$ arithmetic operations. An implementation for drawing $h\sim N(R(\zeta))$ is given in [@condition algorithm 17.7]. Its number of arithmetic operations is ${\mathcal{O}}(N)$. Summarizing we can implement Step $3.$ with ${\mathcal{O}}(N)$ arithmetic operations. For drawing $R$ with density $e^{-R}\;\mathbf{1}_{{\left\{R\geq 0\right\}}}(R)$, one can draw $z\sim N({\mathbb{C}})$ and then put $R={\left\lVert z \right\rVert}^2$.

Alogether this shows that steps $1.$-$7$ require ${\mathcal{O}}(N)$ arithmetic operations.

The number of times we have to execute steps $4.$-$7$ is imposed by the [**if**]{}-statement in step 8. Let $E$ denote the expected number of iterations and let $C:=\operatorname*{\mathrm{Prob}}\limits_{({\mathbbm{f}},\zeta),\eta}{\left\{{\left\lVert D\,{\mathbbm{f}}(\zeta)+\eta^{d-1}P_\zeta^\perp \right\rVert}_F \leq {\left\lVert D\,{\mathbbm{f}}(\zeta) \right\rVert}_F\right\}}$ be the probability of the [**if**]{}-statement being true. For any $k\geq 1$ we have $$\operatorname*{\mathrm{Prob}}{\left\{ \text{The {\bf if}-statement is executed at least $k$ many times}\right\}} = (1-C)^{k-1},$$ which implies $E= \sum_{k=1}^\infty (1-C)^{k-1} = C^{-1}$. In \[C\] we show that $C\geq 2/(5\sqrt{\pi}\;n )$. Observe that every iteration requires ${\mathcal{O}}(1)$ many draws from $N({\mathbb{C}}^n)$ and the computation of a derivative and its Frobenius norm, which can be done with ${\mathcal{O}}(N)$ many arithmetic operations.

Summarizing, our implemention of algorithm <span style="font-variant:small-caps;">draw-from-</span>$\rho^*$ requires an expected number of ${\mathcal{O}}(dnN)$ arithmetic operations.

Proof of \[Theorem\_4.8\] {#sec:rho_star}
=========================

Before we can prove \[Theorem\_4.8\] we will have to compute the density $\rho^*$ itself. The probability density function associated to the Beltran-Pardo randomization is given in [@condition sec. 7.6]. We denote it by $\rho_\mathrm{BP}$.

\[beta\_density\] If we choose $R$ with density $e^{-R}\;\mathbf{1}_{{\left\{R\geq 0\right\}}}(R)$ and $\phi\in[0,2\pi)$ uniformly at random, putting $\eta:=R^\frac{1}{2(d-1)} \exp(i\phi)$ defines a random variable with density $$\beta(\eta):= \frac{(d-1)}{\pi}\;{\left\lvert \eta \right\rvert}^{2(d-2)}\;\exp(-{\left\lvert \eta \right\rvert}^{2(d-1)}).$$

Let $\alpha(R):=\exp(-R)\;\mathbf{1}_{{\left\{R\geq 0\right\}}}(R)$. Put $r:=R^\frac{1}{2(d-1)}$, such that we have $2(d-1)r^{2(d-2)+1}{\mathrm{d}}r = {\mathrm{d}}R$ and $$\alpha(R) {\mathrm{d}}R = 2(d-1)r^{2(d-2)+1}\;\exp(-r^{2(d-1)}) \;\mathbf{1}_{{\left\{r\geq 0\right\}}}(r) {\mathrm{d}}r =: \alpha'(r){\mathrm{d}}r.$$ We have defined the argument of the random variable $\eta$ as being uniform distributed in $[0,2\pi)$. Changing from polar coordinates to euclidean coordinates $\eta := r \exp(i\phi)$ we therefore get $$\alpha'(r) {\mathrm{d}}r {\mathrm{d}}\phi = \frac{(d-1)}{\pi}\;{\left\lvert \eta \right\rvert}^{2(d-2)}\;\exp(-{\left\lvert \eta \right\rvert}^{2(d-1)}) \;{\mathrm{d}}\eta,$$ which shows the assertion.

We can now describe $\rho^*$. Let $(\Omega,{\mathcal{E}},\operatorname*{\mathrm{Prob}})$ be the probability space $$\begin{aligned}
    \Omega :=& \Big\{({\mathbbm{f}},\zeta,\eta,U,a,h)\in  {\mathcal{H}}_{n,d}^{n-1}\times {\mathbb{P}}({\mathbb{C}}^n)\times{\mathbb{C}}\times {\mathcal{U}}(n)\times \zeta^\perp\times
     {\mathcal{H}}_{n,d} \mid \\
    &\hspace{1cm}{\mathbbm{f}}(\zeta)=0,\; Ue_1=\zeta,\; h\in R(\zeta)\Big\},
    \end{aligned}$$ so that $\psi({\mathbbm{f}},\zeta,\eta,U,a,h)= (f,\zeta,\eta)$, where $$f:=U\cdot \begin{bmatrix} \eta^{d-1}\langle X,\zeta\rangle^d + \langle X,\zeta \rangle^{d-1} \sqrt{d} a^T X' + h \\ {\mathbbm{f}}\end{bmatrix}.$$ The set of events ${\mathcal{E}}$ consists of the measurable subsets of $\Omega$ (with respect to the induced Lebesgue measure) and $\operatorname*{\mathrm{Prob}}(Y)= \operatorname*{\mathbb{E}}\limits_{({\mathbbm{f}},\zeta),a,h,U,\eta}\; \quad[\mathbf{1}_Y],$ where $({\mathbbm{f}},\zeta)\sim \rho_{\mathrm{BP}}$, $U\sim \mathrm{Unif} {\left\{U\in{\mathcal{U}}(n)\mid Ue_1=\zeta\right\}}$, $a\sim N(\zeta^\perp)$, $h\sim N(R(\zeta))$, $\eta\sim\beta$ and $\mathbf{1}_Y$ denotes the characteristic function of $Y\in{\mathcal{E}}$.

It is immediate from the description of the algorithm <span style="font-variant:small-caps;">draw-from-$\rho^*$</span> that that the probability density function $\rho^*$ is associated to a random variable $\psi^*={\ensuremath{\left.\psi\right|_{\Omega^*}}}$, where $(\Omega^*,{\mathcal{E}}, \operatorname*{\mathrm{Prob}}^*)$ is the probability space. $$\begin{aligned}
    \Omega^* =& {\left\{({\mathbbm{f}},\zeta,\eta,U,a,h)\in \Omega\mid {\left\lVert {\ensuremath{\left.D\,{\mathbbm{f}}(\zeta)\right|_{\zeta^\perp}}} + \eta^{d-1}P_\zeta^\perp \right\rVert}_F \leq {\left\lVert {\ensuremath{\left.D\,{\mathbbm{f}}(\zeta)\right|_{\zeta^\perp}}} \right\rVert}_F\right\}},
    \end{aligned}$$ and ${\mathcal{E}}^* = {\mathcal{E}}\cap \Omega^*$. In fact, $\rho^*$ is the *conditional distribution on $\Omega^*$,* that is $$\label{rhostar1}
        {\operatorname*{\mathrm{Prob}}}^*(Y) = \frac{\operatorname*{\mathrm{Prob}}(Y)}{\operatorname*{\mathrm{Prob}}(\Omega^*)} = \frac{1}{\operatorname*{\mathrm{Prob}}(\Omega^*)}\, \operatorname*{\mathbb{E}}\limits_{({\mathbbm{f}},\zeta),a,h,U,\eta}\; \quad[\mathbf{1}_Y].$$

\[C\] $\operatorname*{\mathrm{Prob}}(\Omega^*)\geq 2d/(5\sqrt{\pi}\,n)$.

From [@condition Lemma 17.19] we get that, if $({\mathbbm{f}},\zeta)\sim\rho_{PB}$, then we have that $\sqrt{d}^{\;-1}D\,{\mathbbm{f}}(\zeta) \in{\mathbb{C}}^{(n-1)\times (n-1)}$ is standard normal. We will use \[norm\_inequality\_gaussian\] with $a:=-\eta^{d-1}P_\zeta^\perp$. Observe that ${\left\lVert -\eta^{d-1}P_\zeta^\perp \right\rVert}_F = \sqrt{n-1}\;{\left\lvert \eta \right\rvert}^{d-1}$. We get $$\begin{aligned}
    \operatorname*{\mathrm{Prob}}(\Omega^*)&\hspace{0.6cm}= \hspace{0.5cm}\operatorname*{\mathbb{E}}\limits_{\eta}\;\operatorname*{\mathrm{Prob}}\limits_{({\mathbbm{f}},\zeta)}{\left\{{\left\lVert {\ensuremath{\left.D\,{\mathbbm{f}}(\zeta)\right|_{\zeta^\perp}}} + \eta^{d-1}P_\zeta^\perp \right\rVert}_F \leq {\left\lVert {\ensuremath{\left.D\,{\mathbbm{f}}(\zeta)\right|_{\zeta^\perp}}} \right\rVert}_F\right\}}\\
    &\stackrel{\text{\cref{norm_inequality_gaussian}}}{\geq} \operatorname*{\mathbb{E}}\limits_{\eta} \; \frac{1}{\sqrt{\pi}} \;  \frac{2\;\exp(-(n-1){\left\lvert \eta \right\rvert}^{2(d-1)}/4d)}{\sqrt{\frac{n-1}{d}}\;{\left\lvert \eta \right\rvert}^{d-1} + \sqrt{\frac{n-1}{d}\;{\left\lvert \eta \right\rvert}^{2(d-1)}+8}}
    \end{aligned}$$ Put $R:={\left\lvert \eta \right\rvert}^{2(d-1)}$. By definition $R$ has density $e^{-R}\;\mathbf{1}_{{\left\{R\geq 0\right\}}}(R)$. This shows

$$\begin{aligned}
    \operatorname*{\mathrm{Prob}}(\Omega^*)&\geq  \frac{2}{\sqrt{\pi}} \operatorname*{\mathbb{E}}\limits_{R}  \;  \frac{\exp(-(n-1)R/4d)}{\sqrt{\frac{n-1}{d}R} + \sqrt{\frac{n-1}{d}\;R+8}}\\
    &= \frac{2}{\sqrt{\pi}}\int\limits_{R\geq 0} \frac{\exp(-(n+3)R/4d)}{\sqrt{\frac{n-1}{d}R} + \sqrt{\frac{n-1}{d}\;R+8}} \; {\mathrm{d}}R.
    \end{aligned}$$

Making a change of variables $T:=\frac{n-1}{d}R$ the latter expression becomes $$\begin{aligned}
     &\frac{2d}{\sqrt{\pi}\,(n-1)}\int\limits_{T\geq 0} \frac{1}{\sqrt{T} + \sqrt{T+8}} \;\exp\left(-\frac{(n+3)}{4d(n-1)} T\right)\; {\mathrm{d}}T\\
     \stackrel{n\geq 2}{\geq}\; & \frac{2d}{ \sqrt{\pi}\,n}\int\limits_{T\geq 0} \frac{1}{\sqrt{T} + \sqrt{T+8}} \;\exp\left(-\frac{5}{4} T\right)\; {\mathrm{d}}T
     \end{aligned}$$ A computer based calculation shows $\int_{T\geq 0} \frac{1}{\sqrt{T} + \sqrt{T+8}} \;\exp\left(-\frac{5}{4} T\right)\; {\mathrm{d}}T \geq \frac{1}{5}$. This finishes the proof.

Recall from \[notation\_C\] the definition of ${\mathcal{C}}$. Let $$\phi: {{\bf V}}\to {\mathbb{R}},\; (g,\zeta,\eta)\mapsto \operatorname*{\mathbb{E}}\limits_{f\sim\mathrm{Unif}\;{\mathbb{S}}({{\mathcal{H}}})}\,{\mathcal{C}}\,\left(f,\left(\frac{g}{{\left\lVert g \right\rVert}},\zeta,\frac{\eta}{{\left\lVert g \right\rVert}^\frac{1}{d-1}}\right)\right).$$ Note the normalization of $g$ that is necessary since algorithm <span style="font-variant:small-caps;">alh</span> only works for polynomial systems of norm 1. By \[2dmu\](3) $\phi$ is unitarily invariant, that is, for all $U\in{\mathcal{U}}(n)$: $\phi(g,\zeta,\eta)=\phi(U.(g,\zeta,\eta))$. Further, by definition $\phi$ is scale invariant, that is, for all $s\in{\mathbb{C}}\backslash{\left\{0\right\}}$: $\phi(g,\zeta,\eta)=\phi(s^{d-1}g,\zeta,s\eta)$. \[Theorem\_4.8\] is obtained as a corollary from the following proposition, whose proof is adapted from [@matrix_eigenpair sec. 10.2].

Let $\Xi: {{\bf V}}\to {\mathbb{R}}$ be a measurable, unitarily invariant and scale invariant function. Then $\operatorname*{\mathbb{E}}\limits_{(f,\zeta,\eta)\sim\rho^*} \Xi(f,\zeta,\eta) \leq 5\sqrt{\pi}\,n\,\operatorname*{\mathbb{E}}\limits_{(f,\zeta,\eta)\sim\rho} \Xi(f,\zeta,\eta)$

While the proof itself is very technical, its underlying idea is explained quickly. In \[important\_inequality\] and \[important\_inequality2\] we show that on $\Omega^*$ we have the inequality $\rho^*\leq \frac{\rho}{\operatorname*{\mathrm{Prob}}(\Omega^*)}$ and can therefore bound

$$\operatorname*{\mathbb{E}}_{X\sim \rho^*}[X] \leq \int_{\Omega^*}  X\,\frac{\rho}{\operatorname*{\mathrm{Prob}}(\Omega^*)}\; {\mathrm{d}}\Omega^* \leq \frac{1}{\operatorname*{\mathrm{Prob}}(\Omega^*)}\int_{\Omega}  X\,\rho\; {\mathrm{d}}\Omega=\frac{\operatorname*{\mathbb{E}}\limits_{X\sim\rho}[X]}{\operatorname*{\mathrm{Prob}}(\Omega^*)}.$$ The claim follows then using \[C\].

To prove this let $C:=\operatorname*{\mathrm{Prob}}(\Omega^*)$ and let $\mathbf{1}_{\Omega^*}$ denote the characteristic function of $\Omega^*$. From \[rhostar1\] we get that $$\label{rhostar1.1}
    \operatorname*{\mathbb{E}}\limits_{(f,\zeta,\eta)\sim\rho^*} \Xi(f,\zeta,\eta) = \frac{1}{C} \operatorname*{\mathbb{E}}\limits_{({\mathbbm{f}},\zeta),a,h,U,\eta} \Xi(f,\zeta,\eta)\;\mathbf{1}_{\Omega^*},$$ where $$\label{rhostar2}
f:=U\cdot \begin{bmatrix} \eta^{d-1}\langle X,\zeta\rangle^d + \langle X,\zeta \rangle^{d-1} \sqrt{d} a^T X + h \\ {\mathbbm{f}}\end{bmatrix}.$$ By assumption $\Xi$ is unitarily invariant. It is an easy exercise to show that $\mathbf{1}_{\Omega^*}$ is unitarily invariant, too.

Let ${\mathcal{Z}}(\zeta):={\left\{M\in{\mathbb{C}}^{(n-1)\times n}\mid M\zeta =0\right\}}$, $M:=D{\mathbbm{f}}(\zeta)\in{\mathcal{Z}}(\zeta)$ and let $\psi:{\mathcal{H}}_{n,d}^{n-1}\times {\mathbb{C}}\to {\mathbb{R}}$ be a measurable function. By \[orthogonal\_decomposition\] ${\mathbbm{f}}={\mathbbm{f}}(M,\zeta,k)$ is a function of $M$, $\zeta$ and $k$. By [@condition Prop. 18.11] we have $$\operatorname*{\mathbb{E}}\limits_{({\mathbbm{f}},\zeta)\sim \rho_{\mathrm{BP}}} \psi({\mathbbm{f}},\zeta) = \operatorname*{\mathbb{E}}_{(M,\zeta)} \operatorname*{\mathbb{E}}_{k}\; \psi({\mathbbm{f}}(M,\zeta,k),\zeta),$$ where $k\sim N(R(\zeta)^{n-1})$, $R(\zeta)$ being as in \[orthogonal\_decomposition\], and $(M,\zeta)$ has $(2\pi)^{-1} \varphi_{{\mathbb{C}}^{n-1}}(0)\varphi(M) \mathrm{NJ}p_1(M,\zeta)$ as density function, where $p_1$ is the projection $(M,\zeta)\to M$. From [@condition Lemma 18.6] and [@condition Lemma 18.12] we get that, $$\begin{aligned}
    \operatorname*{\mathbb{E}}_{M,\zeta,k} \psi({\mathbbm{f}},\zeta)   &=\frac{\varphi_{{\mathbb{C}}^{n-1}}(0)}{2\pi } \int\limits_{\zeta\in{\mathbb{S}}({\mathbb{C}}^n)} \operatorname*{\mathbb{E}}\limits_{M,k}{\left\lvert \det  {\ensuremath{\left.M\right|_{\zeta^\perp}}} \right\rvert}^2 \psi({\mathbbm{f}},\zeta)\,{\mathrm{d}}{\mathbb{S}}({\mathbb{C}}^n)\\
    &=\frac{\varphi_{{\mathbb{C}}^{n-1}}(0)}{2\pi d^{n-1}} \int\limits_{\zeta\in{\mathbb{S}}({\mathbb{C}}^n)} \operatorname*{\mathbb{E}}\limits_{M,k}{\left\lvert \det \sqrt{d} {\ensuremath{\left.M\right|_{\zeta^\perp}}} \right\rvert}^2 \psi({\mathbbm{f}},\zeta)\,{\mathrm{d}}{\mathbb{S}}({\mathbb{C}}^n),
    \end{aligned}$$ where $k\sim N(R(\zeta)^{n-1})$, $M\sim N({\mathcal{Z}}(\zeta))$ and we have $\varphi_{{\mathbb{C}}^{n-1}}(0) = \pi^{-(n-1)}$.

If $\psi$ is unitarily invariant, that is, if for all $U\in{\mathcal{U}}(n): \psi(U.f,U\zeta)=\psi(f,\zeta)$, we may replace $\zeta$ by $e_1$ in the upper expression so that $$\operatorname*{\mathbb{E}}_{M,\zeta,k} \psi({\mathbbm{f}},\zeta)
    = \frac{\mathrm{vol}{\mathbb{S}}({\mathbb{C}}^n)}{2\pi^{n}d^{n-1}} \operatorname*{\mathbb{E}}\limits_{k,M}\;{\left\lvert \det \sqrt{d} {\ensuremath{\left.M\right|_{e_1^\perp}}} \right\rvert}^2\; \psi({\mathbbm{f}},e_1).$$ Observe that ${\mathcal{Z}}(e_1)={\left\{[0,M]\mid M\in{\mathbb{C}}^{(n-1)\times (n-1)}\right\}}$ and that ${\ensuremath{\left.[0,M]\right|_{e_1^\perp}}}=M$. In the following we abuse notation and put $M:={\ensuremath{\left.M\right|_{e_1^\perp}}} \in {\mathbb{C}}^{(n-1)\times (n-1)}$.

We now put $\psi({\mathbbm{f}},\zeta):=\frac{1}{C}\,\operatorname*{\mathbb{E}}\limits_{a,h,U,\eta}\; \Xi(f,\zeta,\eta)\;\mathbf{1}_{\Omega^*}$ and obtain from \[rhostar1.1\] and the above that $$\operatorname*{\mathbb{E}}\limits_{(f,\zeta,\eta)\sim\rho^*} \Xi(f,\zeta,\eta)=\frac{\mathrm{vol}\,{\mathbb{S}}({\mathbb{C}}^n)}{2\pi^{n}d^{n-1}\;C}\;\operatorname*{\mathbb{E}}\limits_{k,M,a,h,\eta} {\left\lvert \det \sqrt{d}M \right\rvert}^2 \Xi(f,e_1,\eta)\mathbf{1}_{\Omega^*},\label{rhostar3}$$ where $k\sim N(R(e_1)^{n-1})$, $M\sim N({\mathbb{C}}^{(n-1)\times (n-1)})$, $a\sim N({\mathbb{C}}^{n-1})$, $h\sim N(R(e_1))$ and $\eta\sim \beta$, where $\beta$ is as in \[beta\_density\]. Observe that we have already integrated over $U$ (since $\Xi$ is unitarily invariant, the integrand is independent of $U$). To keep track, recall that by \[rhostar2\] we now have $$f= \eta^{d-1}X_1^de_1 + X_1^{d-1}  \sqrt{d}\begin{bmatrix} a^T\\ M \end{bmatrix} (X_2,\ldots,X_n)^T + \begin{bmatrix} h\\ k \end{bmatrix}$$ and since ${\ensuremath{\left.D{\mathbbm{f}}(e_1)\right|_{e_1^\perp}}}= M$ we have $\mathbf{1}_{\Omega^*} = \mathbf{1}_{\Omega^*}(M,\eta)$ Put $H:=[ h,k]^T$. Using Fubini’s theorem we see that \[rhostar3\] equals $$\frac{\mathrm{vol} \;{\mathbb{S}}({\mathbb{C}}^n)}{2\pi^{n}\;d^{n-1}\;C}\ \;\operatorname*{\mathbb{E}}\limits_{a,H} \;\left[\operatorname*{\mathbb{E}}\limits_{\eta,M}\; {\left\lvert \det \sqrt{d}M \right\rvert}^2\; \Xi(f,e_1,\eta)\;\mathbf{1}_{\Omega^*}(M,\eta)\right],\label{rhostar4}$$ We have put the brackets to indicate which part we compute next. By definition we have that $$\begin{aligned}
\label{rhostar10}
    &\operatorname*{\mathbb{E}}\limits_{\eta,M}\;{\left\lvert \det \sqrt{d}M \right\rvert}^2\; \Xi(f,e_1,\eta)\;\mathbf{1}_{\Omega^*}(M,\eta)\\
    =&\frac{1}{\pi^{(n-1)^2}}\operatorname*{\mathbb{E}}\limits_{\eta} \int\limits_{M} {\left\lvert \det \sqrt{d}M \right\rvert}^2\Xi(f,e_1,\eta)\mathbf{1}_{\Omega^*}(M,\eta)\exp(-{\left\lVert M \right\rVert}_F^2)\,{\mathrm{d}}{\mathbb{C}}^{(n-1)\times (n-1)}. \nonumber
    \end{aligned}$$ Setting $\sqrt{d}A:= \sqrt{d}M + \eta^{d-1}I$ we get ${\left\lVert A \right\rVert}_F^2 = {\left\lVert M+\sqrt{d}^{\;-1}\;\eta^{d-1} I  \right\rVert}_F^2$ and $$\begin{aligned}
\label{important_inequality}
\mathbf{1}_{\Omega^*}(M,\eta)=1&\stackrel{\text{by definition}}{\Longleftrightarrow} \quad {\left\lVert M+\sqrt{d}^{\;-1}\;\eta^{d-1} I  \right\rVert}_F^2 \leq {\left\lVert M \right\rVert}_F^2
\Longleftrightarrow  \exp(-{\left\lVert M \right\rVert}_F^2) \leq \exp(-{\left\lVert A \right\rVert}_F^2).\end{aligned}$$ From \[rhostar10\] and using that $\mathbf{1}_{\Omega^*}(M,\eta)\leq 1$ we therefore get $$\label{important_inequality2}
    \operatorname*{\mathbb{E}}\limits_{\eta,M}{\left\lvert \det \sqrt{d}M \right\rvert}^2 \Xi(f,e_1,\eta)\mathbf{1}_{\Omega^*}(M,\eta)
    \leq \operatorname*{\mathbb{E}}\limits_{\eta,A}\;{\left\lvert \det (\sqrt{d}A-\eta^{d-1}I) \right\rvert}^2 \Xi(f,e_1,\eta),$$ where $A\sim N({\mathbb{C}}^{(n-1)\times (n-1)})$.

Plugging into \[rhostar4\] and then into \[rhostar3\] we obtain $$\begin{aligned}
\label{rhostar5}
    \operatorname*{\mathbb{E}}\limits_{(f,\zeta,\eta)\sim\rho^*} \Xi(f,\zeta,\eta)\nonumber
    &\hspace{0.5cm}\leq\hspace{0.72cm} \frac{\mathrm{vol} \,{\mathbb{S}}({\mathbb{C}}^n)}{2\pi^{n}d^{n-1}C}\; \operatorname*{\mathbb{E}}\limits_{a,H,A,\eta}\;{\left\lvert \det (\sqrt{d}A-\eta^{d-1}I) \right\rvert}^2 \Xi(f,e_1,\eta)\nonumber\\
    &\stackrel{\text{\cref{beta_density}}}{=}\;\frac{\mathrm{vol} \,{\mathbb{S}}({\mathbb{C}}^n)}{2\pi^{n}d^{n-1}C} \;\int_{\eta\in{\mathbb{C}}} E(\eta) \; \frac{(d-1)}{\pi}\; {\left\lvert \eta \right\rvert}^{2(d-2)}\; e^{-{\left\lvert \eta \right\rvert}^{2(d-1)}} {\mathrm{d}}\eta;\end{aligned}$$ where $E(\eta):=\operatorname*{\mathbb{E}}\limits_{a,H,A} \;{\left\lvert \det (\sqrt{d}A-\eta^{d-1}I) \right\rvert}^2\; \Xi(f,e_1,\eta)$ is defined as in \[integration\] (note that the $H$ here is $h$ in \[integration\]). By \[integration\] we have that $$\label{rhostar6}
\operatorname*{\mathbb{E}}\limits_{f\sim N({{\mathcal{H}}})}\Xi_\text{av}(f)
= \frac{(d-1)^2\mathrm{vol}\;{\mathbb{S}}({\mathbb{C}}^n)}{2\pi^{n+1}{\mathcal{D}}(n,d)} \int\limits_{\eta\in{\mathbb{C}}} E(\eta) {\left\lvert \eta \right\rvert}^{2(d-2)} e^{-{\left\lvert \eta \right\rvert}^{2(d-1)}} {\mathrm{d}}\eta,$$ From \[rhostar5\] and \[rhostar6\] we get $$\label{rhostar7}
    \operatorname*{\mathbb{E}}\limits_{(f,\zeta,\eta)\sim\rho^*} \Xi(f,\zeta,\eta)
    \;\leq\; \frac{(d^n-1)}{d^{n-1}\; (d-1)\;C}\;\operatorname*{\mathbb{E}}\limits_{f\sim N({{\mathcal{H}}})}\Xi_\text{av}(f).$$ Since $\Xi$ is scale invariant we have $\operatorname*{\mathbb{E}}\limits_{f\sim N({{\mathcal{H}}})}\Xi_\text{av}(f)= \operatorname*{\mathbb{E}}\limits_{f\sim \mathrm{Unif}\;{\mathbb{S}}({{\mathcal{H}}})}\Xi_\text{av}(f)$ and using the coarea formula (\[coarea\_formula\]) on the projection $\pi_1:{{\bf V}}\to{{\mathcal{H}}}$ we get $\operatorname*{\mathbb{E}}\limits_{f\sim \mathrm{Unif}\;{\mathbb{S}}({{\mathcal{H}}})}\Xi_\text{av}(f)= \operatorname*{\mathbb{E}}\limits_{(f,\zeta,\eta)\sim \rho}\Xi(f,\zeta,\eta)$. From \[C\] we have $C\geq 2d/(5\sqrt{\pi}\;n)$ and since $d\geq 2$ we have $\frac{d^n-1}{d^{n-1} (d-1)}= \frac{1-d^{-n}}{1-d^{-1}}\leq 2$. Plugging everything into \[rhostar7\] shows $$\operatorname*{\mathbb{E}}\limits_{(f,\zeta,\eta)\sim\rho^*} \Xi(f,\zeta,\eta)
    \;\leq\; \frac{5\sqrt{\pi}n}{d}\;\operatorname*{\mathbb{E}}\limits_{f\sim N({{\mathcal{H}}})}\Xi_\text{av}(f),$$ which finishes the proof.

Proof of \[Proposition\_1.4\] {#proof_Proposition_1.4}
=============================

Let $K:=K(f,(g,\zeta,\eta))$. By [@condition Theorem 17.3, eq. (17.1)] we have $$\label{steps_ALH}
    K\geq 74 \; d^\frac{5}{2} \int_0^1 {\left\lVert \zeta_t,\eta_t \right\rVert}^{2(d-1)}{\left\lVert {\mathcal{F}}_{q_t} \right\rVert}^2{\left\lVert {\ensuremath{\left.D{\mathcal{F}}_{q_t}(\zeta_t,\eta_t)\right|_{(\zeta_t,\eta_t)^\perp}}}^{-1} \right\rVert}^2 {\left\lVert \frac{{\mathrm{d}}q_t}{{\mathrm{d}}t} \right\rVert} {\mathrm{d}}t;$$ Here $q_t:=tg + (1-t)f$ and $(\zeta_t,\eta_t)$ denotes some representative for an h-eigenpair $(\zeta_t,\eta_t)\in{\mathscr{P}}$ of $q_t$ and ${\left\lVert \cdot \right\rVert}$ is the spectral norm for linear operators (see \[A3\]). In \[2dmu\] we prove that $${\left\lVert {\ensuremath{\left.D{\mathcal{F}}_{q_t}(\zeta,\eta)\right|_{(\zeta,\eta)^\perp}}}^{-1} \right\rVert} \geq \frac{1}{d\,\left({\left\lVert q_t \right\rVert}+\max{\left\{{\left\lvert \eta \right\rvert}^{d-1},{\left\lvert \eta \right\rvert}^{d-2}\right\}}\right)}.$$ Using that ${\left\lVert {\mathcal{F}}_{q_t} \right\rVert}^2 = {\left\lVert q_t \right\rVert}^2+{\left\lVert \Lambda^{d-1}X \right\rVert}^2 = {\left\lVert q_t \right\rVert}^2 + \frac{n}{d}$ we deduce from \[steps\_ALH\] $$\label{steps_ALH2}
    K\geq 74 \; d^\frac{5}{2} \int_0^1  \frac{({\left\lVert q_t \right\rVert}^2 + \frac{n}{d})\,{\left\lVert \zeta_t,\eta_t \right\rVert}^{2(d-1)}\, {\left\lVert \frac{{\mathrm{d}}q_t}{{\mathrm{d}}t} \right\rVert}}{d^2\,\left({\left\lVert q_t \right\rVert}+\max{\left\{{\left\lvert \eta \right\rvert}^{d-1},{\left\lvert \eta \right\rvert}^{d-2}\right\}}\right)^2}\,{\mathrm{d}}t.$$ If $f,g\sim N({\mathcal{H}}_{n,d}^n)$, then $((1-t)^2+t^2)^{-1}q_t\sim N({\mathcal{H}}_{n,d}^n)$ (see \[A1\] for details on the distribution $N({\mathcal{H}}_{n,d}^n)$).

Let ${\mathbb{S}}:={\left\{x\in{\mathbb{C}}^n\mid x^T\overline{x}=1\right\}}$ and $\chi_{2k}^2$ denote the $\chi^2$ distribution with $2k$ degrees of freedom. If $q\sim N({\mathcal{H}}_{n,d}^n)$ and $(v,\lambda)\in{\mathbb{S}}\times {\mathbb{C}}$ is an eigenpair of $q$, that is chosen uniformly at random from all eigenpairs of $q$, we can deduce from [@distr Theorem 1.1(2)] that $$\operatorname*{\mathrm{Prob}}{\left\{{\left\lvert \lambda \right\rvert}> 1\right\}} = \frac{d-1}{d^n-1} \sum_{k=1}^n d^{n-k} \operatorname*{\mathrm{Prob}}\limits_{X\sim \chi^2_{2k}}{\left\{ X\geq 2\right\}}.$$ Let us put $\eta^{d-1}=\lambda$, $\zeta=v$. Using $\operatorname*{\mathrm{Prob}}\limits_{X\sim \chi^2_{2k}}{\left\{ X\geq 2\right\}} \geq \operatorname*{\mathrm{Prob}}\limits_{X\sim \chi^2_{2}}{\left\{ X\geq 2\right\}} = e^{-1}$, we obtain $\operatorname*{\mathrm{Prob}}{\left\{{\left\lvert \eta \right\rvert}\geq 1\right\}}> e^{-1}$ and consequently $$\label{steps_ALH3}
\operatorname*{\mathrm{Prob}}{\left\{{\left\lVert \zeta,\eta \right\rVert}^{2(d-1)}\geq 2^{2(d-1)}\right\}}> e^{-1}.$$ Furthermore, we have $\frac{{\mathrm{d}}q_t}{{\mathrm{d}}t}= g-f$ and $(g-f)\sim N({\mathcal{H}}_{n,d}^n)$, which implies that ${\left\lVert g-f \right\rVert}^2\sim \chi^2_{2N}$, where $N=\dim_{\mathbb{C}}{\mathcal{H}}_{n,d}^n\geq 1$ and therefore

$$\label{steps_ALH4}
    \operatorname*{\mathrm{Prob}}{\left\{{\left\lVert \frac{{\mathrm{d}}q_t}{{\mathrm{d}}t} \right\rVert}\geq \frac{1}{\sqrt{2}}\right\}}\geq \operatorname*{\mathrm{Prob}}\limits_{X\sim \chi^2_{2}}{\left\{ X\geq \frac{1}{2}\right\}} = e^\frac{-1}{4}.$$

For ${\left\lvert \eta \right\rvert}\geq 1$ we have $$\label{steps_ALH8}
\frac{{\left\lVert q_t \right\rVert}^2 + \frac{n}{d}}{d^2\left({\left\lVert q_t \right\rVert}+\max{\left\{{\left\lvert \eta \right\rvert}^{d-1},{\left\lvert \eta \right\rvert}^{d-2}\right\}}\right)^2} \leq \frac{n}{d^3}$$ Hence, using \[steps\_ALH3\], \[steps\_ALH4\] and \[steps\_ALH8\] in \[steps\_ALH2\] we obtain $$\begin{aligned}
\operatorname*{\mathrm{Prob}}{\left\{K\geq \frac{74}{\sqrt{2}}\,  d^\frac{5}{2}\, \frac{n}{d^3}\,2^{2(d-1)}\right\}}\geq &\operatorname*{\mathrm{Prob}}{\left\{{\left\lvert \eta \right\rvert}\geq 1 \text{ and } {\left\lVert \frac{{\mathrm{d}}q_t}{{\mathrm{d}}t} \right\rVert}\geq \frac{1}{2}\right\}}\\
\geq &\operatorname*{\mathrm{Prob}}{\left\{{\left\lvert \eta \right\rvert}\geq 1\right\}}+\operatorname*{\mathrm{Prob}}{\left\{{\left\lVert \frac{{\mathrm{d}}q_t}{{\mathrm{d}}t} \right\rVert}\geq \frac{1}{2}\right\}} -1\\
\geq &e^{-1} + e^\frac{-1}{4} - 1 \approx 0.1467.\end{aligned}$$ This finishes the proof.

Complex random variables {#A1}
========================

Let $X\in{\mathbb{C}}$ be a complex random variable. The expectation of $X$ is $$\operatorname*{\mathbb{E}}X = \operatorname*{\mathbb{E}}\Re(X) + i \operatorname*{\mathbb{E}}\Im(X).$$ The variance of $X$ is defined as $\mathrm{Var}(X):= \operatorname*{\mathbb{E}}{\left\lvert X-\operatorname*{\mathbb{E}}X \right\rvert}^2=\operatorname*{\mathbb{E}}{\left\lvert X \right\rvert}^2-{\left\lvert \operatorname*{\mathbb{E}}X \right\rvert}^2$.

Suppose that $W$ is a finite dimensional complex vector space with hermitian inner product and put $k:=\dim_{\mathbb{C}}W$. If $z\in W$ is distributed with density $\varphi_W(z) :=  \pi^{-k}\cdot \exp(-\lVert z\rVert^2),$ we say that $z$ is distributed according to the standard normal distribution on $W$ and write $z\sim N(W)$. If it is clear from the context which space is meant, we omit the subscript $W$ in $\varphi_W$. Clearly, the standard normal distribution is invariant under unitary transformation of basis.

A special case worth mentioning is the following. If $z\in{\mathbb{C}}$ is chosen at random with density $\varphi_{{\mathbb{C}}}$, we write $z\sim N({\mathbb{C}})$. It is easy to see that if $z\sim N({\mathbb{C}})$ then $\Re(z)$ and $\Im(z)$ are independent real gaussian random variables with mean $0$ and variance $\frac{1}{2}$. This shows that $$\label{mean_and_variance}
    \operatorname*{\mathbb{E}}z = 0,\quad \text{and}\quad \mathrm{Var}(z) = 1.$$

\[norm\_inequality\_gaussian\] Let $a\in {\mathbb{C}}^m$ be fixed. Then $$\operatorname*{\mathrm{Prob}}\limits_{z\sim N({\mathbb{C}}^m)}{\left\{ {\left\lVert z-a \right\rVert}\leq {\left\lVert z \right\rVert}\right\}}\geq \frac{1}{\sqrt{\pi}} \;  \frac{2\;\exp(-{\left\lVert a \right\rVert}^2/4)}{{\left\lVert a \right\rVert} + \sqrt{{\left\lVert a \right\rVert}^2+8}}.$$

We have ${\left\lVert z-a \right\rVert}\leq {\left\lVert z \right\rVert}$, if and only if ${\left\lVert a \right\rVert}^2\leq 2\Re\langle z,a\rangle$. By unitary invariance of $N({\mathbb{C}}^m)$ we may assume that $a=({\left\lVert a \right\rVert},0,\ldots,0)\in{\mathbb{C}}^m$. Hence $\Re\langle z,a\rangle ={\left\lVert a \right\rVert} \Re\langle z,e_1\rangle$. Observe that $\Re\langle z,e_1\rangle$ is a real gaussian random variable with mean $0$ and variance $\frac{1}{2}$. This shows that $$\operatorname*{\mathrm{Prob}}\limits_{z\sim N({\mathbb{C}}^m)}{\left\{{\left\lVert z-a \right\rVert}\leq {\left\lVert z \right\rVert}\right\}}= \frac{1}{\sqrt{\pi}}\int\limits_{{\left\lVert a \right\rVert}/2}^\infty \exp(-x^2) {\mathrm{d}}x.$$ From [@stegun eq. (7.1.13)] we get the inequality $$\int\limits_{x}^\infty \exp(-t^2) {\mathrm{d}}t \geq \frac{\exp(-x^2)}{x + \sqrt{x^2+2}},\quad x\geq 0,$$ which finishes the proof.

Let $A\in{\mathbb{C}}^{m\times m}$. For $1\leq i,j\leq m$ we denote by $A_{i,j}$ the $(i,j)$-entry of $A$ and by $A^{i,j}$ the matrix that is obtained from $A$ by removing the $i$-th row and the $j$-th column.

\[equation\_random\_matrix\] Suppose that the entries of a random complex matrix $A$ are distributed independently and that all of them have finite first and second moment (the distribution does not necessarily has to be standard normal).

Let $1\leq i\leq m$ and $A'$ be the matrix that is obtained by replacing the $i$-th row of $A$ by the (deterministic) $i$-th row of $\operatorname*{\mathbb{E}}A$. Then we have that $\operatorname*{\mathbb{E}}{\left\lvert \det A \right\rvert}^2 = \operatorname*{\mathbb{E}}{\left\lvert \det A' \right\rvert}^2 + \sum_{j=1}^m \mathrm{Var}(A_{i,j}) \operatorname*{\mathbb{E}}{\left\lvert \det A^{i,j} \right\rvert}^2.$

We have $\det A = \sum_{j=1}^m (-1)^{j+i}A_{i,j}\cdot  \det A^{i,j}$ by Laplace’s expansion. Thus $${\left\lvert \det A \right\rvert}^2 = \det A \cdot \det \overline{A} = \sum_{j,j'=1}^m (-1)^{j+j'}  A_{i,j}\overline{A}_{i,j'}\cdot \det A^{i,j}\det \overline{A}^{i,j'}.$$ The independence of the $A_{i,j}$ implies that $$\operatorname*{\mathbb{E}}A_{i,j}\overline{A}_{i,j'} \det A^{i,j}\det \overline{A}^{i,j'}
     = 
 \operatorname*{\mathbb{E}}[A_{i,j}\overline{A}_{i,j'}]\cdot  \operatorname*{\mathbb{E}}[\det A^{i,j} \det \overline{A}^{i,j'}].$$ If $j=j'$, we have $\operatorname*{\mathbb{E}}[A_{i,j}\overline{A}_{i,j'}] = \operatorname*{\mathbb{E}}A_{i,j}\operatorname*{\mathbb{E}}\overline{ A_{i,j'}} + \mathrm{Var}(A_{i,j}) $, and if $j\neq j'$ we have $\operatorname*{\mathbb{E}}[A_{i,j}\overline{A}_{i,j'}] = \operatorname*{\mathbb{E}}A_{i,j}  \operatorname*{\mathbb{E}}\overline{A}_{i,j'}$, so that $$\begin{aligned}
\operatorname*{\mathbb{E}}{\left\lvert \det A \right\rvert}^2
 = &\sum_{j,j'=1}^m (-1)^{j+j'} \operatorname*{\mathbb{E}}[ A_{i,j}\overline{A}_{i,j'}]\cdot \operatorname*{\mathbb{E}}[\det A^{i,j}\det \overline{A}^{i,j'}]\\
  = &\sum_{j,j'=1}^m (-1)^{j+j'} \operatorname*{\mathbb{E}}A_{i,j} \operatorname*{\mathbb{E}}\overline{A_{i,j'}}\cdot  \operatorname*{\mathbb{E}}[\det A^{i,j}\det \overline{A}^{i,j'}]+ \sum_{j=1}^m \mathrm{Var}(A_{i,j})\operatorname*{\mathbb{E}}[\det A^{i,j}\det \overline{A}^{i,j}]\\
  =& \operatorname*{\mathbb{E}}{\left\lvert \det A' \right\rvert}^2 + \sum_{j=1}^m \mathrm{Var}(A_{i,j})\operatorname*{\mathbb{E}}{\left\lvert \det A^{i,j} \right\rvert}^2,\end{aligned}$$ which shows the assertion.

The Gamma function {#A2}
==================

Recall that the Gamma function is defined by $\Gamma(n):= \int_{t=0}^\infty t^{n-1} e^{-t} {\mathrm{d}}t$ for a positive real number $n >0$. It is well known that $\Gamma(n+1)=n\Gamma(n)$ and, if $n$ is a positive integer, that $\Gamma(n)=(n-1)!$.

\[gamma\_lemma\] Let $n\geq 2$. We have $\Gamma(1/n)\leq \frac{\sqrt{\pi}}{2}n$ and $\Gamma(1+1/n)\leq \frac{\sqrt{\pi}}{2}$.

We have $\Gamma(1/n) = n \Gamma(1+1/n)$. The Gamma function is convex, which shows that for $n\geq 2$ we have $\Gamma(1+1/n)\leq \max{\left\{\Gamma(1),\Gamma(3/2)\right\}}=~\sqrt{\pi}/2$.

The *upper incomplete Gamma function* is defined as $\Gamma(n,x):= \int\limits_{x}^\infty t^{n-1} e^{-t} {\mathrm{d}}t,$ where $x\geq 0$. The following is [@distr Lemma 2.5, Prop. 2.6].

\[auxiliary\_lemma\]

1.  Let $x\geq 0$ and $n\geq 1$. Then $\Gamma(n,x) = (n-1)! \, e^{-x} \sum\limits_{k=0}^{n-1} \frac{x^k}{k!}$.

2.  We have $\operatorname*{\mathbb{E}}\limits_{A\sim N({\mathbb{C}}^{n\times n})} \lvert \det(A)\rvert^2 = n! = \Gamma(n-1).$

3.  For $t\in {\mathbb{C}}$ we have $\operatorname*{\mathbb{E}}\limits_{A\sim N({\mathbb{C}}^{n\times n})} \lvert \det (A+tI_{n})\rvert^2 =  e^{\lvert t\rvert^2} \Gamma\left(n+1,\lvert t\rvert^2\right).$

Norms of multilinear operators {#A3}
==============================

For $k,l\in{\mathbb{N}}$ let ${\mathcal{L}}_k({\mathbb{C}}^l,{\mathbb{C}}^n)$ denote the vector space of multilinear maps $({\mathbb{C}}^l)^k\to {\mathbb{C}}^n$. The *spectral norm* of $A\in{\mathcal{L}}_k({\mathbb{C}}^l,{\mathbb{C}}^n)$ is defined as $$\label{spectral_norm}
    {\left\lVert A \right\rVert}:=\sup\limits_{v_1,\ldots,v_k\in{\mathbb{S}}({\mathbb{C}}^l)} {\left\lVert A(v_1,\ldots,v_k) \right\rVert}.$$ If $A\in{\mathcal{L}}_1({\mathbb{C}}^l,{\mathbb{C}}^n)$ is linear we denote by ${\left\lVert A \right\rVert}_F$ its Frobenius norm. It is well known that for all $A\in{\mathcal{L}}_1({\mathbb{C}}^l,{\mathbb{C}}^n)$ one has ${\left\lVert A \right\rVert}\leq{\left\lVert A \right\rVert}_F$. The spectral norm is *submultiplicative*; that is, for $A\in {\mathcal{L}}_k({\mathbb{C}}^l,{\mathbb{C}}^n), B\in{\mathcal{L}}_1({\mathbb{C}}^n,{\mathbb{C}}^{n'})$ we have ${\left\lVert BA \right\rVert}\leq {\left\lVert B \right\rVert}{\left\lVert A \right\rVert}$. Norms of projections play an important role in this work.

\[projection\_lemma\]

1.  Let $u,v\in{\mathbb{C}}^n\backslash{\left\{0\right\}}$ and $P:u^\perp\to v^\perp$ be the orthogonal projection from $u^\perp$ to $v^\perp$. We have ${\left\lVert P \right\rVert}\leq 1$. If $d_{\mathbb{S}}(u,v)<\pi/2$, then $P$ is invertible and ${\left\lVert P^{-1} \right\rVert}= [\cos  d_{\mathbb{S}}(u,v)]^{-1}$.

2.  Let $A\in{\mathcal{L}}_1({\mathbb{C}}^{n+1},{\mathbb{C}}^n)$ and $u,v\in{\mathbb{C}}^{n+1}\backslash{\left\{0\right\}}$, such that $\ker A ={\mathbb{C}}v$. Then ${\ensuremath{\left.A\right|_{v^\perp}}}^{-1}{\ensuremath{\left.A\right|_{u^\perp}}}: u^\perp\to v^\perp$ is the orthogonal projection $u^\perp\to v^\perp$.

3.  Let $A\in{\mathcal{L}}_1({\mathbb{C}}^{n+1},{\mathbb{C}}^n)$ and $u,v\in{\mathbb{C}}^{n+1}\backslash{\left\{0\right\}}$, such that $\ker A ={\mathbb{C}}v$. Then ${\left\lVert {\ensuremath{\left.A\right|_{v^\perp}}}^{-1} \right\rVert}\leq {\left\lVert {\ensuremath{\left.A\right|_{u^\perp}}}^ {-1} \right\rVert}$.

For (1) see [@condition Lemma 16.40]. For (2) let $x\in u^\perp$ and $y\in v^\perp$, such that ${\ensuremath{\left.A\right|_{v^\perp}}}^{-1}{\ensuremath{\left.A\right|_{u^\perp}}}x=y$. Then $Ax=Ay$, which implies that $x-y\in\ker A = {\mathbb{C}}v$.

To prove (3), write ${\ensuremath{\left.A\right|_{v^\perp}}}^{-1} = {\ensuremath{\left.A\right|_{v^\perp}}}^{-1}{\ensuremath{\left.A\right|_{u^\perp}}}{\ensuremath{\left.A\right|_{u^\perp}}}^ {-1}.$ Using the submultiplicativity of the spectral norm we obtain $${\left\lVert {\ensuremath{\left.A\right|_{v^\perp}}}^{-1} \right\rVert}\leq {\left\lVert  {\ensuremath{\left.A\right|_{v^\perp}}}^{-1}{\ensuremath{\left.A\right|_{u^\perp}}} \right\rVert}{\left\lVert {\ensuremath{\left.A\right|_{u^\perp}}}^ {-1} \right\rVert}.$$ From (1) and (2) we get that ${\left\lVert  {\ensuremath{\left.A\right|_{v^\perp}}}^{-1}{\ensuremath{\left.A\right|_{u^\perp}}} \right\rVert}\leq 1$, which shows the assertion.

Some Trigonometry
=================

\[real\_geometry\_prop\] Let $m=m_1+m_2$, and $x:=(x_1,x_2)\in({\mathbb{R}}^{m_1}\backslash{\left\{0\right\}})\times{\mathbb{R}}^{m_2}$, such that ${\left\lVert x_2 \right\rVert} \leq {\left\lVert x_1 \right\rVert}$. Let $y:=(y_1,y_2)\in ({\mathbb{R}}^{m_1}\times{\mathbb{R}}^{m_2})\backslash{\left\{0\right\}}$ and put $\delta:=d_{\mathbb{S}}(x,y)$

1.  If $\delta < \pi/4$, then $y_1\neq 0$.

2.  Suppose that $\delta < \pi/16$ and $x_1,y_1\in{\mathbb{S}}({\mathbb{R}}^{m_1})$. Then ${\left\lVert x-y \right\rVert}\leq  \delta\sqrt{8}.$

Let us first prove the first part. Without restriction we may assume that ${\left\lVert x \right\rVert}={\left\lVert y \right\rVert}=1$. Consider the map $$\begin{aligned}
    \Psi: {\mathbb{S}}({\mathbb{R}}^{m_1})\times {\mathbb{S}}({\mathbb{R}}^{m_2}) \times [0,\pi/2]&\to {\mathbb{S}}({\mathbb{R}}^{m_1+m_2}),      (u,v,\phi)\mapsto \left(\cos(\phi)u,\sin(\phi)v\right)
    \end{aligned}$$ One easily shows that $\Psi$ is surjective. Suppose that $\Psi(u_x,v_x,\phi_x)=x$ and $\Psi(u_y,v_y,\phi_y)=y$. We have $$\begin{aligned}
\cos(\delta) &= \cos(\phi_x)\cos(\phi_y)\langle u_x,u_y\rangle + \sin(\phi_x)\sin(\phi_y)\langle v_x,v_y\rangle \\
    &\leq \cos(\phi_x)\cos(\phi_y)
     + \sin(\phi_x)\sin(\phi_y) = \cos(\phi_x-\phi_y)
    \end{aligned}$$ and hence $\delta\geq {\left\lvert \phi_x-\phi_y \right\rvert}$. From our assumption ${\left\lVert x_2 \right\rVert}\leq {\left\lVert x_1 \right\rVert}$ it follows that $0\leq \phi_x\leq \pi/4$, which implies $0\leq \phi_y \leq \delta+\phi_x< \pi/2$. This implies ${\left\lVert y_1 \right\rVert}=\cos(\phi_y)\neq 0$. The first assertion follows from this.

We now prove the second assertion. Let $\Psi(u_x,v_x,\phi_x)=x/{\left\lVert x \right\rVert}$ and let $\Psi(u_y,v_y,\phi_y)=y/{\left\lVert y \right\rVert}$. By assumption we have $\cos(\phi_x)\neq 0$ and by the first part we have $\cos(\phi_y)\neq 0$. Since ${\left\lVert x_1 \right\rVert}={\left\lVert x_2 \right\rVert}=1$, we have that ${\left\lVert x \right\rVert}^2  = 1 + \tan^2(\phi_x),$ and ${\left\lVert y \right\rVert}^2  = 1 + \tan^2(\phi_y)$. The law of cosines yields ${\left\lVert x-y \right\rVert}^2 = {\left\lVert x \right\rVert}^2 + {\left\lVert y \right\rVert}^2 - 2{\left\lVert x \right\rVert}{\left\lVert y \right\rVert} \cos(\delta)$. From this we obtain $${\left\lVert x-y \right\rVert}^2 = 2  + \tan^2\phi_x + \tan^2\phi_y -2 \sqrt{(1+\tan^2\phi_x)(1+\tan^2\phi_y)} \cos(\delta).$$ Writing $\phi_y = \phi_x+\delta$ we obtain ${\left\lVert x-y \right\rVert}^2$ as a function of $\phi_x$ and $\delta$, which we denote by $$\ell:[0,\frac{\pi}{4}]\times [-\frac{\pi}{16},\frac{\pi}{16}] \to {\mathbb{R}}_{\geq 0},\: (\phi_x,\delta)\mapsto {\left\lVert x-y \right\rVert}^2.$$ A computer based calculation reveals that $\partial \ell/(\partial \phi_x) >0$. This implies $${\left\lVert x-y \right\rVert}^2 \leq \ell(\pi/4,\delta) = 3 + \tan(\pi/4+\delta)^2 -2 \sqrt{2(1+\tan(\pi/4+\delta)^2)} \cos(\delta).$$ Another computer based calculation shows $\ell(\pi/4,0)=0$ and that $0$ is a global minimum of $8\delta^2 - \ell(\pi/4,\delta)$.

Differential geometry {#A4}
=====================

Suppose that $M,N$ are Riemannian manifolds of dimensions $m,n$, respectively. Let $\phi: M\to N$ be a surjective smooth map. We denote by $\mathrm{NJ}(\phi)(p)$ the normal jacobian of $\phi$ at $p$; see [@condition sec. 17.3].

\[coarea\_formula\] For any function $\chi: M\to {\mathbb{R}}$, that is integrable with respect to the volume measure of $M$, we have that $$\int_M \chi {\mathrm{d}}M = \int_{y\in N} \left[ \int_{\phi^{-1}(y)} \frac{\chi}{\mathrm{NJ}(\phi)} {\mathrm{d}}\phi^{-1}(y)\right] {\mathrm{d}}N.$$

Let $E_1,E_2$ be finite dimensional complex vector spaces with hermitian inner product, such that $\dim_{\mathbb{C}}E_1 \geq \dim_{\mathbb{C}}E_2$ and $\phi:E_1 \to E_2$ be linear and surjective. Let $\Gamma(\phi):={\left\{(x,\phi(x))\in E_1\times E_2\right\}}$. Then $\Gamma(\phi)$ is a linear space and the projections $p_1: \Gamma(\phi)\to E_1$ and $p_2: \Gamma(\phi)\to E_2$ are linear maps.

The following result is Lemma 3 in [@BSS sec. 13.2], combined with the comment in Theorem 5 in [@BSS sec. 13.2].

\[NJ\_smale\_lemma\] Let $W$ be the orthogonal complement of $\ker p_2$. Then $\lvert \det (p_1)\rvert /\lvert \det (p_2|_W)\rvert= \lvert\det(\phi\phi^*)\rvert^{-1}.$

[^1]: Institute of Mathematics, Technische Universität Berlin, breiding@math.tu-berlin.de. Partially supported by DFG research grant BU 1371/2-2.
