---
abstract: 'The ensemble Kalman inversion (EKI) is a particle based method which has been introduced as the application of the ensemble Kalman filter to inverse problems. In practice it has been widely used as derivative-free optimization method in order to estimate unknown parameters from noisy measurement data. For linear forward models the EKI can be viewed as gradient flow preconditioned by a certain sample covariance matrix. Through the preconditioning the resulting scheme remains in a finite dimensional subspace of the original high-dimensional (or even infinite dimensional) parameter space and can be viewed as optimizer restricted to this subspace. For general nonlinear forward models the resulting EKI flow can only be viewed as gradient flow in approximation. In this paper we discuss the effect of applying a sample covariance as preconditioning matrix and quantify the gradient flow structure of the EKI by controlling the approximation error through the spread in the particle system. The ensemble collapse on the one side leads to an accurate gradient approximation, but on the other side to degeneration in the preconditioning sample covariance matrix. In order to ensure convergence as optimization method we derive lower as well as upper bounds on the ensemble collapse. Furthermore, we introduce covariance inflation without breaking the subspace property intending to reduce the collapse rate of the ensemble such that the convergence rate improves. In a numerical experiment we apply EKI to a nonlinear elliptic boundary-value problem and illustrate the dependence of EKI as derivative-free optimizer on the choice of the initial ensemble.'
author:
- 'Simon Weissmann[^1]'
bibliography:
- 'references.bib'
title: Gradient flow structure and convergence analysis of the ensemble Kalman inversion for nonlinear forward models
---

<span> Ensemble Kalman inversion, Tikhonov regularization, derivative-free optimization, subspace property, covariance inflation\
<span>**AMS(MOS) subject classifications.**</span> 37C10, 65N21, 65N75, 93D05 </span>

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

In inverse problems we are concerned with the task of recovering some unknown quantity of interest, which can not be observed directly. Its research area has a wide range of applications in science and engineering, including among others medical imaging and geophysics. Since inverse problems are typically ill-posed, much research focuses on theoretical and practical analysis of regularization methods. Regularization techniques help to overcome instability issues arising for example through noise in the data. Beside deterministic regularization methods, the Bayesian approach formulates inverse problems in a statistical framework. By formulating a probabilistic approach, it incorporates uncertainty of the underlying model. The regularization can then be viewed as incorporating prior information through a probability distribution on the unknown parameter. The solution of the Bayesian inverse problem is given by the posterior distribution - the distribution of the unknown parameter conditioned on the realization of the observation. The resulting posterior distribution is often not accesible directly, such that sampling or suitable integration methods are needed.

In this document, we focus on a particle based method which is commenly used for data assimilation problems - the ensemble Kalman filter (EnKF). The EnKF has been introduced by Evensen @GE03 [@GE09] and more recently, formulated for solving inverse problems @ILS13. The application of the EnKF to inverse problem has been established as widely used tool and is known as ensemble Kalman inversion (EKI). The aim of this manuscript is to analyse EKI as derivative-free optimization method for general nonlinear forward models. Our analysis will be based on the continuous-time formulation of the scheme, which can be viewed as (stochastic) ordinary differential equation ((S)ODE) in time, with focus on the deterministic setting, i.e. without perturbed observations. We will quantify the approximation of derivatives through the ensemble spread and derive sufficient lower and upper bounds on the collapse in order to verify convergence of the scheme.

Literature review
-----------------

The EnKF has been introduced by Evensen @GE03 as particle based approximation of the filtering distribution arising in data assimilation problems. The method has beend applied in the context of Bayesian inverse problems @chen2012ensemble [@emerick2013ensemble]. An important focus lies in the analysis of the large ensemble size limit, which has been studied for linear and Gaussian models @L2009LargeSA [@doi:10.1137/140965363] as well as in a nonlinear setting @doi:10.1137/140984415 and for the ensemble square root filter @LS2021_c. Viewing the particle system as Monte Carlo method had led to much focus on the formulation of multilevel variants @doi:10.1137/15M100955X [@2016arXiv160808558C; @HST2020; @chada2021multilevel]. Moreover, ensemble Kalman methods have been studied in the long time behavior @0951-7715-27-10-2579 [@47c5c78ebb8c44ef9d8d5e0d23e23c13; @0951-7715-29-2-657]. The accuracy for a fixed ensemble size has been studied in @Tong2018 [@doi:10.1002/cpa.21722] for the EnKF and in @delmoral2018 [@doi:10.1137/17M1119056] for the ensemble Kalman-Bucy filter. Furthermore, a high focus of research for ensemble Kalman methods lies in the continuous-time formulation @bergemann2010localization [@bergemann2010mollified; @Reich2011; @LS2021; @LS2021_b; @lange2021derivation].

In @ILS13 the authors propose the application of the EnKF to inverse problems. In the literature EKI has been analysed as sequential Monte Carlo type methods as well as derivative-free optimization method. In the setting of linear forward maps and Gaussian prior assumptions it is well-known that EKI approximates the posterior distribution in its mean field limit. However, in @ErnstEtAl2015 it has been demonstrated that in general nonlinear settings the resulting estimator is not consistent with respect to the posterior distribution. In the mean field limit EKI has been analysed based on the Fokker–Planck equation @DL2021_b [@MHGV2018]. The continuous-time limit of EKI has been formally derived in @SS17 and theoretically analysed in @BSW18 [@BSWW2021]. In the continuous-time formulation EKI can be viewed as derivative-free optimization method @SS17 and has shown promising results for the training task in different machine learning applications @KS18 [@GSW2020]. Building up on the continuous-time formulation there has been much analysis on deterministic EKI, which ignores the diffusion of the underlying SDE, and stochastic EKI including the perturbed observations. For linear models well-posedness and convergence results have been derived for the deterministic formulation @SS17 and the stochastic formulation @BSWW19. The nonlinear setting has been analysed in @Chada2019ConvergenceAO where the authors consider the discrete time setting with a nonconstant step size scheme. The authors include variance inflation breaking the subspace property in order to verify convergence of the method. Moreover, EKI has been studied for nonlinear models in the mean field limit @DLL2020, where weights have been incorporated in order to correct the resulting posterior estimate. In our presented analysis it turns out that the gradient flow structure highly depends on the behavior of the sample covariance which is used as preconditioner. The dynamical behavior of EKI and its sample covariance has been described and analysed by a spectral decomposition @bungert2021. Furthermore, in @tong2022localization a localization of the sample covariance has been introduced and analysed based on the deterministic continuous-time formulation for nonlinear forward models. Since EKI is applied as solver for inverse problems, one has to handle noise in the data. In this context, an early stopping criterion has been proposed in @SS17b and discrete regularization has been analysed in @Iglesias2015 [@2016InvPr..32b5002I]. The focus in this document is on the Tikhonov regularized modification of EKI (TEKI) which has been introduced in @CST19 and further analysed in @weissmann2021adaptive. Further, adaptive regularization methods within EKI have been studied in @parzer2021convergence [@iglesias2020adaptive].

From an alternative point of view, EKI has been modified to a particle based sampling method @AGFHWLAS2019 [@GNR2020; @DL2021; @RW2021]. Shifting the noise in the observations to the parameter space itself the resulting SDE can be treated as Langevin dynamic, where the ergodicity can be used to build a sampling method.

Main contributions
------------------

In this article we are going to quantify EKI as derivative-free optimization method in the context of general nonlinear forward maps. We employ a gradient flow structure and present a convergence analysis based on Lyapunov functions. With this document, we extend the convergence analysis for TEKI presented in @CST19 where the convergence result was based on linear forward models. We make the following contributions:

-   We present the well-posedness of the TEKI flow by proving unique existence of solutions for . Furthermore, we view the TEKI flow as appoximate gradient flow by decomposing the flow into the preconditioned gradient direction and the approximation error resulting through Taylor expansion.

-   We quantify the approximation error through the spread in the particle system. While the ensemble collapses in time with rate $1/t$, we will see that the approximation error degenerates with rate $(1/t)^{3/2}$. In contrast, we prove that the sample covariance remains strictly-positive definite as operator acting on the subspace spanned by the initial ensemble spread <span>$\mathcal B = u_0^\perp + \operatorname{span}\{u_0^{(j)}-\bar u_0\mid j=1,\dots,J\}$ for a specific $u_0^\perp\in\mathcal X$</span>.

-   We describe the effect of preconditioning through the sample covariance. Therefore, we view the minimization task of $\Phi_R$ over the subspace <span>$\mathcal B$</span> as equality constrained optimization method and derive a Polyak-Łojasiewicz (PL)-type inequality restricted to the subspace <span>$\mathcal B$</span>. Under strong convexity and smoothness of $\Phi_R$ we are then able to prove convergence with rate $(1/t)^{\frac1\alpha}$, $\alpha\ge1$.

-   We incorporate covariance inflation without breaking the subspace property. The inflation sufficiently slows down the ensemble collapse such that the convergence rate $\alpha$ can be improved to $(1-\rho)\alpha$, where $\rho\in[0,1)$ is the inflation factor. Furthermore, we view our proposed covariance inflation scheme as generalization of the ensemble square root filter (ESRF) applied to inverse problems.

#### Outline

The remainder of this manuscript is structured as follows. In Section \[sec:mathsetup\] we provide the mathematical background for (T)EKI, and we formulate our main convergence result with the corresponding assumptions in Section \[sec:main\]. We provide a row of auxilary properties of the TEKI flow in Section \[sec:prelim\] which are then applied to present the proof of our main Theorem \[thm:main\] in Section \[sec:proof\_main\]. The incorporation of the covariance inflation and the improved convergence analysis are presented in Section \[sec:ESRF\]. In Section \[sec:numerics\] we illustrate the presented convergence results in a one-dimensional elliptic boundary-value problem. The document will be closed with a summary and outlook for open research directions in Section \[sec:conclusion\].

Mathematical setup {#sec:mathsetup}
==================

In the following we will introduce the mathematical background. We consider the inverse problem of recovering $u\in\mathcal X$ given noisy observations $$\label{eq:IP}
y = G(u) + \eta,$$ where $G:\mathcal X\to\mathbb R^K$ is the possibly nonlinear forward map and $\eta$ denotes additive Gaussian noise, i.e. $\eta\sim\mathcal N(0,\Gamma)$ for some symmetric positive definite noise covariance matrix $\Gamma\in\mathbb R^{K\times K}$. Due to ill-posedness of inverse problems, we typically consider the task of minimization of a regularized loss functionals of the form

$$\min_{x\in\mathcal X}\ \mathcal L_{\mathbb R^K}(G(x),y) + \mathcal R_{\mathcal X}(x),$$

where we describe the discrepancy to the data through $\mathcal L_{\mathbb R^K}:\mathbb R^K\times\mathbb R^K \to \mathbb R_+$ and incorporate prior information through the regularization function $\mathcal R_\mathcal X:\mathcal X\to\mathbb R_+$. We refer to @EHN1996 [@benning_burger_2018] for an overview of various types of regularization methods. Classical choices of regularization include Tikhonov regularization @EKN1989 and total variation regularization @Chambolle2009AnIT [@ROF1992]. Throughout this document, our focus will be on the finite dimensional case $\mathcal X=\mathbb R^{n_x}$ and the Tikhonov regularized lossfuntion of the form $$\label{eq:regularized_lossfunction}
\Phi_R(x) = \Phi(x;y) + R(x), \quad R(x) = \frac12\|x\|_{C_0}^2,$$ where we define the least-square data misfit by $$\label{eq:datamisfit}
\Phi(x;y) = \frac12 \|G(x)-y\|_\Gamma^2$$ and $R$ denotes the regularization function with symmetric positive definite regularization matrix $C_0\in{\mathbb{R}}^{n_x\times n_x}$. Here, we have introduced the notation $\|\cdot\|_{\Gamma}:=\|\Gamma^{-1/2}\cdot\|$, $\|\cdot\|_{C_0}=\|C_0^{-1/2}\cdot\|$, where $\|\cdot\|$ denotes the euclidean norm in ${\mathbb{R}}^K$ and ${\mathbb{R}}^{n_x}$ respectively. Moreover, we will make use of $\|\cdot\|_{\mathrm{HS}}$ as notation for the Hilbert-Schmidt operator norm.

The Tikhonov regularization is closely connected to the Bayesian approach for inverse problems @AMS10 which incorporates regularization from a statistical point of view. In a probabilistic model we let $u$ be an $\mathcal X$-valued random variable with prior distribution $\mu_0$ stochastically independent of the noise $\eta$. When viewing $(u,y)$ as a jointly distributed random variable on ${\mathbb{R}}^K\times\mathcal X$, the solution of the Bayesian inverse problem is given by the posterior distribution of $u\mid y$ $$\label{eq:posterior}
\mu(\mathrm{d}x) = \frac1Z\exp(-\Phi(x;y))\mu_0({\mathrm{d}}x),$$ with normalization constant $$Z:= \int_{{\mathbb{R}}^{n_x}}\exp(-\Phi(x;y))\mu_0({\mathrm{d}}x).$$ We note for a Gaussian prior assumption $\mu_0 = {\mathcal{N}}(0, C_0)$ the maximum a-posteriori estimate computes as $$\min_{x\in\mathcal X}\ \Phi(x;y) + \frac12\|x\|_{C_0}^2,$$ which relates the Bayesian approach for inverse problems to the Tikhonov regularization through . Throughout this manuscript we assume that $y\in{\mathbb{R}}^{n_y}$ is fixed and suppress the dependence of $\Phi$ on $y$ by writing $\Phi(x) = \Phi(x;y)$.

The ensemble Kalman filter applied to inverse problems
------------------------------------------------------

The EKI has been introduced as the application of the EnKF to inverse problems @ILS13. We will follow the derivation of EKI as sequential Monte Carlo method aiming to approximate the posterior distribution. Therefore, we introduce the tempered distribution $$\label{eq:tempering}
\mu_{n+1}({\mathrm{d}}u) = \frac1{Z_n} \exp(-h\Phi(u;y))\mu_n({\mathrm{d}}u),$$ with $h=1/N$ and normalizing constants $Z_n$, where $\mu_0$ is the prior distribution and $\mu_N$ corresponds to the posterior distribution. Given a sample from the prior distribution, the EKI evolves the sample as particle system through Gaussian approximation steps. Let $(u_0^{(j)})_{j\in\{1,\dots,J\}}$ be the initial ensemble of size $J\ge 2$ and consider the empirical approximation of the tempering distribution defined in $$\mu_n(\mathrm{d}u)\approx \frac1J\sum_{j=1}^J\delta_{u_n^{(j)}}(\mathrm{d}u).$$ Defining the following empirical means and covariances $$\begin{aligned}
\bar u = \frac1J\sum_{j=1}^J u^{(j)},\quad &C(u)=\frac1J\sum_{j=1}^J(u^{(j)}-\bar u)\otimes (u^{(j)}-\bar u),\\
\bar G = \frac1J\sum_{j=1}^J G(u^{(j)}),\quad &C^{G,G}(u)=\frac1J\sum_{j=1}^J(G(u^{(j)})-\bar G)\otimes (G(u^{(j)})-\bar G),\\
C^{u,G}(u) &= \frac1J\sum_{j=1}^J(u^{(j)}-\bar u)\otimes (G(u^{(j)})-\bar G), \\ C^{G,u}(u) &= \frac1J\sum_{j=1}^J(G(u^{(j)})-\bar G)\otimes (u^{(j)}-\bar u),\end{aligned}$$ the ensemble Kalman iteration for the current particle system $(u_n^{(j)})_{j\in\{1,\dots,J\}}$ is given by $$\label{eq:discreteEKI}
u_{n+1}^{(j)} = u_n^{(j)} + C^{u,G}(u_n)(C^{G,G}(u_n) + h^{-1}\Gamma)^{-1} (y_{n+1}^{(j)} - G(u_n^{(j)})),\quad j=,1\dots,J,$$ where $h>0$ is a artificial step size and $y_{n+1}^{(j)}$ are perturbed observations $$y_{n+1}^{(j)} = y + \xi_{n+1}^{(j)},\quad \xi_{n+1}^{(j)} \sim \mathcal N(0,h^{-1}\Gamma)$$ with $\xi_{n+1}^{(j)}$ being i.i.d. with respect to both $j$ and $n$. Considering the limit $h\to0$ the discrete EKI can be viewed as time discretization of the system of coupled SDEs $$\label{eq:cont_stochasticEKI}
{\mathrm d}u_t^{(j)} = C^{u,G}(u_t)\Gamma^{-1}(y-G(u_t^{(j)}))\, {\mathrm d}t + C^{u,G}(u_t)\Gamma^{-1/2}\,{\mathrm d}W_t^{(j)},$$ where $W^{(j)}$ are independent Brownian motions on $\mathbb R^K$. The continuous-time limit has been formulated in @SS17 and theoretical verified in @BSW18 [@BSWW2021].

Since the EKI is not consistent with the posterior distribution for general nonlinear forward maps @ErnstEtAl2015, we will focus on EKI as derivative-free optimization method. Instead of considering perturbed observations, sometimes also referred to as stochastic EKI, the EKI is often analysed in its deterministic formulation represented by a system of coupled ODEs $$\label{eq:cont_deterministicEKI}
\frac{{\mathrm d}u_t^{(j)}}{{\mathrm d}t} = C^{u,G}(u_t)\Gamma^{-1}(y-G(u_t^{(j)})),$$ which describes the drift term of the SDE formulation @SS17 [@SS17b]. Considering a linear forward map $G(\cdot) = A\cdot$ with $A\in\mathcal L(\mathcal X,\mathbb R^K)$ the deterministic EKI can be viewed as preconditioned gradient flow written through $$\label{eq:cont_deterministicEKI2}
\frac{{\mathrm d}u_t^{(j)}}{{\mathrm d}t} = -C(u_t)\nabla\Phi(u_t^{(j)}).$$ For general nonlinear forward maps the representation as preconditioned gradient flow holds only approximatively. In particular, using Taylor approximations we can justify that $$C^{u,G}(u) \approx C(u){\mathrm D}G^\ast(u),$$ where ${\mathrm D}G$ denotes the (Fréchet) derivative of $G$, and we are going to quantify the error between the nonlinear EKI and a preconditioned gradient flow. Since our aim is to view the EKI as optimization method for minimizing the data misfit functional $\Phi$, the resulting scheme is ill-posed due to the ill-posed inverse and it is natural to consider a regularized modification of the EKI. Therefore, the authors in @CST19 proposed to incorporate Tikhonov regularization within EKI resulting in the deterministic continuous-time formulation as coupled system of ODEs $$\label{eq:cont_deterministicTEKI}
\frac{{\mathrm d}u_t^{(j)}}{{\mathrm d}t} = C^{u,G}(u_t)\Gamma^{-1}(y-G(u_t^{(j)}))-C(u_t)C_0^{-1}u_t^{(j)},$$ which can then be viewed as derivative-free approximation to the preconditioned gradient flow $$\label{eq:cont_deterministicTEKI2}
\frac{{\mathrm d}u_t^{(j)}}{{\mathrm d}t} = -C(u_t)\nabla\Phi_R(u_t^{(j)}).$$ We will see that this approximation is getting more accurate for a decreasing spread of the particle system. To do so, we are going to analyse the long-time behaviour of for a fixed number of particles. Therefore, we will extend the convergence analysis presented in @CST19 from the linear to the nonlinear setting. Here, it has been shown that assuming a linear forward model $G(\cdot) = A\cdot, $ $A\in\mathcal L(\mathcal X,\mathbb R^K)$ the resulting solution of the TEKI flow minimizes the objective funtion $\Phi_R$ in the subspace spanned by initial ensemble <span>spread $\mathcal B=u_0^\perp + \operatorname{span}\{u_0^{(j)}-\bar u_0\mid j=1,\dots,J\}$ for a specific $u_0^\perp\in\mathcal X$</span>.

Main result: Convergence of TEKI for nonlinear forward models {#sec:main}
=============================================================

In order to quantify the nonlinear EKI as derivative-free approximation we make the following assumptions.

\[ass:smoothness\] We assume that the objective function $\Phi_R$ is $C^2({\mathcal{X}};{\mathbb{R}}_+)$ and $\mu$-strongly convex, i.e.  $$\Phi_R(x_1)-\Phi_R(x_2)\ge \langle \nabla\Phi_R(x_2),x_1-x_2\rangle + \frac{\mu}2\|x_1-x_2\|^2$$ for some $\mu>0$ and all $x_1,x_2\in\mathcal X$. Moreover, we assume that $\Phi_R$ is $L$-smooth, i.e. $$\Phi_R(x_1)-\Phi_R(x_2)\le \langle \nabla\Phi_R(x_2),x_1-x_2\rangle + \frac{L}2\|x_1-x_2\|^2$$ for some $L>0$ and all $x_1,x_2\in\mathcal X$ and therefore satisfies the PL-inequality $$\nu\|\nabla\Phi(x)\|^2\ge \Phi_R(x) - \Phi(x_\ast), \quad x\in\mathcal X$$ for some $\nu>0$, where $x_\ast$ is a stationary point, i.e. $\nabla\Phi(x_\ast)=0$.

\[ass:Taylor\] We assume that the forward map $G$ is $C^2({\mathcal{X}};{\mathbb{R}}^{n_y})$, locally Lipschitz with constant $c_{\mathrm{lip}}>0$ and can be approximated linearly by $$\label{eq:linearization}
G(x_1) = G(x_2) + {\mathrm D}G(x_2)(x_1-x_2) + {\mathrm{Res}}(x_1,x_2),$$ where the approximation error ${\mathrm{Res}}$ is bounded by $$\label{eq:Taylor_residual}
\|{\mathrm{Res}}(x_1,x_2)\|_{{\mathbb{R}}^{n_y}} \le b_{\mathrm{res}} \|x_1-x_2\|_{{\mathcal{X}}}^2$$ for some $b_{\mathrm{res}}>0$ independent from $x_1,x_2\in\mathcal X$.

We note that Assumption \[ass:Taylor\] is satisfied for linear forward maps $G(\cdot) = A\cdot$, $A\in\mathcal L(\mathcal X,\mathbb R^K)$ with ${\mathrm{Res}}(x_1,x_2) = 0$ for all $x_1,x_2\in\mathcal X$. Furthermore, it is sufficient to assume that the Hessian of $G$ is uniformly bounded in the sense that $\langle z, {\mathrm D}^2 G(x)z\rangle \le c \|z\|^2$ for all $z\in{\mathcal{X}}$. Alternatively, the tangential cone condition $$\|G(x_1)-G(x_2)-{\mathrm D}G(x_2)(x_1-x_2)\|\le \tilde b\|x_1-x_2\| \|G(x_1)-G(x_2)\|$$ for some uniform $\tilde b>0$ together with Lipschitz continuity implies Assumption \[ass:Taylor\]. This condition is often assumed (locally) when studying iterative methods for nonlinear inverse problems @S1995. Furthermore, we note that the above assumption can be weaken through the assumption $\|{\mathrm{Res}}(x_1,x_2)\| \le b_{\mathrm{res}} \|x_1-x_2\|^p$, for $p> 2$. However, to avoid technical details we will keep the assumption with $p=2$ for the main proof and state more details on the extension to $p>2$ in Remark \[rem:higher\_apprx\] after the proof of our main result.

\[prop:gradientflow\_structure\] Suppose Assumption \[ass:Taylor\] is satisfied, then it holds true that $$\begin{aligned}
\frac{{\mathrm d}\frac1J\sum_{j=1}^J\left(\Phi_R(u_t^{(j)})\right)}{{\mathrm d}t} &\le -\frac1J\sum_{j=1}^J \langle \nabla \Phi_R(u_t^{(j)}), C(u_t)\nabla \Phi_R(u_t^{(j)})\rangle\\ &\quad+   b_1 J V_e(t)^{3/2}\frac{1}{J}\sum_{j=1}^J\left(\frac{1}{2}\|\nabla\Phi_R(u_t^{(j)})\|^2+ \Phi_R(u_t^{(j)}) \right),\end{aligned}$$ where $b_1>0$ is independent from $J$ and $V_e(t) :=\frac{1}{J}\sum_{k=1}^J \|u_t^{(k)}-\bar u_t\|^2$.

The above result quantifies the (approximate) gradient flow structure of TEKI. We will see, that $V_e(t)$ is of the order $1/t$, which means that the approximation error of the gradient through the covariance degenerates in time. However, the degeneration of $C(u_t)$ influences the preconditioning effect for the gradient as well. Although we can show, that the degeneration of $C(u_t)$ is bounded from below by the order $1/t$, it is not possible to imply lower bounds on the eigenvalues $C(u_t)$. This issue comes from the fact that $C(u_t)$ is a sample covariance and has at most rank $\min(n_x,J-1)$. To alleviate this problem, we will show that $C(u_t)$ will remain positive definite in the subspace spanned through the initial ensemble <span>spread</span>. <span>Following Lemma 3.7 and Corollary 3.8 in @CST19 along the solution of the TEKI flow the particle system $(u_t^{(j)})_{j=1,\dots,J}$ remains in the subspace $${\mathcal{B}}:= u_0^\perp + \operatorname{span}\{u_0^{(j)} - \bar u_0 \mid j=1,\dots,J\} \subset \operatorname{span}\{u_0^{j}\mid j=1,\dots,J\}=:\mathcal S,$$ where $u_0^\perp = \bar u_0 - \mathcal P_E \bar u_0$, where $\mathcal P_E:= E(E^\top E)^{-1}E^T$ with $E=((u_0^{(1)}-\bar u_0)^\top,\dots,(u_0^{(J)}-\bar u_0)^\top)\in\mathbb R^{n_x\times J}$ is the orthogonal projection on the subspace $\operatorname{span}\{u_0^{(j)} - \bar u_0 \mid j=1,\dots,J\}$.</span>

Hence, our aim is to quantify TEKI as gradient flow w.r.t. the constrained optimization problem

$$\label{eq:constr_opti}
\min_{x\in {\mathcal B}}\ \Phi_R(x),$$

where $(u_0^{(j)})_{j=1,\dots,J}$ is the initial ensemble for TEKI. In fact, a similar result has been shown in @CST19 for the linear setting, where the gradient approximation is exact. We are going to extend the theory to nonlinear forward maps satisfying Assumptions \[ass:smoothness\] and \[ass:Taylor\]. Note that we will reformulate the optimization probelm as equality constrained optimization problem, implying that there exists a unique minimizer $u_\ast\in\mathcal B$ of . In the following we formulate our main convergence result.

\[thm:main\] Suppose Assumption \[ass:smoothness\] and Assumption \[ass:Taylor\] are satisfied, let $(u_t^{(j)},t\ge0)_{j=1,\dots,J}$ solve with linearly independent initial ensemble $(u_0^{(j)})_{j=1,\dots,J}$ and let $u_\ast\in\mathcal B$ be the unique global minimizer of . Then there exist $c_1,c_2>0$ such that $$\label{eq:main_result}
\frac{1}{J}\sum_{j=1}^J\Phi_R(u_t^{(j)})-\Phi_R(u_\ast) \le \left(\frac{c_1}{t+c_2}\right)^{\frac1\alpha},$$ where $0<\alpha < \frac{L}{\mu}(\sigma_{\max}+c_{\mathrm{lip}}\lambda_{\max}\|C(u_0)\|_{\mathrm{HS}})$.

Preliminaries {#sec:prelim}
=============

In the following we present a row of auxilary results, which are needed to prove the main convergence result in Theorem \[thm:main\].

Existence of solutions and ensemble collapse
--------------------------------------------

Recall that we assume a finite dimensional parameter space $\mathcal X = \mathbb R^{n_x}$. We start this section with verifying the well-posedness of the scheme. Therefore, we state that there exists a unique solution for the considered TEKI flow.

Let $(u_0^{(j)})_{j=1,\dots,J}$ be the linearly independent initial ensemble and define its linear span $S = \operatorname{span}\{u_0^{(j)}\mid j=1,\dots,J\}$. Then for all $T>0$ the equation has a unique solution $(u_t^{(j)}, t\in[0,T])\in C([0,T],\mathcal S)$. In particular, it holds true that $\langle z, u_t^{(j)}\rangle = 0$ for all $z\in S^\perp$ and all $t\in[0,T]$, $j=1,\dots,J$.

Due to local Lipschitz continuity local solutions follow from standard ODE theory, see e.g. @CST19 [Theorem 3.2] for details. Moreover, we refer to @CST19 [Corollary 3.8] for the subspace property, i.e. while a solution exists it holds true that $\langle z, u_t^{(j)}\rangle = 0$ for all $z\in S^\perp$ and all $j=1,\dots,J$. In the following, we extend the existence of solutions globally. Therefore, we consider the Lyapunov function $$V_{\bar u} (u_t) = \varphi(\|\bar u_t\|^2) + \frac{B_1}J\sum_{j=1}^J\|u_t^{(j)}-\bar u_t\|^2 + B_2$$ for $\varphi:{\mathbb{R}}\to{\mathbb{R}}$ with $\varphi(z) = \log(1+z)$ and sufficiently large $B_1,B_2>0$. We firstly observe that $z\varphi'(z) = \frac{z}{1+z}\le 1$ for $z\ge0$. The time evolution of $\varphi(\|\bar u_t\|^2)$ is given by $$\begin{aligned}
\frac{\mathrm{d}}{{\mathrm{d}}t}&\varphi(\|\bar u_t\|^2) = 2\varphi'(\|\bar u_t\|^2)\left(- \langle \bar u_t, C^{u,G}(u_t)\Gamma^{-1}(\bar G_t-y)\rangle - \langle \bar u_t, C(u_t)C_0^{-1}\bar u_t\rangle\right)\\
&\le 2\varphi'(\|\bar u_t\|^2) \left(\|\bar u_t\|\|\bar G_t-y\|_\Gamma \|C^{u,G}(u_t)\Gamma^{-1/2}\|_{\mathrm{HS}} + \|\bar u_t\|\|\bar u_t\|_{C_0} \|C(u_t)C_0^{-1/2}\|_{\mathrm{HS}}\right)\\
&\le \varphi'(\|\bar u_t\|^2)^2\|\bar u_t\|^2 (2\|\bar G_t - G(\bar u_t)\|_\Gamma^2+2\|G(\bar u_t)-y\|_\Gamma^2) +  \|C^{u,G}(u_t)\Gamma^{-1/2}\|_{\mathrm{HS}}^2\\ &\quad+  \varphi'(\|\bar u_t\|^2)^2\|\bar u_t\|^2 \|\bar u_t\|_{C_0}^2 +  \|C(u_t)C_0^{-1/2}\|_{\mathrm{HS}}^2,\end{aligned}$$ where we have applied Young's inequality and $$\|\bar G_t-y\|_\Gamma^2\le (\|\bar G_t-G(\bar u_t)\|_\Gamma+\|G(\bar u_t)-y\|_\Gamma)^2\le 2\|\bar G_t-G(\bar u_t)\|_\Gamma^2+2\|G(\bar u_t)-y\|_\Gamma)^2$$ for the last inequality. With Lipschitz continuity of $G$, Cauchy-Schwarz inequality and Jensen's inequality we have that $$\begin{aligned}
\|\bar G - G(\bar u) \|^2 = \frac{1}{J^2}\sum_{j,l}^2 \langle G(u^{(j)})-G(\bar u),G(u^{(l)})-G(\bar u)\rangle &\le c_{\mathrm{lip}}^2\left(\frac{1}{J}\sum_{j=1}^J \|u^{(j)} - \bar u\|\right)^2 \\
&\le c_{\mathrm{lip}}^2\frac{1}{J}\sum_{j=1}^J \|u^{(j)} - \bar u\|^2.\end{aligned}$$ Hence, using $z\varphi'(z)\le 1$ we obtain $$\begin{aligned}
\frac{\mathrm{d}}{{\mathrm{d}}t}\varphi(\|\bar u_t\|^2) &\le c_1\frac{1}{J}\sum_{j=1}^J \|u_t^{(j)} - \bar u_t\|^2+ \tilde c_2 \varphi'(\|\bar u\|^2)\Phi_R(\bar u_t)\\ &\quad+  \|C^{u,G}(u_t)\Gamma^{-1/2}\|_{\mathrm{HS}}^2+ \|C(u_t)C_0^{-1/2}\|_{\mathrm{HS}}^2\\
&\le c_1\frac{1}{J}\sum_{j=1}^J \|u_t^{(j)} - \bar u_t\|^2+ c_2 +  \|C^{u,G}(u_t)\Gamma^{-1/2}\|_{\mathrm{HS}}^2+ \|C(u_t)C_0^{-1/2}\|_{\mathrm{HS}}^2\end{aligned}$$ for some constants $c_1,c_2>0$. Here we have used, that $\Phi_R(u)\le c\|u\|^2$ for local Lipschitz continuous $G$. On the other side, we have $$\begin{aligned}
\frac{{\mathrm d}\frac1J\sum_{j=1}^J \|u_t^{(j)}-\bar u_t\|^2}{{\mathrm d}t} &= -\frac{2}{J^2} \sum_{j,k=1}^J \langle u_t^{(j)}-\bar u_t,u_t^{(k)}-\bar u_t\rangle \langle G(u_t^{(k)})-\bar G_t,G(u_t^{(j)})-\bar G_t\rangle_{\Gamma}\\
                    &\quad - \frac{2}{J^2} \sum_{j,k=1}^J \langle u_t^{(j)}-\bar u_t,u_t^{(k)}-\bar u_t\rangle \langle u_t^{(k)}-\bar u_t,C_0^{-1}(u_t^{(j)}-\bar u_t)\rangle\\
                    &= -2\|C^{u,G}(u_t)\Gamma^{-1/2}\|_{\mathrm{HS}}^2-2\|C(u_t)C_0^{-1/2}\|_{\mathrm{HS}}^2.\end{aligned}$$ It follows for $B_1>c_1$ and $B_2>c_2$ that $$\frac{\mathrm{d}}{{\mathrm{d}}t}V_{\bar u}(u_t) \le c V_{\bar u}(u_t)$$ and by application of Gronwall's inequality for all $T>0$ the solution of remains bounded.

In the following we define the spread of the particle system by $$e_t^{(j)} = u_t^{(j)}- \bar u_t.$$

From Lemma 3.7 and Corollary 3.8 in @CST19 it is known that the TEKI flow satisfies the following extended subspace property.

\[Corollary 3.8, @CST19\]\[prop:subspace\_prop\] Let $(u_0^{(j)})_{j=1,\dots,J}$ be the linearly independent initial ensemble and define the subspace $${\mathcal{B}}= u_0^\perp + \operatorname{span}\{e_0^{(j)} \mid j=1,\dots,J\},$$ where $u_0^\perp = \bar u_0 - \mathcal P_E \bar u_0$, where $\mathcal P_E= E(E^\top E)^{-1}E^T$ with $E=((e_0^{(1)})^\top,\dots,(e_0^{(J)})^\top)\in\mathbb R^{n_x\times J}$ is the orthogonal projection on the subspace $\operatorname{span}\{e_0^{(j)} \mid j=1,\dots,J\}$. Then for $T\ge 0$ the unique solution $(u_t^{(j)}, t\in[0,T])$ of the TEKI flow remains in $\mathcal B$, i.e.  $u_t^{(j)} \in \mathcal B$ for all $t\in[0,T]$ and all $j=1,\dots,J$.

On the one side the spread of the particle system describes the accuracy of the gradient approximation, which gets more accurate for a less spread particle system. On the other side, the spread of the particle system determines the preconditioning effect through the sample covariance. For this reason we aim for a collapse of the ensemble but not too fast. In our first result, we prove that the ensemble collapses with rate $1/t$.

\[lem:ensemble\_collapse\] Let $(u_t^{(j)},t\ge0)_{j=1,\dots,J}$ be the solution of initialized by a linearly independent ensemble $(u_0^{(j)})_{j=1,\dots,J}$. Then the mapping $V_e:\mathbb R_+\to \mathbb R_+$ with $t\mapsto \frac{1}{J}\sum_{j=1}^J\|e_t\|^2$ is bounded by $$V_e(t) \le \frac{1}{\frac{2\sigma_{\min}}{J} t + V_e(0)^{-1}},$$ where $\sigma_{\min}$ denotes the smallest eigenvalue of $C_0^{-1}$.

The evolution of $V_e(t)$ is given by $$\begin{aligned}
\frac{{\mathrm d}\frac1J\sum_{j=1}^J \|u_t^{(j)}-\bar u_t\|^2}{{\mathrm d}t} &= -\frac{2}{J^2} \sum_{j,k=1}^J \langle u_t^{(j)}-\bar u_t,u_t^{(k)}-\bar u_t\rangle \langle G(u_t^{(k)})-\bar G_t,G(u_t^{(j)})-\bar G_t\rangle_{\Gamma}\\
                    &\quad - \frac{2}{J^2} \sum_{j,k=1}^J \langle u_t^{(j)}-\bar u_t,u_t^{(k)}-\bar u_t\rangle \langle u_t^{(k)}-\bar u_t,C_0^{-1}(u_t^{(j)}-\bar u_t)\rangle\\
                    &= -2\|C^{u,G}(u_t)\Gamma^{-1/2}\|_{\mathrm{HS}}^2\\ &\quad-\frac{2}{J^2} \sum_{j,k=1}^J \langle u_t^{(j)}-\bar u_t,u_t^{(k)}-\bar u_t\rangle \langle u_t^{(k)}-\bar u_t,C_0^{-1}(u_t^{(j)}-\bar u_t)\rangle\\
                    &\le -\frac{2\sigma_{\min}}{J} \left(\frac1J\sum_{j=1}^J \|u_t^{(j)}-\bar u_t\|^2\right)^2.\end{aligned}$$ Hence, we have shown $$\frac{{\mathrm d}V_e(t)}{{\mathrm d}t} \le - \frac{2\sigma_{\min}}{J}V_e(t)^2$$ and the assertion follows by Lyapunov-type argument.

In the following result, we state that, although the sample covariance degenerates along the particle evolution, it remains a strictly positive definite operator acting on the subspace <span>$\mathcal B$</span>.

\[lem:cov\_subspace\] Let $(u_t^{(j)},t\ge0)_{j=1,\dots,J}$ be the solution of initialized by a linearly independent ensemble $(u_0^{(j)})_{j=1,\dots,J}$ such that $$\label{eq:smallest_eigenvalue}
\zeta_0 = \min_{z\in {\mathcal B},\ \|z\|=1}\ \langle z,C(u_0)z\rangle > 0.$$ For each $z\in {\mathcal B}$ with $\|z\|=1$ it holds true that $$\langle z, C(u_t) z\rangle \ge \frac{1}{m t+\zeta_0^{-1}},$$ where $m=2 (c_{\mathrm{lip}}^2\lambda_{\max}V_e(0)+\sigma_{\max})>0$ depends on the smallest and largest eigenvalue $\sigma_{\max}$ and $\sigma_{\min}$ of $C_0^{-1}$, the largest eigenvalue $\lambda_{\max}$ of $\Gamma^{-1}$ and the Lipschitz constant $c_{\mathrm{lip}}$ of $G$.

We note that the following proof is closely related to the proof of Theorem 3.5 in @CST19, where the authors derived an upper bound on the sample covariance matrix. The time evolution of the sample covariance is given by $$\begin{aligned}
\frac{{\mathrm d} C(u_t)}{{\mathrm d}t} &= \frac{1}{J}\sum_{j=1}^J \frac{{\mathrm d}e_t^{(j)}}{{\mathrm d}t}\left(e_t^{(j)}\right)^\top + \frac{1}{J}\sum_{j=1}^J e_t^{(j)}\left(\frac{{\mathrm d}e_t^{(j)}}{{\mathrm d}t}\right)^\top\\
& = -2C^{u,G}(u_t)\Gamma^{-1}C^{G,u}(u_t) - 2C(u_t)C_0^{-1}C(u_t).\end{aligned}$$ Let $z\in {\mathcal B}$ with $\|z\|=1$, then we have that $$\begin{aligned}
\langle z, \frac{{\mathrm d} C(u_t)}{{\mathrm d}t} z\rangle
& = -2 \|C^{G,u}(u_t)z\|_{\Gamma}^2 - 2\|C(u_t)z\|_{C_0}^2.\end{aligned}$$

Since $G$ is locally Lipschitz, we obtain with Cauchy-Schwarz $$\begin{aligned}
\|C^{G,G}(u_t)\|_{\mathrm{HS}} = \operatorname{Tr}(C^{G,G}(u_t)C^{G,G}(u_t))^{1/2} &\le \frac1J\sum_{j=1}^J\|G(u_t^{(j)})-\bar G\|^2 \\ &\le c_{\mathrm{lip}}^2 V_e(t)\le c_{\mathrm{lip}}^2V_e(0)\end{aligned}$$ and therefore it follows with $\|C^{G,u}(u_t)z\|^2 \le \|C^{G,G}\|_{\mathrm{HS}} \|C(u_t)z\|_{\mathrm{HS}}$ that $$\|C^{G,u}(u_t)z\|_{\Gamma}^2\le c_{\mathrm{lip}}^2\lambda_{\max}V_e(0) \|C(u_t) z \|_{C_0}^2.$$ Hence, we have derived $$\frac{{\mathrm d} \langle z,C(u_t)z\rangle }{{\mathrm d}t} \ge -2(c_{\mathrm{lip}}^2\lambda_{\max}V_e(0)+\sigma_{\max})\|C(u_t)z\|^2.
$$ Next, we consider $C(u_t)$ as operator acting on <span>$\mathcal B$</span> and denote its smallest eigenvalue $\zeta_t\ge0$ with unit-norm eigenvector $\varphi(t)\in {\mathcal B}$. In the following we will prove that $\zeta_t$ is indeed strictly positive. Since $\|\varphi(t)\|=1$ for all $t\ge0$, we observe that $$0 = \frac{{\mathrm{d}}\|\varphi(t)\|^2}{{\mathrm d}t} = 2\langle \varphi(t),\frac{{\mathrm d}\varphi(t)}{{\mathrm d}t}\rangle.$$ Hence, we can describe the time-evolution of the smallest eigenvalue $\zeta_t$ of $C(u_t)$ (initialized with $\zeta_0>0$) through $$\begin{aligned}
\frac{{\mathrm d}}{{\mathrm d}t}\zeta_t = \frac{{\mathrm d}}{{\mathrm d}t}\langle \varphi(t),C(u_t) \varphi(t)\rangle &= \langle \varphi(t), \frac{{\mathrm d}C(u_t)}{{\mathrm d}t}\varphi(t)\rangle + 2\langle \frac{{\mathrm d}\varphi(t)}{{\mathrm d}t}, C(u_t)\varphi(t)\rangle\\
& = \langle \varphi(t), \frac{{\mathrm d}C(u_t)}{{\mathrm d}t} \varphi(t)\rangle + 2\zeta_t\langle \frac{{\mathrm d}\varphi(t)}{{\mathrm d}t}, \varphi(t)\rangle\\
&= \langle \varphi(t), \frac{{\mathrm d}C(u_t)}{{\mathrm d}t} \varphi(t)\rangle\\
&\ge -2 (c_{\mathrm{lip}}^2\lambda_{\max}V_e(0)+\sigma_{\max})\|C(u_t)\varphi(t)\|^2\\
&\ge -2(c_{\mathrm{lip}}^2\lambda_{\max}V_e(0)+\sigma_{\max})\zeta_t^2.\end{aligned}$$ With the above computation we obtain the lower bound on the smallest eigenvalue of $C(u_t)$ as operator acting on <span>$\mathcal B$</span> by $$\zeta_t \ge \frac{1}{2(c_{\mathrm{lip}}^2\lambda_{\max}V_e(0)+\sigma_{\max}) t+ \zeta_0^{-1}}>0,$$ and the assertion follows with $$\label{eq:const_m}
m:=2 (c_{\mathrm{lip}}^2\lambda_{\max}V_e(0)+\sigma_{\max})>0.$$

Gradient approximation via Taylor expansion
-------------------------------------------

In the following we will quantify how the TEKI flow approximates gradients and hence can be viewed as gradient flow.

\[lem:grad\_approx\] Suppose that Assumption \[ass:Taylor\] is satisfied. Given a particle system $(u^{(j)})_{j=1,\dots,J}$ it holds true that $$\|C^{u,G}(u)\Gamma^{-1}(G(u^{(j)})-y) - C(u) \nabla\Phi(u^{(j)})\| \le b_1 J \sqrt{\Phi(u^{(j)})}\left(\frac1J\sum_{k=1}^J\|u^{(k)}-\bar u\|^2\right)^{3/2},$$ for some $b_1$ independent of $J$.

We apply and compute $$\begin{aligned}
&C^{u,G}(u)\Gamma^{-1}(G(u^{(j)})-y) = \frac{1}{J}\sum_{k=1}^J \langle G(u^{(k)})-\bar G, G(u^{(j)})-y\rangle_\Gamma (u^{k}-\bar u)\\
&= \frac{1}J \sum_{k=1}^J \langle G(u^{(j)}) + {\mathrm D}G(u^{(j)})(u^{(k)}- u^{(j)}) + {\mathrm{Res}}(u^{(k)},u^{(j)}),G(u^{(j)})-y\rangle_{\Gamma}(u^{(k)}-\bar u) \\ &\quad - \frac1J\sum_{l=1}^J \langle G(u^{(j)}) + {\mathrm D}G(u^{(j)}) (u^{(l)}-u^{(j)}) + {\mathrm{Res}}(u^{(l)},u^{(j)}) ,G(u^{(j)})-y\rangle_{\Gamma}(u^{(k)}-\bar u)\\
& = \frac{1}{J}\sum_{k=1}^J \langle {\mathrm D}G(u^{(j)})(u^{(k)}-\bar u),G(u^{(j)})-y\rangle_\Gamma(u^{(k)}-\bar u)\\ &\quad + \frac{1}{J}\sum_{k=1}^J \langle {\mathrm{Res}}(u^{(k)},u^{(j)})-\overline{\mathrm{Res}}^{(j)},G(u^{(j)})-y\rangle_{\Gamma}(u^{(k)}-\bar u)\\
& = C(u)\nabla\Phi(u^{(j)}) + \frac{1}{J}\sum_{k=1}^J \langle {\mathrm{Res}}(u^{(k)},u^{(j)})-\overline{\mathrm{Res}}^{(j)},G(u^{(j)})-y\rangle_\Gamma(u^{(k)}-\bar u),\end{aligned}$$ where we have defined $$\overline{\mathrm{Res}}^{(j)} = \frac{1}{J}\sum_{l=1}^J{\mathrm{Res}}(u^{(l)},u^{(j)}).$$ It follows with Assumption \[ass:Taylor\] and Cauchy-Schwarz that $$\begin{aligned}
&\|C^{u,G}(u)\Gamma^{-1}(G(u^{(j)})-y)-C(u)\nabla\Phi(u^{(j)}) \|\\ &\le b_{\mathrm{res}}\|\Gamma^{-1/2}\| \frac{1}{J}\sum_{k=1}^J 4\left(\|u^{(k)}-u^{(j)}\|^2+\frac1J\sum_{l=1}^J \|u^{(l)}-u^{(j)}\|^2\right)\|u^{(k)}-\bar u\|\|G(u^{(j)})-y\|_{\Gamma}\\
&\le b_{\mathrm{res}}\|\Gamma^{-1/2}\| \frac{1}{J}\sum_{k=1}^J 4\left((1+\frac1J)\sum_{l=1}^J \|u^{(l)}-u^{(j)}\|^2\right)\|u^{(k)}-\bar u\|\|G(u^{(j)})-y\|_{\Gamma}\\
&\le b_{\mathrm{res}}\|\Gamma^{-1/2}\| (8+\frac{2}{J})J\|G(u^{(j)})-y\|_\Gamma\left(\frac1J\sum_{k=1}^J\|u^{(k)}-\bar u\|^2\right)^{3/2},\end{aligned}$$ where we have used that $$\|u^{(l)}-u^{(j)}\|^2 \le 2 \|u^{(l)}-\bar u\|^2 + 2 \|u^{(j)}-\bar u\|^2.$$

We are now ready to prove Proposition \[prop:gradientflow\_structure\] in order to quantify the gradient flow structure of TEKI.

\[Proof of Proposition \[prop:gradientflow\_structure\]\] We apply chain rule for deriving the time-evoluiton of $V_{\Phi_R}(t) := \frac1J \sum_{j=1}^J\Phi_R(u_t^{(j)})$ as $$\begin{aligned}
\frac{{\mathrm d}V_{\Phi_R}(t)}{{\mathrm d}t} &= \frac{{\mathrm d}V_{\Phi_R}(t)}{{\mathrm d}t} = \frac1J\sum_{j=1}^J \langle \nabla\Phi_R(u_t^{(j)}),\frac{{\mathrm d}u_t^{(j)}}{{\mathrm d}t}\rangle\\
&= -\frac{1}{J}\sum_{j=1}^J \langle \nabla \Phi_R(u_t^{(j)}), C(u_t)\nabla\Phi_R(u_t^{(j)})\rangle \\
&\quad + \frac{1}{J}\sum_{j=1}^J \langle  \nabla\Phi_R(u_t^{(j)}), C^{u,G}(u_t)\Gamma^{-1}(G(u_t^{(j)})-y)-C(u_t)\nabla \Phi(u_t^{(j)})\rangle.\end{aligned}$$ We apply Cauchy-Schwarz inequality and Lemma \[lem:grad\_approx\] such that $$\begin{aligned}
\frac{{\mathrm d}V_{\Phi_R}(t)}{{\mathrm d}t} &\le  -\frac{1}{J}\sum_{j=1}^J \langle \nabla \Phi_R(u_t^{(j)}), C(u_t)\nabla\Phi_R(u_t^{(j)})\rangle\\
&\quad + b_1 J V_e(t)^{3/2}\frac{1}{J}\sum_{j=1}^J\|\nabla\Phi_R(u_t^{(j)})\|\sqrt{\Phi(u_t^{(j)})}\\ &\le  -\frac{1}{J}\sum_{j=1}^J \langle \nabla \Phi_R(u_t^{(j)}), C(u_t)\nabla\Phi_R(u_t^{(j)})\rangle\\
&\quad + b_1 J V_e(t)^{3/2}\frac{1}{J}\sum_{j=1}^J\left(\frac{1}{2}\|\nabla\Phi_R(u_t^{(j)})\|^2+ \Phi(u_t^{(j)}) \right).\end{aligned}$$ The claim follows with $\Phi(x)\le \Phi_R(x)$.

TEKI as constrained optimization method
---------------------------------------

Before proving our main convergence result, we need to quantify the behaviour of the preconditioning effect through the sample covariance, i.e. what does it mean to consider the direction $C(u_t)\nabla\Phi_R(u_t^{(j)})$ instead of the steepest descent direction given through $\nabla\Phi_R(u_t^{(j)})$. We first note that once $C(u_t)$ can be identified as strictly positive definite operator on the whole parameter space $\mathcal X$, the scheme can be viewed as global optimization method. However, in general it is not true that $C(u_t)$ describes a strictly positive definite operator on the parameter space $\mathcal X$ and indeed, $C(u_t)$ has at most rank $\min(n_x,J-1)$ and hence is positive semi-definite in case $J-1<n_x$. While $C(u_t)$ is only positive semi-definite on the whole space $\mathcal X$, we have verified in Lemma \[lem:cov\_subspace\] that $C(u_t)$ is a strictly positive definite operator acting on the subspace <span>$\mathcal B$</span> spanned through the initial ensemble. We will make use of this property in order to quantify the TEKI flow as optimizer for the constrained optimization problem <span> $$\min_{x\in \mathcal X}\ \Phi_R(x),\quad x\in\mathcal B= u_0^\perp + \operatorname{span}\{e_0^{(j)} \mid j=1,\dots,J\}. $$ </span> Since we have assumed the finite dimensional setting $\mathcal X=\mathbb R^{n_x}$, we reformulate this problem as equality constrained optimization problem $$\label{eq:constr_opti2}
\min_{x\in \mathbb R^{n_x}}\ \Phi_R(x),\quad \text{s.t.}\quad h_i(x) = \langle q^{(i)},x\rangle = 0,\ i=J+1,\dots, n_x,$$ where <span>$q^{(i)}\perp e_0^{(j)}$ and $q^{(i)}\perp u_0^\perp$</span> for all $j=1,\dots,J$ and $i=J+1,\dots,n_x$. Since under Assumption \[ass:smoothness\] $\Phi_R$ is assumed to be strongly convex, there exists a unique global solution $u_\ast$ of @DPB15 [Proposition 2.1.1]. By the Lagrange multiplier theorem @DPB15 [Proposition 3.1.1.] there exist $\kappa_{J+1}^\ast,\dots,\kappa_{n_x}^\ast\in\mathbb R$ $$\label{eq:nec_conditions}
\nabla\Phi_R(u_\ast) + \sum_{i=J+1}^{n_x}\kappa_i \nabla h_i(x_\ast) = 0.$$ We will make use of this necessary condition in order to derive the following constrained PL-type inequality.

\[lem:constr\_PL\] Suppose Assumption \[ass:smoothness\] is satisfied and let $x_\ast$ be the unique global minimizer of . Then there exists $\nu>0$ such that for all $x\in{\mathcal B}$ it holds true that $$\nu\|\nabla \Phi_R(x)\|^2\ge \Phi_R(x)-\Phi_R(x_\ast).$$ Moreover, let <span>$\mathcal P_{\mathcal B}$</span> be the orthogonal projection onto <span>$\mathcal B$</span>. Then it holds true that $${\nu\|\mathcal P_{\mathcal B}\nabla \Phi_R(\mathcal P_{\mathcal B} x)\|^2\ge \Phi_R(\mathcal P_{\mathcal B} x) - \Phi_R(x_\ast)}$$ for all $x\in\mathbb R^{n_x}$.

Consider some arbitrary <span>$x\in \mathcal B$</span>. By $L$-smoothness and the necessary optimality condition we have that $$\begin{aligned}
\Phi_R(x)&\le \Phi_R(x_\ast) + \langle \nabla\Phi_R(x_\ast),x-x_\ast\rangle + \frac{L}{2}\|x-x_\ast\|^2\\
& = \Phi_R(x_\ast) - \sum_{i=J+1}^{n_x} \kappa_i \langle \nabla h_i(x_\ast),x-x_\ast\rangle + \frac{L}{2}\|x-x_\ast\|^2\\
& = \Phi_R(x_\ast) - \sum_{i=J+1}^{n_x} \kappa_i \langle q^{(i)},x-x_\ast\rangle + \frac{L}{2}\|x-x_\ast\|^2\\
& = \Phi_R(x_\ast) + \frac{L}{2}\|x-x_\ast\|^2,\end{aligned}$$ where we have used $x,x_\ast\perp q^{(i)}$ for all $i=J+1,\dots,n_x$. On the other side with $\mu$-strong convexity and Cauchy-Schwarz we obtain $$\frac{\mu}{2} \|x_\ast-x\| \le \|\nabla \Phi(x)\|$$ leading to $$\Phi_R(x)-\Phi_R(x_\ast) \le \frac{L}{2} \|x-x_\ast\|^2 \le \frac{L}{\mu}\|\nabla\Phi_R(x)\|^2.$$ For the second claim, consider $x\in\mathbb R^{n_x}$. By $\mu$-strong convexity it follows $$\langle {\mathcal P_{\mathcal B}} \nabla \Phi_R(x), {\mathcal P_{\mathcal B}}(x-x_\ast)\rangle = \langle \nabla \Phi_R(x),  {\mathcal P_{\mathcal B}}x-x_\ast)\rangle \ge \Phi_R({\mathcal P_{\mathcal B}} x)-\Phi_R(x_\ast)+\frac{\mu}{2} \|{\mathcal P_{\mathcal B}} x-x_\ast\|^2.$$ The assertion follows again by applying Cauch-Schwarz inequality and $L$-smoothness.

Proof of Theorem \[thm:main\] {#sec:proof_main}
=============================

We are now ready to present the proof of our main convergence result.

\[Proof of Theorem \[thm:main\]\] Let $\mathcal B= u_0^\perp + \operatorname{span}\{e_0^{(j)} \mid j=1,\dots,J\}$ and let <span>$\mathcal P_{\mathcal B}$</span> be the orthogonal projection onto <span>$\mathcal B$</span>. Recall that from Proposition \[prop:gradientflow\_structure\] we have that $$\begin{aligned}
\frac{{\mathrm d}\frac1J\sum_{j=1}^J\left(\Phi_R(u_t^{(j)})\right)}{{\mathrm d}t} &\le -\frac1J\sum_{j=1}^J \langle \nabla \Phi_R(u_t^{(j)}), C(u_t) \nabla \Phi_R(u_t^{(j)})\rangle\\ &\quad+  b_1 J V_e(t)^{3/2}\frac{1}{J}\sum_{j=1}^J\left(\frac{1}{2}\|\nabla\Phi_R(u_t^{(j)})\|^2+ \Phi_R(u_t^{(j)}) \right)\\
&\le -\frac1J\sum_{j=1}^J \langle \nabla \Phi_R(u_t^{(j)}), C(u_t)\nabla \Phi_R(u_t^{(j)})\rangle\\ &\quad+ \frac32 b_1 J \left(\frac{1}{\frac{2\sigma_{\min}}{J}t+V_e(0)^{-1}}\right)^{3/2}\frac{1}{J}\sum_{j=1}^J(\Phi_R(u_t^{(j)})-\Phi_R(u_\ast)) \\
&\quad+ \tilde b_1 J \left(\frac{1}{\frac{2\sigma_{\min}}{J}t+V_e(0)^{-1}}\right)^{3/2}\Phi_R(u_\ast)),\end{aligned}$$ where we have used strong convexity. Due to the subspace space property in Proposition \[prop:subspace\_prop\] we obtain $C(u_t) =  \mathcal P_{\mathcal B}C(u_t) \mathcal P_{\mathcal B}$ and with Lemma \[lem:cov\_subspace\] it holds true that $$\begin{aligned}
 \langle \nabla \Phi_R(u_t^{(j)}), C(u_t) \nabla \Phi_R(u_t^{(j)})\rangle &=  \langle {\mathcal P_{\mathcal B}}\nabla \Phi_R(u_t^{(j)}), C(u_t) {\mathcal P_{\mathcal B}}\nabla \Phi_R(u_t^{(j)})\rangle\\ &\ge  \frac{1}{mt+\zeta_0^{-1}}\|{\mathcal P_{\mathcal B}}\nabla\Phi_R(u_t^{(j)}) \|^2,
  \end{aligned}$$ where $m>0$ is defined in and $\zeta_0$ is defined in . Hence, we define $V_{\Phi_R}(t):=\frac{1}{J}\sum_{j=1}^J \Phi_R(u_t^{(j)})-\Phi_R(u_\ast) $ and apply Lemma \[lem:constr\_PL\] in order to obtain $$\begin{aligned}
\frac{{\mathrm d}V_{\Phi_R}(t)}{{\mathrm d}t} = \frac{{\mathrm d}\frac1J\sum_{j=1}^J\left(\Phi_R(u_t^{(j)})\right)}{{\mathrm d}t} &\le - \frac{1}{\frac{L}{\mu}mt+\zeta_0^{-1}}V_{\Phi_R}(t)\\
&\quad+ \tilde b_1 J \left(\frac{1}{\frac{2\sigma_{\min}}{J}t+V_e(0)^{-1}}\right)^{3/2} V_{\Phi_R}(t) \\
&\quad+ \tilde b_1 J \left(\frac{1}{\frac{2\sigma_{\min}}{J}t+V_e(0)^{-1}}\right)^{3/2}\Phi_R(u_\ast).\end{aligned}$$ It follows with $\alpha = \frac{L}{\mu}m>0$ that $$\begin{aligned}
\frac{{\mathrm d}V(t)}{{\mathrm d}t}\le -\frac{1}{\alpha t+a} V(t) + \left(\frac{z_1}{z_2+z_3t} \right)^{3/2}(V(t)+c)\end{aligned}$$ for some constants $a,z_1,z_2,z_3,c>0$. By Gronwall's inequality we obtain $$\begin{aligned}
V(t) &\le V(0) \left(\int_0^t \left(\frac{z_1}{z_2+z_3s} \right)^{3/2}\, {\mathrm d}s\right) \exp\left(\int_0^t \left(\frac{z_1}{z_2+z_3s} \right)^{3/2}\,{\mathrm d}s -\int_0^t \frac{1}{\alpha s+a}\,{\mathrm d}s\right)\\
&\le \left(\frac{c_1}{t+c_2}\right)^{\frac1\alpha},\end{aligned}$$ for some constants $c_1,c_2>0$.

\[rem:higher\_apprx\] We note that under the relaxed assumption $\|{\mathrm{Res}}(x,y)\| \le b_{\mathrm{res}} \|x-y\|^p$, for $p\ge 2$ such that $p/2\in\mathbb N$, we obtain a similar bound for the gradient approximation as in Lemma \[lem:grad\_approx\] given by $$\begin{aligned}
&\|C^{u,G}(u)\Gamma^{-1}(G(u^{(j)})-y)-C(u)\nabla\Phi(u^{(j)}) \|\\ 
&\le b_{\mathrm{res}}\|\Gamma^{-1/2}\| (8+\frac{2}{J})J(4J)^{p/2}\|G(u^{(j)})-y\|_\Gamma\left(\frac1J\sum_{k=1}^J\|u^{(k)}-\bar u\|^2\right)^{1/2+p/2}.\end{aligned}$$ Here, we have applied Binomial theorem to imply the inequality $$\sum_{j=1}^{J}a_j^p\le \left(\sum_{j=1}^{J} a_j^2\right)^{p/2},\quad a_j\ge0.$$ Since $p\ge2$ the integral $\int_0^t \left(\frac{z_1}{z_2+z_3s} \right)^{1/2+p/2}\,{\mathrm d}s$ in the above proof remains finite and hence the asymptotic convergence result in Theorem \[thm:main\] still holds.

Stabilization via covariance inflation: A generalized ensemble square root filter for inverse problems {#sec:ESRF}
======================================================================================================

The incorporation of covariance inflation is a data assimilation tool in order to stabilize convergence and often used in pratice @JLA09 [@JLA07; @47c5c78ebb8c44ef9d8d5e0d23e23c13]. In the following we present a form of covariance inflation for the TEKI flow for which it turns out to be a generalized formulation of the ensemble square root filter (ESRF) @RC14 applied to inverse problems.

Through our incorporation of covariance inflation we obtain in approximation a weighted gradient flow structure between the current particle position and the position of the ensemble mean. Roughly speaking, the TEKI flow can then be viewed as approximation of the equation: $$\label{eq:approx_ESRF_flow}
\frac{\mathrm{d}u_t^{(j)}}{{\mathrm d}t} = - C(u_t) \left((1-\rho)\nabla \Phi_R(u_t^{(j)})+\rho\nabla \Phi_R(\bar u_t)\right),$$ where $\rho\in[0,1)$ describes the weight of the gradients of the particles and the mean. Based on @bergemann2010mollified [@bergemann2010localization] the continuous time formulation of the ESRF applied to inverse problems has been analysed in @CSW19 for linear forward models and the special case $\rho=1/2$. In the following, we will incorporate the covariance inflation and theoretical quantify the approximate gradient flow structure. Finally, we will observe an acceleration in convergence towards the optimal solution restricted to the subspace spanned through the initial ensemble spread.

![Illustration of the effect through the incorporation of the covariance inflation. Each particle is getting moved into its own direction as well as into a joint direction.<span data-label="fig:covariance_inflation"></span>](./without_covariance_inflation.eps "fig:") ![Illustration of the effect through the incorporation of the covariance inflation. Each particle is getting moved into its own direction as well as into a joint direction.<span data-label="fig:covariance_inflation"></span>](./covariance_inflation.eps "fig:")

Incorporation of covariance inflation
-------------------------------------

The covariance inflation is incorporated through the following modified TEKI flow $$\label{eq:cov_inflation}
\begin{split}
\frac{{\mathrm d}u_t^{(j)}}{{\mathrm d}t} &= C^{u,G}(u_t)\Gamma^{-1}(y-G(u_t^{(j)}))-C(u_t)C_0^{-1}u_t^{(j)}\\  &\quad+ \rho C^{u,G}(u_t)\Gamma^{-1}(G(u_t^{(j)})-\bar G) +\rho C(u_t)C_0^{-1}(u_t^{(j)}-\bar u).
\end{split}$$ The idea behind this incorporation comes from the fact that the inflating term does not directly change the dynamical behavior of the particles mean, since the evolution $$\label{eq:cov_inflation_mean}
\frac{{\mathrm d}\bar u_t}{{\mathrm d}t} = C^{u,G}(u_t)\Gamma^{-1}(y-\bar G_t)-C(u_t)C_0^{-1}\bar u_t$$ coincides with the unmodified dynamic (i.e. $\rho=0$). However the inflating term decreases the force of collapsing the particle system and hence leads to a slower ensemble collapse without changing the collapse rate $1/t$ but decreasing the constant. For the interpretation from the optimization point of view we rewrite as $$\label{eq:cov_inflation2}
\begin{split}
\frac{{\mathrm d}u_t^{(j)}}{{\mathrm d}t} &= (1-\rho)\left\{C^{u,G}(u_t)\Gamma^{-1}(y-G(u_t^{(j)}))-C(u_t)C_0^{-1}u_t^{(j)}\right\}\\
&\quad +\rho\left\{C^{u,G}(u_t)\Gamma^{-1}(y-\bar G_t)-C(u_t)C_0^{-1}\bar u_t\right\}.
\end{split}$$ motivating the modified TEKI flow as approximation of . The movement of the particle system through is described through two forces. The first force is given by $$C^{u,G}(u_t)\Gamma^{-1}(y-G(u_t^{(j)}))-C(u_t)C_0^{-1}u_t^{(j)}$$ moving each particle in its own direction and leading to a collapse of the ensemble and hence to a better gradient approximation as we have already seen in Lemma \[lem:grad\_approx\]. The second force $$C^{u,G}(u_t)\Gamma^{-1}(y-\bar G_t)-C(u_t)C_0^{-1}\bar u_t$$ moves the whole particle system into the same direction without changing the spread and hence does not improve the gradient approximation. However, it accelerates the overall convergence of the optimization process since it slows down the degeneration of the preconditioning through the sample covariance matrix. We will start the theoretical analysis by considering the ensemble spread and its collapse behavior.

We first note, that unique existence of solutions of can be verified and the subspace property Propostion \[prop:subspace\_prop\] is obviously satisfied.

Let $(u_0^{(j)})_{j=1,\dots,J}$ be the linearly independent initial ensemble and define the subspace $${\mathcal{B}}= u_0^\perp + \operatorname{span}\{e_0^{(j)} \mid j=1,\dots,J\},$$ where $u_0^\perp = \bar u_0 - \mathcal P_E \bar u_0$, where $\mathcal P_E= E(E^\top E)^{-1}E^T$ with $E=((e_0^{(1)})^\top,\dots,(e_0^{(J)})^\top)\in\mathbb R^{n_x\times J}$ is the orthogonal projection on the subspace $\operatorname{span}\{e_0^{(j)} \mid j=1,\dots,J\}$. Then for all $T\ge 0$ and $\rho\in[0,T)$ the unique solution $(u_t^{(j)}, t\in[0,T])$ of the flow exists and remains in $\mathcal B$, i.e.  $u_t^{(j)} \in \mathcal B$ for all $t\in[0,T]$ and all $j=1,\dots,J$.

The following result states, that the ensemble collapse occurs with reduced rate through the factor $1-\rho\in(0,1]$.

\[lem:ensemble\_collapse\_ESRF\] Let $\rho\in[0,1)$ and $(u_t^{(j)},t\ge0)_{j=1,\dots,J}$ be the solution of initialized by a linearly independent ensemble $(u_0^{(j)})_{j=1,\dots,J}$. Then the mapping $V_e:\mathbb R_+\to \mathbb R_+$ with $t\mapsto \frac{1}{J}\sum_{j=1}^J\|e_t\|^2$ is bounded by $$V_e(t) \le \frac{1}{\frac{2(1-\rho)\sigma_{\min}}{J} t + V_e(0)^{-1}},$$ where $\sigma_{\min}$ denotes the smallest eigenvalue of $C_0^{-1}$.

The evolution of $V_e(t)$ is given by $$\begin{aligned}
\frac{{\mathrm d}\frac1J\sum_{j=1}^J \|u_t^{(j)}-\bar u_t\|^2}{{\mathrm d}t}
                    &= -(1-\rho)2\|C^{u,G}(u_t)\Gamma^{-1/2}\|_{\mathrm{HS}}\\ &\quad-\frac{(1-\rho)2}{J^2} \sum_{j,k=1}^J \langle u_t^{(j)}-\bar u_t,u_t^{(k)}-\bar u_t\rangle \langle u_t^{(k)}-\bar u_t,C_0^{-1}(u_t^{(j)}-\bar u_t)\rangle\\
                    &\le -\frac{2(1-\rho)\sigma_{\min}}{J} \left(\frac1J\sum_{j=1}^J \|u_t^{(j)}-\bar u_t\|^2\right)^2,\end{aligned}$$ and the assertion follows again by Lyapunov-type argument.

Similarly, we can derive the lower bound of the ensemble collapse.

\[lem:cov\_subspace\_ESRF\] Let $\rho\in[0,1)$ and $(u_t^{(j)},t\ge0)_{j=1,\dots,J}$ be the solution of initialized by a linearly independent ensemble $(u_0^{(j)})_{j=1,\dots,J}$ such that $$\zeta_0 = \min_{z\in {\mathcal B},\ \|z\|=1}\ \langle z,C(u_0)z\rangle > 0.$$ For each $z\in {\mathcal B}$ with $\|z\|=1$ it holds true that $$\langle z, C(u_t) z\rangle \ge \frac{1}{(1-\rho)m t+\zeta_0^{-1}},$$ where $m=2(c_{\mathrm{lip}}^2\lambda_{\max}V_e(0)+\sigma_{\max})>0$ depends on the smallest and largest eigenvalue $\sigma_{\max}$ and $\sigma_{\min}$ of $C_0^{-1}$, the largest eigenvalue $\lambda_{\max}$ of $\Gamma^{-1}$ and the Lipschitz constant $c_{\mathrm{lip}}$ of $G$.

The time evolution of the sample covariance is given by $$\begin{aligned}
\frac{{\mathrm d} C(u_t)}{{\mathrm d}t} &= \frac{1}{J}\sum_{j=1}^J \frac{{\mathrm d}e_t^{(j)}}{{\mathrm d}t}\left(e_t^{(j)}\right)^\top + \frac{1}{J}\sum_{j=1}^J e_t^{(j)}\left(\frac{{\mathrm d}e_t^{(j)}}{{\mathrm d}t}\right)^\top\\
& = -2(1-\rho)C^{u,G}(u_t)\Gamma^{-1}C^{G,u}(u_t) - 2(1-\rho)C(u_t)C_0^{-1}C(u_t)\end{aligned}$$ and similarly, for $z\in {\mathcal B}$ with $\|z\|=1$ we obtain $$\begin{aligned}
\langle z, \frac{{\mathrm d} C(u_t)}{{\mathrm d}t} z\rangle
& = -2(1-\rho) \|C^{G,u}(u_t)z\|_{\Gamma}^2 - 2(1-\rho)\|C(u_t)z\|_{C_0}^2\end{aligned}$$ and therefore $$\frac{{\mathrm d} \langle z,C(u_t)z\rangle }{{\mathrm d}t} \ge -2(1-\rho)(c_{\mathrm{lip}}^2\lambda_{\max}V_e(0)+\sigma_{\max})\|C(u_t)z\|^2.
$$ We consider again the smallest eigenvalue $\zeta_t\ge0$ of $C(u_t)$ restricted to <span>$\mathcal B$</span> with unit-norm eigenvector $\varphi(t)\in {\mathcal B}$. For the time-evolution of $\zeta_t$ we obtain $$\frac{{\mathrm d}}{{\mathrm d}t}\zeta_t \ge -2(1-\rho)(c_{\mathrm{lip}}^2\lambda_{\max}V_e(0)+\sigma_{\max})\zeta_t^2,$$ such that the assertion follows.

Our convergence result will be based on the mean of the particle system. Therefore we will need the following extension of Lemma \[lem:grad\_approx\].

\[lem:grad\_approx\_mean\] Suppose that Assumption \[ass:Taylor\] is satisfied. Given a particle system $(u^{(j)})_{j=1,\dots,J}$ it holds true that $$\|C^{u,G}(u)\Gamma^{-1}(\bar G-y) - C(u) \nabla\Phi(\bar u)\| \le b_1 J \sqrt{\Phi(\bar u)}\left(\frac1J\sum_{k=1}^J\|u^{(k)}-\bar u\|^2\right)^{3/2},$$ for some $b_1$ independent of $J$.

We apply triangular inequality $$\begin{aligned}
\|C^{u,G}(u)\Gamma^{-1}(\bar G-y) - C(u) \nabla\Phi(\bar u)\| &\le \|C^{u,G}(u)\Gamma^{-1}(\bar G-G(\bar u))\|\\ &\quad + \|C^{u,G}(u)\Gamma^{-1}(G(\bar u)-y) - C(u) \nabla\Phi(\bar u)\|.\end{aligned}$$ Using Lipschitz continuity and the inequality $\|C^{u,G}\|_{\mathrm{HS}}\le \sqrt{\|C^{u,u}\|_{\mathrm{HS}}\|C^{G,G}\|_{\mathrm{HS}}}$ we can bound the first term $$\|C^{u,G}(u)\Gamma^{-1}(\bar G-G(\bar u))\| \le \|\Gamma^{-1}\|c_{\mathrm{lip}}^2  \left(\frac1J\sum_{k=1}^J\|u^{(k)}-\bar u\|^2\right)^{3/2}.$$ The second term can be bounded similarly to Lemma \[lem:grad\_approx\] and the assertion follows.

\[thm:main2\] Suppose Assumption \[ass:smoothness\] and Assumption \[ass:Taylor\] are satisfied, let $(u_t^{(j)},t\ge0)_{j=1,\dots,J}$ solve with $\rho\in[0,1)$ and linearly independent initial ensemble $(u_0^{(j)})_{j=1,\dots,J}$ and let $u_\ast\in\mathcal B$ be the unique global minimizer of . Then there exist $c_1,c_2>0$ such that $$\label{eq:main_result2}
\Phi_R(\bar u_t)-\Phi_R(u_\ast) \le \left(\frac{c_1}{t+c_2}\right)^{\frac1\alpha},$$ where $0<\alpha < (1-\rho)\frac{L}{\mu}(\sigma_{\max}+c_{\mathrm{lip}}\lambda_{\max}\|C(u_0)\|_{\mathrm{HS}})$.

With the above presented results in Lemma \[lem:ensemble\_collapse\_ESRF\], Lemma \[lem:cov\_subspace\_ESRF\] and Lemma \[lem:grad\_approx\_mean\], the proof is similar to the proof of Theorem \[thm:main\].

Through the incorporation of covariance inflation we have reduced the ensemble collapse by decreasing the constant of the degeneration rate through the constant inflation parameter $(1-\rho)\in(0,1]$. Resulting from this slow down of the ensemble collapse the convergence rate of TEKI as optimization method can be accelerated by the factor $(1-\rho)$.

Numerical experiment {#sec:numerics}
====================

In our numerical experiment we consider a nonlinear inverse problem based on the one-dimensional elliptic boundary-value problem in the form of $$\label{eq:darcyflow}
\begin{split}
-\frac{{\mathrm d}}{{\rm d}s}\left(\exp(u(s))\frac{{\mathrm d}}{{\mathrm d}s}p(s)\right) &= 1,   \qquad  s\in[0,1],\\
 p(s) &= 0,  \qquad s\in\{0,1\}.
\end{split}$$ Given discrete noisy observations $y\in\mathbb R^{K}$ of the solution $p\in H_0^1([0,1];{\mathbb{R}})$ we consider the task of recovering the unknown parameter $u\in L^\infty([0,1])$. To be more precise, we consider $y = ({\mathcal{O}}\circ S)(u(s))+\eta$, where $\eta\sim{\mathcal{N}}(0,\Gamma)$ is additive Gaussian noise, $S:\ L^\infty([0,1])\to H_0^1([0,1];{\mathbb{R}})$ denotes the solution operator of and ${\mathcal{O}}:\ H_0^1([0,1];{\mathbb{R}})\to{\mathbb{R}}^{K}$ denotes the observation operator, which provides function values at $n_y$ equidistant observation points in $[0,1]$, i.e.  $z(\cdot)\in H_0^1([0,1];{\mathbb{R}})\mapsto {\mathcal{O}}(z(\cdot)) = (z(s_1),\dots,z(s_{K}))^{\top}$, $s_i = \frac{i}{K},\ i=1,\dots,K$.

For our numerical results we replace $S$ by an numerical solution operator for on the grid ${\mathcal{D}}\subset[0,1]$ with mesh size $h=2^{-8}$ and restrict $u(\cdot)$ to the computational grid $s_l = l\,h$, $l=1,\ldots,2^8-1$, i.e. we consider the finite dimensional parameter space $\mathcal X=\mathbb R^{n_x}$ with $n_x=2^8$. Our observations are taken at $K = 2^5-1$ observation points and the noise covariance is assumed to be $\Gamma = 0.01\cdot{\mathrm{Id}}\in{\mathbb{R}}^{K\times K}$.

We set a Gaussian prior $\mathcal N(0,C_0)$ on the unknown parameter with covariance operator $C_0=\beta(-\Delta)^{-1}$, $\beta = 10$. The underlying groundtruth is constructed as realization $u^\dagger\sim\mathcal N(0,C_0)$ and shown in Figure \[fig:reference\] with corresponding taken observations.

![Underlying groundtruth of the unknown parameter $u$ (left) and the corresponding (noisy) observations (right). <span data-label="fig:reference"></span>](./Numerics/nonlinear_PDE/ref_par "fig:") ![Underlying groundtruth of the unknown parameter $u$ (left) and the corresponding (noisy) observations (right). <span data-label="fig:reference"></span>](./Numerics/nonlinear_PDE/ref_obs "fig:")

We consider two types of initialization for the implementation of the TEKI flow:

-   **Basis initialization**: we choose the initial ensemble of particles based on (ordered) eigenvalues and eigenfunctions $\{\lambda_j,z_j\}_{j\in{\mathbb{N}}}$ of the covariance operator $C_0$.

-   **Random initialization**: we choose the initial ensemble of particles based on i.i.d. realizations of the Gaussian prior $\mathcal N(0,C_0)$.

The TEKI flow with covariance inflation and regularization parameter $\kappa = 0.01^2$ $$\begin{split}
\frac{{\mathrm d}u_t^{(j)}}{{\mathrm d}t} &= C^{u,G}(u_t)\Gamma^{-1}(y-G(u_t^{(j)}))-C(u_t)\kappa C_0^{-1}u_t^{(j)}\\  &\quad+ \rho C^{u,G}(u_t)\Gamma^{-1}(G(u_t^{(j)})-\bar G) +\rho C(u_t)\kappa C_0^{-1}(u_t^{(j)}-\bar u)
\end{split}$$ is tested for different choices of inflation scaling $\rho\in\{0,0.25,0.5,0.8\}$ and solved through `MATLAB` via the function `ode45` until final time $T=10^7$ with the aim of minimizing $$\Phi_R(u) =  \frac12 \|G(u)-y\|_\Gamma^2 + \frac\kappa2\|u\|_{C_0}^2,\quad u\in\mathbb R^{n_x}.$$ The reference solution $u_\ast^J$ of the constrained optimization problem depending of the ensemble size $J\in\{5,20,50\}$ is approximated with the `MATLAB` function `fmincon`. We note that $u_\ast^J$ depends on the initial ensemble and differs for basis and random initialization.

In Figure \[fig:spread\_J=50\] we show that the ensemble collapses with rate $1/t$ and illustrate the effect of the covariance inflation slowing down the collapse by a constant. This observation verifies our expectation on the behavior from the results in Lemma \[lem:ensemble\_collapse\_ESRF\] and Lemma \[lem:cov\_subspace\_ESRF\]. Here, we observe no significant difference between basis initialization and random initialization. We demonstrate our main convergence result presented in Theorem \[thm:main\] and Theorem \[thm:main2\] through Figure \[fig:Phi\_J=5\]-\[fig:Phi\_J=50\], where we observe that the lossfunctions evaluated at the particle mean converge towards the expected minimium restricted to the subspace spanned by the initial ensemble <span>spread</span>. We firstly observe, that increasing the ensemble size, the resulting minimum improves since the initial subspace increases. Secondly, we observe that the resulting estimates for basis function intialization lead to lower values in the lossfunction compared to random initialization. This behavior is expected since the basis functions are weighted through the ordered eigenvalues. Furthermore, in Figure \[fig:Phi\_diff\_J=50\] we illustrate the improved convergence through increasing variance inflation parameter $\rho$. Finally, Figure \[fig:par\_est\] shows the resulting estimators of the unknown parameter $u$ where we observe smooth estimates for basis function intialization compared to the estimates resulting from random initialization.

![Particle spread $\frac1J\sum_{j=1}^J \|e_t^{(j)}\|^2$ of the TEKI flow for basis function initialization (left) and random initialization (right) with ensemble size $J=50$.<span data-label="fig:spread_J=50"></span>](./Numerics/nonlinear_PDE/BI/spread "fig:") ![Particle spread $\frac1J\sum_{j=1}^J \|e_t^{(j)}\|^2$ of the TEKI flow for basis function initialization (left) and random initialization (right) with ensemble size $J=50$.<span data-label="fig:spread_J=50"></span>](./Numerics/nonlinear_PDE/RI/spread "fig:")

![Lossfunction $\Phi_R$ evaluated at the particle mean $\bar u_t$ of the TEKI flow for basis function initialization (left) and random initialization (right) with ensemble size $J=5$.<span data-label="fig:Phi_J=5"></span>](./Numerics/nonlinear_PDE/BI/Phi_J5 "fig:") ![Lossfunction $\Phi_R$ evaluated at the particle mean $\bar u_t$ of the TEKI flow for basis function initialization (left) and random initialization (right) with ensemble size $J=5$.<span data-label="fig:Phi_J=5"></span>](./Numerics/nonlinear_PDE/RI/Phi_J5 "fig:")

![Lossfunction $\Phi_R$ evaluated at the particle mean $\bar u_t$ of the TEKI flow for basis function initialization (left) and random initialization (right) with ensemble size $J=20$.<span data-label="fig:Phi_J=20"></span>](./Numerics/nonlinear_PDE/BI/Phi_J20 "fig:") ![Lossfunction $\Phi_R$ evaluated at the particle mean $\bar u_t$ of the TEKI flow for basis function initialization (left) and random initialization (right) with ensemble size $J=20$.<span data-label="fig:Phi_J=20"></span>](./Numerics/nonlinear_PDE/RI/Phi_J20 "fig:")

![Lossfunction $\Phi_R$ evaluated at the particle mean $\bar u_t$ of the TEKI flow for basis function initialization (left) and random initialization (right) with ensemble size $J=50$.<span data-label="fig:Phi_J=50"></span>](./Numerics/nonlinear_PDE/BI/Phi_J50 "fig:") ![Lossfunction $\Phi_R$ evaluated at the particle mean $\bar u_t$ of the TEKI flow for basis function initialization (left) and random initialization (right) with ensemble size $J=50$.<span data-label="fig:Phi_J=50"></span>](./Numerics/nonlinear_PDE/RI/Phi_J50 "fig:")

![Difference of the lossfunction $\Phi_R$ evaluated at the particle mean $\bar u_t$ the TEKI flow for basis function initialization (left) and random initialization (right) with ensemble size $J=50$ and the optimal solution restricted to the initial subspace $u_\ast^J$.<span data-label="fig:Phi_diff_J=50"></span>](./Numerics/nonlinear_PDE/BI/Phi_diff_J50 "fig:") ![Difference of the lossfunction $\Phi_R$ evaluated at the particle mean $\bar u_t$ the TEKI flow for basis function initialization (left) and random initialization (right) with ensemble size $J=50$ and the optimal solution restricted to the initial subspace $u_\ast^J$.<span data-label="fig:Phi_diff_J=50"></span>](./Numerics/nonlinear_PDE/RI/Phi_diff_J50 "fig:")

![Resulting estimates of the unknown parameter $u$ for different ensemble sizes $J\in\{5,20,50\}$ of the TEKI flow initialized by basis functions (left) and random (right). <span data-label="fig:par_est"></span>](./Numerics/nonlinear_PDE/BI/est_par "fig:") ![Resulting estimates of the unknown parameter $u$ for different ensemble sizes $J\in\{5,20,50\}$ of the TEKI flow initialized by basis functions (left) and random (right). <span data-label="fig:par_est"></span>](./Numerics/nonlinear_PDE/RI/est_par "fig:")

Conclusion {#sec:conclusion}
==========

In this work, we have quantified the EKI as derivative-free optimization method restricted to the finite dimensional subspace spanned through the initial ensemble <span>spread</span>. Our results are based on the deterministic continuous-time formulation represented by an ODE and the incorporation of Tikhonov regularization. The ensemble collapse has been quantified from above and below such that we were able to bound the approximation of gradients uniform in time and avoiding too fast degeneration of the preconditioner. We have further improved the convergence result through covariance inflation without breaking the subspace property. The considered covariance inflation can be viewed as generalization of the ESRF and gives an intuitive connection between the EKI and ESRF. In our numerical experiment we have illustrated the application of EKI as optimization method restricted to the initial subspace and specified the role of choosing the initial ensemble.

The next step for future work includes the extension of the presented results to the stochastic formulation of EKI represented as stochastic differential equation. The key challenge in this scenario will be the quantification of the ensemble collapse, since the resulting lower and upper bounds on the eigenvalues will be path-depending. In addition, a detailed complexity analysis of EKI needs to be done in order to quantify the advantage of applying EKI as derivative-free scheme compared to other commonly used optimization methods including derivatives such as gradient descent or (Quasi-)Newton method.

<span>**Acknowledgement.**</span> The author is very grateful for helpful discussions with Claudia Schillings and Jakob Zech which had an significant impact on the contribution of this work. Moreover, the author thanks Neil Chada and Claudia Schillings for carefully proofreading this manuscript.

[^1]: Universität Heidelberg, Interdisziplinäres Zentrum für Wissenschaftliches Rechnen, D-69120 Heidelberg, Germany (<span>jill90@example.org</span>)

{'source': 'arXiv_out/2203'}