On the randomised stability constant for inverse problems
Giovanni S. Alberti Yves Capdeboscq Yannick Privat






MaLGa Center, Department of Mathematics, University of Genoa, Via Dodecaneso 35,
16146 Genova, Italy.

giovanni.alberti@unige.it



Université de Paris, CNRS, Sorbonne Université, Laboratoire Jacques-Louis
Lions, UMR 7598, Paris, France

yves.capdeboscq@sorbonne-universite.fr



IRMA, Université de Strasbourg, CNRS UMR 7501, 7 rue René Descartes,
67084 Strasbourg, France

yannick.privat@unistra.fr

[2010]65J22, 35R30

In this paper we introduce the randomised stability constant for abstract
inverse problems, as a generalisation of the randomised observability
constant, which was studied in the context of observability inequalities
for the linear wave equation. We study the main properties of the
randomised stability constant and discuss the implications for the
practical inversion, which are not straightforward. 




On the randomised stability constant for inverse problems
    Yannick Privat
    December 30, 2023
=========================================================





§ INTRODUCTION


Inverse problems are the key to all experimental setups where the
physical quantity of interest is not directly observable and must
be recovered from indirect measurements. They appear in many different
contexts including medical imaging, non-destructive testing, seismic
imaging or signal processing. In mathematical terms, an inverse problem
consists in the inversion of a linear or nonlinear map 

    T X→ Y,     x↦ T(x),

which models how the quantity of interest x belonging to a space
X is related to the measurements y=T(x) in the space Y. The
reader is referred to the many books on inverse problems for a comprehensive
exposition (see, e.g., <cit.>).

Inverse problems can be ill-posed: the map T may not be injective
(i.e., two different x_1 and x_2 may correspond to the same
measurement T(x_1)=T(x_2)) or, when injective, T^-1 T⊆ Y→ X
may not be continuous (i.e., two different and not close x_1
and x_2 may correspond to almost identical measurements T(x_1)≈ T(x_2)).
Various strategies have been introduced to tackle the issue of inversion
in this setting, Tykhonov regularisation being the most famous method
<cit.>.

Our purpose is to investigate the role of randomisation in the resolution
of inverse problems. By randomisation, we refer to the use of random
measurements, or to the case of random unknowns. We do not mean the
well-established statistical approaches in inverse problems, as in
the Bayesian framework, where probability is used to assess the reliability
of the reconstruction.

Even with this distinction, the wording “randomisation” may refer
to many different concepts in the framework of inverse problems. A
huge literature is devoted to the issue of randomisation in the measuring
process: the unknown x in X is fixed and deterministic, and
we choose the measurements randomly according to some suitable distribution.
For example, compressed sensing <cit.> and passive imaging with
ambient noise <cit.> belong to this class. Another very
popular idea consists in randomising the unknown: in this scenario,
we try to recover most unknowns x in X, according to
some distribution. For example, this is typically the situation when
deep learning <cit.> is applied to inverse
problems. We briefly review these instances in Appendix <ref>.

This article deals with a more recent approach, in the framework of
observability or control theory: the so-called randomised observability
constants <cit.>. We argue that, in contrast
with the initial motivation for its introduction, the randomised observability
constant is not necessarily indicative of the likelihood for randomised
unknowns to be observable.

In the next section, we recall the notion of randomised observability
constant and comment on its use in optimal design problems. In section <ref>,
we reformulate the randomised observability constant in an abstract
setting as randomised stability constant. In section <ref>
we show that when the classical (deterministic) stability constant
is null, a positive randomised stability constant need not imply,
as one could hope, that the inverse problem can be solved for most
unknowns. In the course of our study, we make several observations
on the properties of the randomised stability constant. Section <ref>
contains several concluding remarks and discusses possible future
directions.



§ RANDOMISING INITIAL DATA OF PDES


In this section we briefly review the randomised observability constant
introduced in <cit.> and its main properties.
This was motivated by the original idea of randomisation by Paley
and Zygmund, which we now briefly discuss.



 §.§ On randomisation processes


 In order to understand the principle of randomisation
that will be at the core of this paper, it is useful to recall the
historical result by Paley and Zygmund on Fourier series. Let (c_n)_n∈
be an element of ℓ^2() and f be the Fourier series given
by 

    f:∋θ↦∑_n∈c_ne^inθ,

where  denotes the torus /(2π). According to the so-called
Parseval identity, the function f belongs to L^2(); furthermore,
the coefficients c_n can be chosen in such a way that f does
not belong to any L^q() for q>2. Some of the results obtained
by Paley and Zygmund (see <cit.>)
address the regularity of the Fourier series f. They show that
if one changes randomly and independently the signs of the Fourier
coefficients c_n, then the resulting random Fourier series belongs
almost surely to any L^q() for q>2. More precisely, introducing
a sequence (β_n^ν)_n∈ of independent Bernoulli
random variables on a probability space (A,𝒜,P)
such that 

    P(β_n^ν=±1)=1/2,

then, the Fourier series f^ν given by 

    f^ν:∋θ↦∑_n∈β_n^νc_ne^inθ

belongs almost surely to L^q() for all q<+∞.

In <cit.>, the effect of the randomisation on the initial
data of solutions to dispersive equations has been investigated. In
that case, initial data and solutions of the PDE considered are expanded
in a Hilbert basis of L^2(Ω) made of eigenfunctions (ϕ_j)_j≥1
of the Laplace operator. The randomisation procedure consists hence
in multiplying all the terms of the series decomposition by well-chosen
independent random variables. In particular, regarding for instance
the homogeneous wave equation with Dirichlet boundary conditions,
one can show that for all initial data (y^0,y^1)∈ H_0^1(Ω)× L^2(Ω),
the Bernoulli randomisation keeps the H_0^1× L^2 norm
constant. It is observed that many other choices of randomisation
are possible. For instance a positive effect of the randomisation
can be observed by considering independent centred Gaussian random
variables with variance 1 (Gaussian randomisation). Indeed, it allows
to generate a dense subset of the space of initial data H_0^1(Ω)× L^2(Ω)
through the mapping 

    R_(y^0,y^1) A→ H_0^1(Ω)× L^2(Ω),    ν↦(y_ν^0,y_ν^1),

where 
(y_ν^0,y_ν^1) denotes the pair of randomised initial
data, provided that all the coefficients in the series expansion of
(y^0,y^1) are nonzero. Several other properties of these randomisation
procedures are also established in <cit.>.



 §.§ Randomised observability constant 


We now review how randomisation appeared in the framework of inverse
problems involving an observability inequality. The property of observability
of a system is related to the following issue: how to recover the
solutions of a PDE from the knowledge of partial measurements of the
solutions. In what follows, we will concentrate on wave models, having
in particular photoacoustic/thermoacoustic tomography imaging in mind.

Let T>0 and Ω⊆^d be a bounded Lipschitz domain
with outer unit normal . We consider the homogeneous wave equation
with Dirichlet boundary conditions 

    {[ ∂_tty(t,x)-Δ y(t,x)=0        (t,x)∈[0,T]×Ω,;              y(t,x)=0       (t,x)∈[0,T]×∂Ω. ].

It is well known that, for all (y^0,y^1)∈ H_0^1(Ω)× L^2(Ω),
there exists a unique solution y∈ C^0([0,T],H_0^1(Ω))∩ C^1((0,T),L^2(Ω))
of (<ref>) such that y(0,x)=y^0(x) and ∂_ty(0,x)=y^1(x)
for almost every x∈Ω. Let Γ be a measurable subset
of ∂Ω, representing the domain occupied by some sensors,
which take some measurements over a time horizon [0,T].

The inverse problem under consideration reads as follows. 

 Inverse problem: reconstruct the initial condition
(y^0,y^1) from the knowledge of the partial boundary measurements

    _Γ(x)∂ y/∂(t,x),    (t,x)∈[0,T]×∂Ω.


To solve this problem, we introduce the so-called observability
constant: C_T(Γ) is defined as the largest non-negative
constant C such that 

    C‖(y(0,·),∂_ty(0,·))‖_H_0^1(Ω)× L^2(Ω)^2≤∫_0^T∫_Γ|∂ y/∂(t,x)|^2 d dt,

for any solution y of (<ref>), where H_0^1(Ω)
is equipped with the norm u_H_0^1(Ω)=∇ u_L^2(Ω).
Then, the aforementioned inverse problem is well-posed if and only
if C_T(Γ)>0. In such a case, we will say that observability
holds true in time T. Moreover, observability holds true within
the class of 𝒞^∞ domains Ω if (Γ,T)
satisfies the Geometric Control Condition (GCC) (see <cit.>),
and this sufficient condition is almost necessary.

Let us express the observability constant more explicitly. Fix an
orthonormal basis (ONB) (ϕ_j)_j≥1 of L^2(Ω)
consisting of (real-valued) eigenfunctions of the Dirichlet-Laplacian
operator on Ω, associated with the negative eigenvalues (-λ_j^2)_j≥1.
Then, any solution y of (<ref>) can be expanded as 

    y(t,x)=∑_j=1^+∞y_j(t)ϕ_j(x)=1/√(2)∑_j=1^+∞(a_j/λ_je^iλ_jt+b_j/λ_je^-iλ_jt)ϕ_j(x),

where the coefficients a_j and b_j account for initial data.
More precisely, we consider the ONB of H_0^1(Ω)× L^2(Ω)
given by {ψ_j^+,ψ_j^-:j≥1}, where 

    ψ_j^+=1/√(2)(ϕ_j/λ_j,iϕ_j),    ψ_j^-=1/√(2)(ϕ_j/λ_j,-iϕ_j).

Expanding now the initial data with respect to this basis we can write
(y^0,y^1)=∑_j=1^+∞a_jψ_j^++b_jψ_j^-,
namely, 

    y^0=∑_j=1^+∞a_j+b_j/√(2) λ_j ϕ_j,     y^1=∑_j=1^+∞ia_j-b_j/√(2) ϕ_j.

The corresponding solution to (<ref>) is given by (<ref>).
In addition, Parseval's identity yields (y^0,y^1)_H_0^1(Ω)× L^2(Ω)^2=∑_j=1^+∞|a_j|^2+|b_j|^2.

Then, the constant C_T(Γ) rewrites 

    C_T(Γ)     =inf_(a_j),(b_j)∈ℓ^2(C)
    ∑_j=1^+∞(|a_j|^2+|b_j|^2)=1
    ∫_0^T∫_Γ|∂ y/∂(t,x)|^2 d dt,

where y(t,x) is given by (<ref>).



The constant C_T(Γ) is deterministic and takes into
account any (a_j),(b_j)∈ℓ^2(C), including the
worst possible cases. Interpreting C_T(Γ) as a quantitative
measure of the well-posed character of the aforementioned inverse
problem, one could expect that such worst cases do not occur too often;
thus it would appear desirable to consider a notion of observation
in average.

Motivated by the findings of Paley and Zygmund (see <ref>)
and its recent use in another context <cit.>,
making a random selection of all possible initial data for the wave
equation (<ref>) consists in replacing C_T(Γ)
with the so-called randomised observability constant defined
by 

    C_T,rand(Γ)=inf_(a_j),(b_j)∈ℓ^2(C)
    ∑_j=1^+∞(|a_j|^2+|b_j|^2)=1
    E(∫_0^T∫_Γ|∂ y^ν/∂(t,x)|^2d dt),

where 

    y^ν(t,x)=1/√(2)∑_j=1^+∞(β_1,j^νa_j/λ_je^iλ_jt+β_2,j^νb_j/λ_je^-iλ_jt)ϕ_j(x)

and (β_1,j^ν)_j∈ and (β_2,j^ν)_j∈
are two sequences of independent random variables of Bernoulli or
Gaussian type, on a probability space (A,𝒜,P)
with mean 0 and variance 1. Here, E is the expectation
in the probability space, and runs over all possible events ν.
In other words, we are randomising the Fourier coefficients {a_j,b_j}_j≥1
of the initial data (y^0,y^1) with respect to the basis {ψ_j^±}_j≥1.

The randomised observability constant was introduced in <cit.>. It can be expressed in terms of
deterministic quantities (see <cit.>). 

 Let Γ⊂∂Ω be measurable.
We have 

    C_T,rand(Γ)=T/2inf_j∈1/λ_j^2∫_Γ(∂ϕ_j/∂(x))^2 d.

 



In view of Lemma <ref> (see below), we have that 

    C_T,rand(Γ)=inf{_Γ∂_y_j^+_L^2([0,T]×∂Ω)^2,_Γ∂_y_j^-_L^2([0,T]×∂Ω)^2:j≥1},

where y_j^± is the solution to (<ref>) with initial
condition ψ_j^±. Thus 

    y_j^±(t,x)=1/√(2) λ_je^± iλ_jtϕ_j(x),

and in turn 

    _Γ∂_y_j^±_L^2([0,T]×∂Ω)^2=1/2λ_j^2∫_[0,T]×Γ|e^± iλ_jt∂_ϕ_j(x)|^2 dtdx,

which leads to our thesis. 

We have C_T,rand(Γ)≥ C_T(Γ) (see Proposition <ref>
below). It has been noted in <cit.> that the observability
inequality defining C_T,rand(Γ) is associated to
a deterministic control problem for the wave equation (<ref>),
where the control has a particular form but acts in the whole domain
Ω.

Regarding C_T,rand(Γ), we refer to <cit.>
for a discussion on the positivity of this constant. The authors show
that if Ω is either a hypercube or a disk, then C_T,rand(Γ)>0
for every relatively non-empty open subset Γ of ∂Ω.
In particular, in some cases C_T(Γ)=0 while C_T,rand(Γ)>0.
This raised hopes that, even if recovering all unknowns is
an unstable process, recovering most unknowns could be feasible,
since apparently most unknowns are observable. This heuristic argument,
mentioned amongst the motivations for the study of the optimisation
of the randomised observability constant, was not investigated further
in the aforementioned papers. This matter will be studied in the
following sections, dedicated more generally on the possible use of such a constant for investigating the well-posed character of general inverse problems.



  §.§.§ Applications to optimal design problems


A larger observability constant C_T(Γ) in (<ref>)
leads to a smaller Lipschitz norm bound of the inverse map. Therefore
C_T(Γ) can be used as the quantity to maximise when searching
for optimal sensors' positions. However, this turns out to be somewhat
impractical. When implementing a reconstruction process, one has to
carry out in general a very large number of measures; likewise, when
implementing a control procedure, the control strategy is expected
to be efficient in general, but possibly not for all cases. Thus,
one aims at exhibiting an observation domain designed to be the best
possible in average, that is, over a large number of experiments.
Adopting this point of view, it appeared relevant to consider an average
over random initial data. In <cit.>, the
best observation is modelled in terms of maximising a randomised
observability constant, which coincides with C_T,rand(Γ)
when dealing with the boundary observation of the wave equation.

When dealing with internal observation of the wave equation on a closed
manifold, it has been shown in <cit.> that the related observability
constant reads as the minimum of two quantities: the infimum of the
randomised observability constants over every orthonormal eigenbasis
and a purely geometric criterion standing for the minimal average
time spent by a geodesic in the observation set.

However, one should keep in mind that a large randomised constant
may not be associated with a reconstruction method (see section <ref>).



§ THE RANDOMISED STABILITY CONSTANT FOR ABSTRACT INVERSE PROBLEMS


It is convenient to generalise the construction of the previous section
to an abstract setting. In what follows, none of the arguments require
the precise form of the forward operator related to the wave equation,
as they rely solely on the structure of the randomised constant.

For the remainder of this paper, we let X and Y be separable
infinite-dimensional Hilbert Spaces, and P X→ Y be an injective
bounded linear operator.

If P^-1ranP→ X is a bounded operator,
the inverse problem of finding x from P(x) can be solved in
a stable way for all x∈ X, without the need for randomisation.
This can be measured quantitatively by the constant 

    =inf_x∈ X∖{ 0}‖ Px‖ _Y^2/‖ x‖ _X^2>0.

The smaller  is, the more ill-conditioned the inversion becomes.

On the other hand, when P^-1 is unbounded, the situation is different,
and the inverse problem is ill-posed <cit.>.
In this case, although the kernel of P reduces to {0}, we
have 

    =inf_x∈ X∖{ 0}‖ Px‖ _Y^2/‖ x‖ _X^2=0.


Examples of such maps abound. The example that motivated our study
was that introduced in section <ref>, with X=H_0^1(Ω)× L^2(Ω),
Y=L^2([0,T]×∂Ω) and 

    P(y^0,y^1)=y|_[0,T]×Γ,

where Γ⊆∂Ω and y is the solution to
(<ref>) with initial condition (y^0,y^1): if Γ
is not large enough, P is still injective but P^-1 is unbounded
<cit.>. Any injective compact linear operator
satisfies (<ref>).

Let us now introduce the randomised stability constant, which
generalises the randomised observability constant to this general
setting. We consider the class of random variables introduced in the
last section. Choose an ONB ={_k}_k∈ of X and
write x=∑_k=1^∞x_k_k∈ X. We consider random
variables of the form 

    x^ν=∑_k=1^∞β_k^νx_k_k,

where β_k^ν are i.i.d. complex-valued random variables
on a probability space (A,𝒜,P) with vanishing
mean and variance 1, so that E(|β_k^ν|^2)=1 for every k. These include the Bernoulli and Gaussian
random variables considered in the previous section. It is worth observing that, in the case of Bernoulli random variables, we have |β_k^ν|^2=1 for every k, so that
x^ν_X=x_X.

The randomised stability constant is defined
as 

    =inf_x∈ X∖{ 0}E(‖ P(x^ν)‖ _Y^2/‖ x‖ _X^2).

 


As in the previous section, this constant should represent stability
of the inverse problem for most unknowns. By definition,
we have ≥. In general, this is a strict inequality:
we will provide examples in section <ref>. This can
be heuristically seen also by the following deterministic expression
for the randomised stability constant.

There holds 

    =inf_k‖ P(_k)‖ _Y^2.




Since (Y,‖·‖ _Y) is also a
Hilbert space, we find 

    ‖ P(x^ν)‖ _Y^2    =⟨∑_k=1^∞β_k^νx_k P(_k),∑_l=1^∞β_l^νx_lP(_k)⟩ _Y
        =∑_k=1^∞|β_k^ν|^2 |x_k|^2‖ P(e_k)‖ _Y^2+∑_k,l
    
    k≠ l
    β_k^νβ_l^νx_kx_l⟨ P(_k),P(_k)⟩_Y.

Since β_k^ν are i.i.d. with vanishing
mean and such that E(|β_k^ν|^2)=1, we obtain 


    E(‖ P(x^ν)‖ _Y^2/‖ x‖ _X^2)=E(‖ P(x^ν)‖ _Y^2)/∑_k=1^∞|x_k|^2=∑_k=1^∞|x_k|^2‖ P(_k)‖ _Y^2/∑_k=1^∞|x_k|^2≥inf_k‖ P(_k)‖ _Y^2,

which means ≥inf_k‖ P(_k)‖ _Y^2.
Choosing x=_k, we obtain (<ref>). 




§ EXPLOITING C_RAND IN INVERSE PROBLEMS 


The aim of this section is to discuss the impact of the randomised
observability constant in inverse problems. In other words, we would
like to address the following question: how can the positivity of
C_rand be exploited in the solution of an inverse ill-posed
problem? We will not fully address this issue, but rather provide
a few positive and negative partial results.

We remind the reader that the randomisation introduced in the last
section when (<ref>) holds, was based on the point
of view that the ratio in (<ref>) is not “usually”
small, and that, hopefully, in most cases inversion “should” be
possible. It is worthwhile to observe that the subset of the x∈ X
such that ‖ Px‖ _Y≥ c‖ x‖ _X
for some fixed c>0 is never generic in X, since { x∈ X:‖ Px‖ _Y<c‖ x‖ _X}
is open and non empty by (<ref>). This caveat in mind,
we nevertheless wish to test if some evidence can be given to support
our optimistic approach that in most cases, inversion should be possible.

 For every ϵ>0 and x∈ X,
there exists c>0 such that 

    P(‖ Px^ν‖ _Y≥ c‖ x‖ _X)>1-ϵ.

 



Take x∈ X. Define the real-valued map g(c)=P(‖ Px^ν‖ _Y≥ c‖ x‖ _X).
Take a sequence c_n↘0. It is enough to show that 

    lim_n→+∞g(c_n)=1.


We write 

    g(c_n)=∫_Af_n(ν)dP(ν), where f_n(ν)=
    1    if ,
    
    0    otherwise.

Note that f_n is monotone increasing and, since P={ 0},
lim_n→∞f_n(ν)=1 for every ν. Thus by the Monotone
Convergence Theorem, 

    lim_n→∞∫_Af_n(ν)dP(ν)=∫_A(lim_n→∞f_n(ν))dP(ν)=1.


This thus shows that, for a fixed x, our intuition is vindicated:
in the vast majority of cases, the inequality ‖ Px^ν‖ _Y≥ c‖ x‖ _X
holds true. This is true independently of ; we now investigate whether the positivity of  may yield a stronger estimate.



 §.§ Large deviation inequalities


The next step is to estimate the probability that, for a given x∈ X∖{0},
the square of the ratio ‖ P(x^ν)‖ _Y/‖ x‖ _X
used in Definition <ref> is close to its mean value. The
large deviation result we could derive describes the deviation from
an upper bound to , namely the constant  defined
by 

    =sup_kP(_k)_Y^2.



 Assume that Y=L^2(Σ,μ), where (Σ,S,μ)
is a measure space. Let (β_k^ν)_k∈ be a sequence
of independent random variables of Bernoulli type, on a probability
space (A,𝒜,P) with mean 0 and variance 1. Let
x∈ X∖{0} and x^ν=∑_k=1^∞β_k^ν_kx_k.
Then, for every δ>0 we have 

    P(‖ Px^ν‖_Y≥δ‖ x^ν‖ _X)≤exp(2-1/eδ/√()).



The proof of Theorem <ref> is postponed to Appendix <ref>.
The argument follows the same lines as the one of <cit.>
and the general method introduced in <cit.>.

 Considering the wave equation (<ref>)
and adopting the framework of section <ref> leads
to choose {ψ_j^±}_j≥1 defined by (<ref>)
as the orthonormal basis e. In that case, X=H_0^1(Ω)× L^2(Ω),
Σ=[0,T]×∂Ω, dμ=dt d and Y=L^2(Σ).
Following the discussion in section <ref>, the
map P is given by P(y^0,y^1)=_Γ∂ y/∂,
where y is the unique solution of (<ref>). Further,
we have 

    =T/2inf_j∈1/λ_j^2∫_Γ(∂ϕ_j/∂)^2 d,
    
    K_rand(e)     =T/2sup_j∈1/λ_j^2∫_Γ(∂ϕ_j/∂)^2 d,

where the first equality is given in Proposition <ref>,
and the second one follows by applying the same argument.

Note that according to the so-called Rellich identity[This identity, discovered by Rellich in 1940 <cit.>, reads

    2λ^2=∫_∂Ω⟨ x,ν⟩(∂ϕ/∂)^2 d

for every eigenpair (λ,ϕ) of the Laplacian-Dirichlet operator,
Ω being a bounded connected domain of ^n either convex
or with a C^1,1 boundary. ], we have 0<K_rand(e)≤T/2diam(Ω),
under additional mild assumptions on the domain Ω. 


The estimate given in Theorem <ref> is on the “wrong side”,
since we show that the ratio related to the inversion is much bigger
than  with low probability. The issue
is not the boundedness of P, which is given a priori, but of its inverse. This would correspond to a result of the type 

    P(P(x^ν)_Y^2/x_X^2<-δ)≤small constant,

namely, a quantification of the estimate given in Proposition <ref>,
uniform in x. If such a bound held, it would show that 
is a reliable estimator of the behaviour of the ratio P(x)_Y^2/x_X^2
in general. Notice that, in the favourable case when P^-1 is  bounded, there exists δ_0∈ [0,) such that

    P(P(x^ν)_Y^2/x_X^2<-δ)=0

for all δ∈ [δ_0,).



In this general framework, estimate (<ref>) does not hold,
see Example <ref>. Using a concentration inequality, a weaker
bound can be derived. 

 Assume that Y=L^2(Σ,μ), where (Σ,S,μ)
is a measure space. Let (β_k^ν)_k∈ be a sequence
of independent random variables of Bernoulli type, on a probability
space (A,𝒜,P) with mean 0 and variance 1. Let
x∈ X∖{0} and x^ν=∑_k=1^∞β_k^ν_kx_k.
Then, for every δ>0 we have 

    ℙ(P(x^ν)_Y^2/x_X^2-𝔼(‖ P(x^ν)‖ _Y^2/‖ x‖ _X^2)<-δ)<exp(-δ^2/4^2).

 


This result is based on an appropriate Hoeffding inequality; its proof
is postponed to Appendix <ref>. Note that (<ref>)
is not a large deviation result: the quantity under consideration
is bounded between 0 and 1, and the upper bound obtained is not small.
This is unavoidable, see Example <ref>.



 §.§ Can you reconstruct two numbers from their sum?


We collect here several observations that suggest that the positivity
of the randomised stability constant may not be helpful for solving
the inverse problems, not even for most unknowns.



  §.§.§ Instability arises for every x∈ X


We remind the reader why (<ref>) renders inversion
unstable. Hypothesis (<ref>) implies that there exists
a sequence (x_n)_n∈ such that 

    ‖ x_n‖ _X=1 and ‖ Px_n‖ _Y<1/n for all n∈.

Suppose that our measurements are not perfect, and are affected by
a low level of noise δ, ‖δ‖ _Y≤ϵ,
with ϵ>0. Then, for every n such that nϵ>1,
we have 

    ‖ P(x+x_n)-P(x)‖ _Y<ϵ,

hence x and x+x_n correspond to the same measured data, even
if ‖(x+x_n)-x‖ _X=1. This is
an unavoidable consequence of the unboundedness of P^-1, and
is true for every x∈ X, even if the randomised stability constant
were positive (and possibly large).



  §.§.§ The dependence of C_rand on the basis


Lemma <ref> shows that the ONB used to randomise our
input plays a role, as it appears explicitly in the formula (<ref>).
The following proposition underscores that point. Namely, if we consider
all possible randomisations with respect to all ONB of X we recover
the deterministic stability constant . 

 We have 

    inf_=,

where the infimum is taken over all ONB of X. In particular, if
P^-1 is unbounded then inf_=0. 



By definition of , we have that ≥ for every
ONB , and so it remains to prove that 

    inf_≤.

By definition of , we can find a sequence x_n∈ X such
that x_n_X=1 for every n and Px_n_Y^2→.
For every n, complete x_n to an ONB of X, which we call ^(n).
By Lemma <ref> we have C_rand(^(n))≤Px_n_Y^2,
and so 

    inf_≤inf_nC_rand(^(n))≤inf_nPx_n_Y^2≤lim_n→+∞Px_n_Y^2=.


This result shows that, in general, the randomised stability constant
strongly depends on the choice of the basis. There will always be
bases for which it becomes arbitrarily small when P^-1 is unbounded.

It is also worth observing that for compact operators, which arise
frequently in inverse problems, the randomised stability constant
is always zero.

 If P is compact then C_rand(e)=0
for every ONB e of X. 



Since e_k tends to zero weakly in X, by the compactness
of P we deduce that P(e_k) tends to zero strongly
in Y. Thus, by Lemma <ref> we have 

    =inf_k‖ P(_k)‖ _Y^2≤lim_k→+∞‖ P(_k)‖ _Y^2=0,

as desired. 




  §.§.§ Examples


Let us now consider some examples. The first example is finite dimensional
and the kernel of the operator is not trivial. Note that the definition
of  and all results above, except Proposition <ref>
and Lemma <ref>, are valid also in this case, with
suitable changes due to the finiteness of the ONB.

 Choose X=R^2 and Y=R, and
consider the map 

    SR^2   →R
    (x,y)    ↦ x+y.

The associated inverse problem can be phrased: find the two numbers
whose sum is given. This problem is ill-posed and impossible to solve.
The deterministic stability constant vanishes 

    inf_(x_1,x_2)∈R^2∖{(0,0)}|x_1+x_2|^2/x_1^2+x_2^2=0,

and S^-1 does not exist. However, the randomised constant obtained
using the canonical basis is positive. Indeed, |P(1,0)|=|P(0,1)|=1,
therefore 

    C_rand({(1,0),(0,1)})=inf{1,1}=1.

The positivity of this constant does not imply the existence of any
useful method to perform the reconstruction of x and y from
x+y, even for most (x,y)∈^2.

Had we chosen as orthonormal vectors 1/√(2)(1,1)
and 1/√(2)(1,-1) , since |P(1,-1)|=0,
we would have found 

    C_rand(1/√(2)(1,1),1/√(2)(1,-1))=0.



One may wonder whether the features highlighted above are due to the
fact that the kernel is not trivial. That is not the case, as the
following infinite-dimensional generalisation with trivial kernel
shows.

 Consider the case when X=Y=ℓ^2, equipped with
the canonical euclidean norm. Let e={e_k}_k=0^+∞
denote the canonical ONB of ℓ^2. Take a sequence (η_n)_n∈_0
such that η_n>0 for all n, and lim_n→∞η_n=0.
We consider the operator P defined by 

    P(_2n)=_2n+_2n+1,     P(_2n+1)=_2n+(1+η_n)_2n+1.

The operator P may be represented with respect to the canonical
basis  by the block-diagonal matrix 

    P=[     1     1     0     0     ⋯;     1 1+η_0     0     0     ⋯;     0     0     1     1     ⋯;     0     0     1 1+η_1     ⋯;     ⋮     ⋮     ⋮     ⋮     ⋱ ].

In other words, P may be expressed as 

    P(x)=(x_0+x_1,x_0+(1+η_0)x_1,x_2+x_3,x_2+(1+η_1)x_3,…),     x∈ℓ^2.


We note that T={ 0} and that its inverse is
given by 

    P^-1(y)=((1+η_0^-1)y_0-η_0^-1y_1,η_0^-1(y_1-y_0),(1+η_1^-1)y_2-η_1^-1y_3,η_1^-1(y_3-y_2),…),

which is an unbounded operator since η_n^-1→+∞. Given
the block diagonal structure of this map, the inversion consists of
solving countably many inverse problems (i.e., linear systems) of
the form 

    {[          x_2n+x_2n+1=y_2n,; x_2n+(1+η_n)x_2n+1=y_2n+1. ].

As soon as ñ is such that η_ñ becomes smaller
than the noise level, all the following inverse problems for n≥ñ
are impossible to be solved, since they reduce to the “sum of two
numbers” discussed in Example <ref>.

Note that 

    P(_2n)_2^2=2,    P(_2n+1)_2^2=1+(1+η_n)^2,

therefore 

    =2.

If we choose instead the rotated orthonormal basis, 

    v_2n=1/√(2)(_2n+_2n+1),   v_2n+1=1/√(2)(_2n-_2n+1),

then P(v_2n+1)=-η_n1/√(2)_2n+1,
and so 

    C_rand({v_k}_k)=inf_kP(v_k)_2^2≤lim_n→∞P(v_2n+1)_2^2=0.


We now turn to (<ref>) and (<ref>). For some k≥0,
consider x=_2k. Then P(x^ν)=β_2k^ν(_2k+_2k+1)
and therefore P(x^ν)_Y=P(x)_Y: there is no deviation
as 

    P(x^ν)_Y^2/x_X^2=𝔼(P(x^ν)_Y^2/x_X^2)==2.

Thus, the probabilities in (<ref>) and (<ref>)
are equal to 0, and the inequalities are trivial.

However, alternatively, consider x=_2k+_2k+1. Then P(x^ν)_Y^2=4+(2+η_2k)^2
if β_1^νβ_2^ν=1 and P(x^ν)_Y^2=η_2k^2
if β_1^νβ_2^ν=-1. Therefore 

    P(x^ν)_Y^2/x_X^2-=(2+η_2k)^2/2   with probability ,
    η_2k^2/2-2    with probability .

As a consequence, (<ref>) cannot be true in general for
every x. Similarly, we have 

    P(x^ν)_Y^2/x_X^2-E(P(x^ν)_Y^2/x_X^2)=
    2+η_2k   with probability ,
    
    -2-η_2k   with probability ,

and the left-hand side of (<ref>) can indeed be large for
some x.


It is worth observing that a very similar example is considered in
<cit.> to show that particular complications may arise
when using neural networks for solving some inverse problems, even
naive and small scale (cfr. <ref>).

These examples show that considering the observability constant for
a particular basis sheds little light on a potential stable inversion
of the problem in average, and that considering all possible randomisations
leads to the same conclusion as the deterministic case (confirming
Proposition <ref>).



 §.§ Linear versus nonlinear problems


The pitfalls we encountered when we tried to make use of the randomised
stability constant all stem from the linearity of the problems we
are considering. The seminal work of Burq and Tzvetkov <cit.>,
which showed existence of solutions in super-critical regimes for
a semilinear problem did not involve tinkering with associated linear
operator (the wave equation); it is the nonlinearity that controlled
the critical threshold. In both compressed sensing and passive imaging
with random noise sources, nonlinearity plays a key role; further,
deep networks are nonlinear maps (cfr. Appendix <ref>).

The naive intuition we discussed earlier, namely, that extreme situations
do not occur often, is more plausible for nonlinear maps where pathological
behaviour is local. 

As a toy finite-dimensional example, consider the map 

    T→,     T(x)=x(x-ϵ)(x+ϵ),

for some small ϵ>0. Then T can be stably inverted outside
of a region with size of order ϵ, since there the inverse
is continuous. Thus, a random initial data has little chance of falling
precisely in the problematic region. Such a case cannot happen with
linear maps. 



Let A H→ H be an unbounded linear operator on a Hilbert
space with compact resolvent, so that the spectrum of A is discrete.
Define the nonlinear map 

    T H×[0,1]→ H×[0,1],     T(x,λ)=(Ax+λ x,λ).

Note that A+λ I is invertible with probability 1 if λ
is chosen uniformly in [0,1]. Thus, if H×[0,1] is equipped
with a product probability measure whose factor on [0,1] is the
uniform probability, then x may be reconstructed from T(x) with
probability 1.





§ CONCLUDING REMARKS


In this paper we focused on the randomised stability constant for
linear inverse problems, which we introduced as a generalisation of
the randomised observability constant.

We argue that, despite its intuitive and simple definition, the randomised
stability constant has no implications in the practical solution of
inverse problems, even for most unknowns. As the examples provided
show, this may be due to the linearity of the problem. With nonlinear
problems, the situation is expected to be completely different. It
could be that the randomised stability constant is meaningful in the
context of a nonlinear inversion process, involving for example a
hierarchical decomposition <cit.>,
but we do not know of results in that direction: this is left for
future research.

plain







§ EXAMPLES OF TECHNIQUES BASED ON RANDOMISATION




In this appendix we briefly review three different techniques for
solving inverse problems where randomisation plays a crucial role.
We do not aim at providing an exhaustive overview, or at reporting
on the most recent advances, or at discussing the many variants that
have been studied. The examples we present are used to contrast possible
different approaches, and the level of mathematical understanding
associated with them.



 §.§ Compressed sensing


Since the seminal works <cit.>, compressed sensing
(CS) has provided a theoretical and numerical framework to overcome
Nyqvist criterion in sampling theory for the reconstruction of sparse
signals. In other words, sparse signals in ^n may be reconstructed
from k discrete Fourier measurements, with k smaller than n
and directly proportional to the sparsity of the signal (up to log
factors, see eqn. (<ref>) below). Let us give a quick overview
of the main aspects of CS, in order to show how it fits in the general
framework of section <ref>. For additional details, the
reader is referred to the book <cit.>, and to the references therein.

Given s∈={1,2,…}, let X be the set of s-sparse
signals in ^n, namely 

    X={x∈^n:# x≤ s}.

Let F^n→^n denote the discrete Fourier transform.
In fact, any unitary map may be considered, by means of the notion
of incoherence <cit.>. In any case, the Fourier transform
is a key example for the applications to Magnetic Resonance Imaging
and Computerised Tomography (via the Fourier Slice Theorem). In order
to subsample the Fourier measurements, we consider subsets S_a
of cardinality k of {1,2,…,n} and parametrise them with
a∈{1,2,…,nk}. Let Y=^k and P_a^n→^k
be the projection selecting the entries corresponding to S_a.
We then define the measurement map 

    T_a=P_a∘ F X→^k.

In other words, T_a is the partial Fourier transform, since only
the frequencies in S_a are measured, and #S_a=k≤ n.

Given an unknown signal x_0∈ X, we need to reconstruct it from
the partial knowledge of its Fourier measurements represented by y:=T_a(x_0).
The sparsity of x_0 has to play a crucial role in the reconstruction,
since as soon as k<n the map P_a∘ F^n→^k
necessarily has a non-trivial kernel. It is worth observing that sparsity
is a nonlinear condition: if X were a linear subspace of ^n,
the problem would be either trivial or impossible, depending on (P_a∘ F)∩ X.
Thus nonlinearity plays a crucial role here.

The simplest reconstruction algorithm is to look for the sparsest
solution to T_ax=y, namely to solve the minimisation problem

    min_x∈^nx_0  subject to ,

where x_0=# x. However, this problem is NP complex,
and its direct resolution impractical. Considering the convex relaxation
·_1 of ·_0 leads to a well-defined minimisation
problem 

    min_x∈^nx_1  subject to ,

whose solution may be easily found by convex optimisation (in fact,
by linear programming).

The theory of CS guarantees exact reconstruction. More precisely,
if x̃ is a minimiser of (<ref>), then x̃=x_0
with high probability, provided that 

    k≥ Cslog n,

and that a is chosen uniformly at random in {1,2,…,nk}
(namely, the subset S_a is chosen uniformly at random among all
the subsets of cardinality k of {1,2,…,n}) <cit.>.
In addition, in the noisy case, with measurements of the form y=T_a(x_0)+η
where η_2≤ϵ, by relaxing the equality “T_ax=y”
to the inequality “T_ax-y_2≤ϵ” in (<ref>),
one obtains the linear convergence rate x_0-x̃_2≤ Cϵ,
namely, the solution is stable.

In summary, CS allows for the stable reconstruction of all
sparse signals from partial Fourier measurements, for most
choices of the measured frequencies. The corresponding forward map
T_a X→^k is nonlinear, simply because X
is not a vector space.



 §.§ Passive imaging with random noise sources


The material presented in this part is taken from <cit.>,
to which the reader is referred for more detailed discussion on this
topic.

A typical multistatic imaging problem is the recovery of some properties
of a medium with velocity of propagation c(x)>0 from some measurements
at locations x_j∈^3 of the solution u(t,x) of the wave
equation 

    ∂_t^2u(t,x)-c(x)^2Δ u(t,x)=f(t)δ(x-y),    (t,x)∈×^3,

where f(t) is the source pulse located at y. One of the major
applications of this setup is geophysical imaging, where one wants
to recover properties of the structure of the earth from measurements
taken on the surface. Generating sources in this context is expensive
and disruptive. Earthquakes are often used as sources, but they are
rare and isolated events. Yet, noisy signals, as they may be recorded
by seismographers, even if low in amplitude, may be relevant and useful
even in absence of important events.

The key idea is to consider the data generated by random sources (e.g.,
in seismology, those related to the waves of the sea). The equation
becomes 

    ∂_t^2u(t,x)-c(x)^2Δ u(t,x)=n(t,x),    (t,x)∈×^3,

where the source term n(t,x) is a zero-mean stationary random process
that models the ambient noise sources. We assume that its autocorrelation
function is 

    E(n(t_1,y_1)n(t_2,y_2))=F(t_2-t_1)K(y_1)δ(y_1-y_2),

where F is the time correlation function (normalised so that F(0)=1)
and K characterises the spatial support of the sources. The presence
of δ(y_1-y_2) makes the process n delta-correlated
in space.

The reconstruction is based on the calculation of the empirical cross
correlation of the signals recorded at x_1 and x_2 up to
time T: 

    C_T(τ,x_1,x_2)=1/T∫_0^Tu(t,x_1)u(t+τ,x_2) dt.

Its expectation is the statistical cross correlation 

    E(C_T(τ,x_1,x_2))=C^(1)(τ,x_1,x_2),

which is given by 

    C^(1)(τ,x_1,x_2)=1/2π∫_×^3F̂(ω)K(y)Ĝ(ω,x_1,y)Ĝ(ω,x_2,y)e^-iωτ dtdy,

where ·̂ denotes the Fourier transform in time and G(t,x,y)
is the time-dependent Green's function. Moreover, C_T is a self-averaging
quantity, namely 

    lim_T→+∞C_T(τ,x_1,x_2)=C^(1)(τ,x_1,x_2)

in probability.

The role of randomised sources is now clear: from the measured empirical
cross correlation C_T with large values of T it is possible
to estimate, with high probability, the statistical cross correlation
C^(1). Using (<ref>), from C^(1)(τ,x_1,x_2)
it is possible to recover (some properties of) the Green function
G, which yield useful information about the medium, such as travel
times.



 §.§ Deep Learning in inverse problems for PDE




Convolutional Neural Networks have recently been used for a variety
of imaging and parameter reconstruction problems <cit.>,
including Electrical Impedance Tomography (EIT) <cit.>,
optical tomography <cit.>, inverse problems with internal
data <cit.>, diffusion problems in imaging <cit.>,
computerised tomography <cit.>, photoacoustic
tomography <cit.> and magnetic
resonance imaging <cit.>. In the following brief
discussion, we decided to focus on inverse problems for partial differential
equations (PDE), and in particular on EIT, but similar considerations
are valid for most methods cited above.

Significant improvement has been observed in EIT with deep learning
compared to previous imaging approaches. Let Ω⊆^d,
d≥2, be a bounded Lipschitz domain with outer unit normal ν.
The data in EIT is (a part of) of the Dirichlet-to-Neumann map 

    Λ_σ[  H^1/2(∂Ω)/R            → H^-1/2(∂Ω)/R;            v            ↦  .σ∇ u·ν|_∂Ω ]

where u(x) denotes the unique solution of the elliptic problem

    {[ div(σ(x)∇ u(x))=0              x∈Ω,;         u(x)=v(x)             x∈∂Ω, ].

and σ(x)>0 is the unknown conductivity. The experimental data
is usually part of the inverse map, namely the Neumann-to-Dirichlet
map Λ_σ^-1. In two dimensions, provided that the
electrodes are equally separated on the unit disk, the data may be
modelled by 

    T_NΛ_σ^-1T_N,

where T_N is the L^2 projection on span{θ↦cos(nθ):1≤ n≤ N},
where N is the number of electrodes: it is the partial Fourier
transform limited to the first N coefficients.

Direct neural network inversion approaches suffer from drawbacks alike
direct non-regularised inversion attempts: the output is very sensitive
to measurement errors and small variations. Successful approaches
to Deep Learning EIT <cit.>,
and to other parameter identification problems in , often involve
two steps.

The first step consists in the derivation of an approximate conductivity
σ by a stable, albeit blurry, regularised inversion method.
For instance, in <cit.> the “D-bar” equation is
used, while in <cit.> a one-step Gauss-Newton method is
used. In both cases, the output of this step is a representation of
the conductivity coefficient, which depends on the inversion method
used. This first step is deterministic and its analysis is well understood.
The forward problem, relating the conductivity to the Dirichlet-to-Neumann
map, is nonlinear, independently of the inversion algorithm used.
Indeed, the map Λ_σ is a linear operator, but σ↦Λ_σ
is nonlinear.

The second, post-processing, step uses a neural network to “deblur”
the image, and in fact restores details that were not identifiable
after the first step.

The second step is not unlike other successful usage of deep-learning
approaches for image classification; in general they are known to
be successful only with very high probability (and in turn for random
unknowns). More precisely, since the findings of <cit.>,
deep networks are known to be vulnerable to so-called “adversarial
perturbations” (see the review article <cit.>
and the references therein). Given an image x that is correctly
classified by the network with high confidence, an adversarial perturbation
is a small perturbation p such that the images x and y=x+p
are visually indistinguishable but the perturbed image y is misclassified
by the network, possibly with high confidence too. State-of-the-art
classification networks are successful for the vast majority of natural
images, but are very often vulnerable to such perturbations.

These instabilities are not specific to image classification problems;
they appear in the same way in image reconstruction <cit.>.
In this case, given an image that is well-reconstructed by the network,
it is possible to create another image that is visually indistinguishable
from the original one, but that is not well-reconstructed by the network.

A full mathematical understanding of deep networks is still lacking,
and the reasons of this phenomenon are not fully known. However, the
large Lipschitz constant of the network certainly plays a role, since
it is a sign of potential instability: in order for the network to
be effective, the weights of its linear steps need to be chosen large
enough, and the composition of several layers yields an exponentially
large constant.



§ PROOFS OF THE LARGE DEVIATION ESTIMATES


The proofs of Theorem <ref> and Proposition <ref>
rest upon a classical large deviation estimate, the so-called Hoeffding
inequality, see e.g. <cit.>, whose proof is recalled
for the convenience of the reader. 

 Let (α_n^ν)_n≥1 be a
sequence of sequence of independent random variables of Bernoulli
type, on a probability space (A,𝒜,P) with mean
0 and variance 1. Then, for any t>0 and any sequence (u_n)_n≥1∈ℓ^2(),
we have 

    P(∑_n=1^+∞α_n^νv_n<-t)=P(∑_n=1^+∞α_n^νv_n>t)≤exp(-1/2t^2/∑_n=1^+∞|v_n|^2).

 



There holds 𝔼(exp(α_n^νv_n))=𝔼(∑_k=0^∞(α_n^νv_n)^k/k!)=∑_k=0^∞1/k!𝔼((α_n^νv_n)^k).
All odd powers of k vanish as α_n^ν has zero mean
and is symmetrical. Therefore for any λ>0 

    𝔼(exp(λα_n^νv_n))
         =∑_k=0^∞1/(2k)!𝔼((λα_n^νv_n)^2k)
       ≤∑_k=0^∞λ^2kv_n^2k/2^k(k!)
        =exp(λ^2/2v_n^2).

Applying Chernoff's inequality, we obtain for any λ>0 

    ℙ(∑_n=1^+∞α_n^νv_n>t)    ≤𝔼[exp(λ(∑_n=1^+∞α_n^νv_n))]exp(-λ t)
       ≤exp(λ^21/2∑_n=1^+∞v_n^2-λ t).

Choosing λ=t/∑ v_n^2 this yields 

    ℙ(∑_n=1^+∞α_n^νv_n<-t)=ℙ(∑_n=1^+∞α_n^νv_n>t)≤exp(-t^2/2∑ v_n^2),

as desired. 

We are now ready to prove Theorem <ref>. 


 Fix r≥2 and set 𝒴^ν=P(x^ν)/‖ x^ν‖ _X.
Markov's inequality yields 


    P(‖𝒴^ν‖_Y≥δ)     =P(‖𝒴^ν‖_Y^r≥δ^r)≤1/δ^rE(‖𝒴^ν‖_Y^r).


Let us denote by ℒ_ν^r the standard Lebesgue space
with respect to the probability measure dP. Recall that
Y=L^2(Σ,μ). To provide an estimate of the right-hand
side, notice that 

    E(‖𝒴^ν‖_Y^r)     =∫_A‖𝒴^ν‖_Y^r dP(ν)
        =∫_A(∫_Σ|𝒴^ν(s)|^2 dμ(s))^r/2 dP(ν)
        =‖∫_Σ|𝒴^ν(s)|^2 dμ(s)‖_ℒ_ν^r/2^r/2
       ≤(∫_Σ‖|𝒴^ν(s)|^2‖_ℒ_ν^r/2 dμ(s))^r/2
        =(∫_Σ‖𝒴^ν(s)‖_ℒ_ν^r^2 dμ(s))^r/2
        =‖ s↦‖𝒴^ν(s)‖_ℒ_ν^r‖_Y^r

by using Jensen's inequality.

Furthermore, for a.e. s∈Σ, we have[Here, we use that if X denotes a non-negative random variable and
φ_+→_+, then 

    E(φ(X))=∫_0^+∞φ'(u)P(X>u) du.

] 

    ‖𝒴^ν(s)‖_ℒ_ν^r^r=∫_A|𝒴^ν(s)|^rdP(ν)=∫_0^+∞ru^r-1P(|𝒴^ν(s)|>u) du

and by using Proposition <ref> and the fact that
𝒴^ν(s) reads 

    𝒴^ν(s)=∑_k=1^∞β_k^νx_k(P_k)(s)/√(∑_k=1^∞|x_k|^2),

one gets 

    ‖𝒴^ν(s)‖_ℒ_ν^r^r≤2∫_0^+∞ru^r-1exp(-1/2∑_k=1^∞|x_k|^2u^2/∑_k=1^+∞|(P_k)(s)|^2|x_k|^2) du.

As a consequence, by using the change of variable 

    v=√(∑_k=1^∞|x_k|^2)u/√(∑_k=1^+∞|(P_k)(s)|^2|x_k|^2)

we get 

    ‖𝒴^ν(s)‖_ℒ_ν^r^r≤ C(r)(∑_k=1^+∞|(P_k)(s)|^2|x_k|^2/∑_k=1^∞|x_k|^2)^r/2

with 

    C(r)=2∫_0^+∞rv^r-1e^-1/2v^2 dv.

An elementary computation yields C(r)<r^r. Therefore, 

    ‖𝒴^ν(s)‖_ℒ_ν^r<(r^2∑_k=1^+∞|(P_k)(s)|^2|x_k|^2/∑_k=1^∞|x_k|^2)^1/2.

According to (<ref>), we infer that 

    E(‖𝒴^ν‖_Y^r)     <‖(r^2∑_k=1^+∞|(P_k)(·)|^2|x_k|^2/∑_k=1^∞|x_k|^2)^1/2‖_Y^r
        =‖ r^2∑_k=1^+∞|(P_k)(·)|^2|x_k|^2/∑_k=1^∞|x_k|^2‖_L^1(Σ)^r/2.

From (<ref>) and estimate (<ref>), we get 

    P(‖𝒴^ν‖_Y≥δ)<1/δ^r(r^2∑_k=1^+∞‖ P_k‖_Y^2|x_k|^2/∑_k=1^∞|x_k|^2)^r/2≤(/δ^2r^2)^r/2,

using the triangle inequality. Minimising the upper bound with respect
to r, that is, choosing 

    r^2=e^-2δ^2/

in the inequality above, one finally obtains 

    P(‖𝒴^ν‖_Y≥δ)≤exp(-e^-1δ/√()).

Note that we have assumed r≥2, thus implicitly posited that
e^-2δ^2≥4; we multiply the bound by exp(2)
to cover the other case. 

We conclude by proving Proposition <ref>. 

 As in (<ref>), we have 

    ‖ P(x^ν)‖ _Y^2=∑_k=1^∞x_k^2‖ P(e_k)‖ _Y^2+2∑_k,l
    
    k<l
    β_k^νβ_l^νx_kx_l⟨ P(_k),P(_l)⟩ _Y.

Observing that the family α_k,l^ν={β_k^νβ_l^ν}_k,l

k<l is made of independent Bernoulli variables, equal almost surely to
-1 or 1, with 1/2 as probability of success, we apply Proposition <ref>
with 

    v_k,l=2x_k/‖ x‖ _Xx_l/‖ x‖ _X⟨ P(_k),P(_l)⟩ _Y

and obtain for all δ>0 

    ℙ(P(x^ν)_Y^2/x_X^2-𝔼(‖ P(x^ν)‖ _Y^2/‖ x‖ _X^2)<-δ)<exp(-δ^2/2K),

with 

    K     =∑_k,l
    
    k<l
    (2x_kx_l/‖ x‖ _X^2⟨ P(_k),P(_l)⟩ _Y)^2
       ≤2∑_k,l(|x_k||x_l|/‖ x‖ _X^2‖ P_k‖ _Y‖ P_l‖ _Y)^2
        =2(∑_k|x_k|^2/‖ x‖ _X^2‖ P_k‖ _Y^2)^2
       ≤2^2.



