# Causal Inference with Treatment Measurement Error:
A Nonparametric Instrumental Variable Approach

Yuchen Zhu Department of Computer Science
University College London
UK  Limor Gultchin  Department of Computer Science
University of Oxford
UK  The Alan Turing Institute
London, UK  Arthur Gretton  Department of Computer Science
University College London
UK  Matt Kusner  Department of Computer Science
University College London
UK  Ricardo Silva  Department of Computer Science
University College London
UK

###### Abstract

We propose a kernel-based nonparametric estimator for the causal effect when
the cause is corrupted by error. We do so by generalizing estimation in the
instrumental variable setting. Despite significant work on regression with
measurement error, additionally handling unobserved confounding in the
continuous setting is non-trivial: we have seen little prior work. As a by-
product of our investigation, we clarify a connection between mean embeddings
and characteristic functions, and how learning one simultaneously allows one
to learn the other. This opens the way for kernel method research to leverage
existing results in characteristic function estimation. Finally, we
empirically show that our proposed method, MEKIV, improves over baselines and
is robust under changes in the strength of measurement error and to the type
of error distributions.

##  1 Introduction

Real world data poses many problems for causal effect estimation. Unmeasured
confounding, the existence of hidden common causes of a treatment $X$ and an
outcome of interest $Y$, is a problem that lies at the heart of many applied
sciences. Solving this problem led to a variety of approaches, the most common
based on the idea of instrumental variables (IVs): an auxiliary variable $Z$
independent of $Y$ upon a perfect intervention on $X$ [Pearl, 2009, Hernán and
Robins, 2020], which is predictive of $X$ but not caused by it.

A less commonly studied challenge is when _the treatment is not directly
observed_. For instance, we may want to learn the effect of taking a drug
($X=1$) against not taking it ($X=0$), where we incentivize the patients to
take it or not ($Z=1$ vs $Z=0$). It is not necessarily the case that $X=Z$,
because the patients do it at home instead of a hospital with supervision, and
so they may not comply with the incentive. This _non-compliance_ problem is
compounded with the _measurement error_ problem: a self-reported measurement
of taking ($M=1$) or not taking ($M=0$) the drug does not imply $X=M$, because
the patient may be lying or just forgetful. An instrumental variable approach
to estimate an _average treatment effect_ (ATE) such as
$\mathbb{E}[Y\leavevmode\nobreak\ |\leavevmode\nobreak\
do(X=1)]-\mathbb{E}[Y\leavevmode\nobreak\ |\leavevmode\nobreak\ do(X=0)]$
[Pearl, 2009] may fail to give reliable results if our data consists of
records of $(Z,M,Y)$, but the assumption $X=M$ does not hold.

Figure 1: Comparison of curves fitted by our method and KIVM under a corrupted
treatment measurement $X$ against with true curve. KIVM is a method we will
discuss in the sequel, which ignores that measurements of $X$ are corrupted by
additive noise.

A related issue happens when postulating latent _constructs_ as causes. In a
widespread example by [Bollen, 1989], a model for the effects of
“industrialization level” of a country in its political freedom $Y$ is
considered. We may operationalize this construct by postulating a space of
possible interventions $Z$ on industrialization $X$ that keep the relation
between $X$ and $Y$ invariant. However, it remains the case that $X$ is not
directly observable but for indirect measurements $M$, such as the GDP or the
proportion of labor force working in industry.

Of relevance, in both classes of indirect treatment measurement problem, is
that the causal relation $\mathbb{E}[Y\leavevmode\nobreak\
|\leavevmode\nobreak\ do(x)]$ is considered to be fundamental, with
$\mathbb{E}[Y\leavevmode\nobreak\ |\leavevmode\nobreak\ do(m)]$ being either
zero, or poorly defined, or of secondary interest (for instance, _redefining_
GDP may as well have a genuine causal impact, but this intervention is not the
motivation behind understanding the causal impact of industrialization
levels). In particular, measurement mechanisms may change more easily than the
relation between the putative cause and the outcome of interest (we may
redefine GDP, or collect data where the phrasing and timing of our questioning
of a patient’s compliance varies in different communities, while assuming that
the relation between $X$ and $Y$ is invariant). In a way, this measurement
problem is a counterpart to why estimating intention-to-treat effects, i.e.
$\mathbb{E}[Y\leavevmode\nobreak\ |\leavevmode\nobreak\ do(z)]$, is not in
many cases the goal of an IV analysis, despite the policy-making implications.

The need to understand effects of the mismeasured quantities on other
quantities of interest motivates the study of measurement error modeling
[Carroll et al., 2006, Schennach, 2016, Hernán and Robins, 2020]. Famously,
even in the linear (noncausal) regression case, naïvely regressing $Y$ on a
noisy measurement of $X$ results in _attenuation error_ , which essentially
means that the regression coefficient will be underestimated due to the
measurement error [Carroll et al., 2006]. An analogous phenomenon will take
place when estimating causal effects. Figure 1 depicts a kernel method that
attempts to estimate a $X$-$Y$ dose-response curve, ignoring measurement error
in $X$, compared against the curve found by the method we propose.

The nonlinear and confounded setting is an open domain to be explored.
Schennach [2016] suggests that, in general, three measurements are needed to
identify the full joint distribution of the measurements and the latent
variable. However, in cases where we can make some assumptions on the error
distribution, this can be reduced. Furthermore, we are not interested in the
full joint distribution with the latent variable $X$, but only the parts which
we need as components of the IV regression model. To that effect, we will
assume that our problem follows the Markov properties of Figure 2: we are
interested in the structural function
$f(x)\equiv\mathbb{E}[Y\leavevmode\nobreak\ |\leavevmode\nobreak\ do(x)]$,
where observationally $Y=f(x)+\epsilon$, the error term $\epsilon$ being
correlated with treatment $X$. We assume that we have access to at least two
treatment measurements, $M$ and $N$, and an instrumental variable $Z$.

$X$$Y$$Z$$\epsilon$$M$$N$$f$ Figure 2: An instrumental variable model with
confounded treatment $X$ and $Y$, where the treatment is unobservable, but has
indirect measurements $M$ and $N$.

Our contribution is threefold:

  * •

we propose an estimator for the structural function $f(x)$ without requiring
latent variable modeling. The resulting method can be applied without
restrictive assumptions in the likelihood, such as the requirement for
Gaussian error terms;

  * •

in particular, we provide a method to learn the conditional mean embedding
[Muandet et al., 2017] of a latent variable distribution, which can be applied
to many two-stage IV settings;

  * •

we propose a way to exploit the connection between characteristic function
methods and kernel methods, which may be applied to many settings outside of
measurement error modelling (see Section 4.1).

##  2 Related Work

Measurement bias takes several forms in causal inference. See [Hernán and
Robins, 2020, Chapter 9] for a textbook overview, including examples
motivating different error structures. For instance, there is a growing
literature on causal inference by adjusting for confounders which are only
measured via proxies [e.g Kuroki and Pearl, 2014, Battistin and Chesher, 2014,
Kallus et al., 2018, Miao et al., 2018, Mastouri et al., 2021, Ghassami et
al., 2022]. Because different components of a causal structure contribute
differently to the target estimand, it is not surprising though that
conditions on identifiability in our setup vary substantively from, e.g.,
those required by models of confounding proxies. In general, our work is
related to the large field of latent variable distribution identification,
particularly those involving Markovian assumptions [Allman et al., 2009]. Even
closer is the literature on _error-in-variables_ regression [Carroll et al.,
2006], as it provides several results for identification and estimation in the
related problem of regression analysis. Schennach [2016] provides a more up-
to-date review, including some comments on its use in causal effect
estimation. To the best of our knowledge, no direct connection between methods
for continuous causal effect estimation with both unmeasured confounding and
measurement error in the treatment is described in the literature. For
partially identified models in _discrete_ spaces, Finkelstein et al. [2021]
provide an approach based on the linear programming formulation of Balke and
Pearl [1994]. It should be pointed out that the term “instrumental variable”
is sometimes used in the error-in-variables regression literature as the name
for a second measurement of the missing regressor $X$ [Carroll et al., 2006,
Chapter 6]. In this work, it signifies a direct cause of $X$ (the more
standard definition in causal inference literature). A similar setting was
studied in Gultchin et al. [2021], where $Z$ operated as a crude intervention
on a complex cause $X$ and causal effects under new $Z$ interventions could be
computed due to invariance. A family of methods for causal inference with
corrupted data is presented by Agarwal and Singh [2021], including a linear
error-in-variables formulation with Riesz representers that can be interpreted
as estimating causal effects when no confounding is present. An example of
effect estimation with observed confounding adjustment is Song et al. [2015],
and an example combining deconfounding and measurement error correction with
linear models is Vansteelandt et al. [2009]. Finally, measurement error has
also been considered in the causal graph discovery literature [e.g. Silva et
al., 2006, Zhang et al., 2018]. In this case, all observed variables are
measurements of some underlying latent causes, and the goal is to learn the
causal structure among such latent variables. Parametric assumptions are
usually necessary, and no nonlinear causal effect estimators are provided when
latent variables are themselves confounded by further hidden common causes.

##  3 Background

Throughout, we use capital letters (e.g. $A$) to denote a random variable on a
measurable space. We denote measurable spaces by calligraphic letters
($\mathcal{A}$), with one exception: $\mathcal{P}$, which we use to denote a
probability measure. We use lowercase letters to denote realizations of a
random variable ($A=a$). We will use the structural causal model (SCM)
formulation of Pearl [2009], where causal relationships are represented as
directed acyclic graphs (DAGs). The operator $do(\cdot)$ is defined in these
models to describe the process of forcing a random variable to take a
particular value, which isolates its effect on downstream variables (i.e.
${{\mathbb{E}}}[Y\leavevmode\nobreak\ |\leavevmode\nobreak\ do(A=a)]$
describes the isolated effect of $A$ on $Y$).

Our goal is to estimate the average treatment effect (ATE)
$\mathbb{E}[Y\leavevmode\nobreak\ |\leavevmode\nobreak\ do(X=x)]$ given the
graph in Figure 2 (equivalent to the structural function
$f:\mathcal{X}\longrightarrow\mathcal{Y}$). Here $X,\epsilon$ are unobserved.
We only have access to an instrument $Z$, the effect $Y$, and corrupted
measurements of $X$: $M$ and $N$.

###  3.1 Structural Assumptions on $p(x,y\leavevmode\nobreak\
|\leavevmode\nobreak\ z)$

When the treatment $X$ is observed and an instrument $Z$ is available, the
structural function is identified by

###### Assumption 1

$Y=f(X)+\epsilon$ and ${{\mathbb{E}}}[\epsilon|Z]=0$

###### Assumption 2

$p(x|z)$ is not constant in $z$.

Under Assumptions 1 and 2, the structural function satisfies the following
equation $\mathcal{P_{Z}}$-almost surely.:

$\displaystyle{{\mathbb{E}}}[Y|Z]={{\mathbb{E}}}[f(X)|Z]=\int
f(x)d\mathcal{P_{X|Z}}$ (1)

Typical methods fall into two categories: 1) two-stage methods (Singh et al.
[2019a], Hartford et al. [2017], Xu et al. [2020]): first identify the
conditional distribution directly or through estimating conditional
expectations of basis functions; this is followed by identifying $f$ under the
identified conditional distribution of vector of conditional expected values
of basis functions; 2) moment-based methods (Zhang et al. [2020], Bennett et
al. [2019]): estimate $f$ using moment conditions generated by the conditional
moment restriction: ${{\mathbb{E}}}[(Y-f(X))g(Z)]=0$ $\forall g$ measurable. A
practical difference between two-stage methods and moment-based methods is
that two-stage methods require separate data for each stage, and the first
stage does not require the outcome observations $Y$, whereas moment-based
methods require data for all variables simultaneously. In this work, we seek
to identify the measurement process before identifying the structural
function. We thus naturally adopt the two-stage framework since the
measurement process requires only the instrument and the measurements, and not
the outcome labels.

###  3.2 Reproducing kernel hilbert spaces

For any space
$\mathcal{S}\in\\{{{\mathcal{X}}},{{\mathcal{Y}}},{{\mathcal{M}}},{{\mathcal{N}}},{{\mathcal{Z}}}\\}$,
let $k:\mathcal{S}\times\mathcal{S}\rightarrow\mathbb{R}$ be a positive
definite kernel. We denote by $\phi$ its associated canonical feature map
$\phi(x)=k(x,\cdot)$ for any $x\in\mathcal{S}$, and $\mathcal{H_{S}}$ its
corresponding Reproducing Kernel Hilbert Space (RKHS) of real-valued functions
on $\mathcal{S}$. The space $\mathcal{H_{S}}$ is a Hilbert space with inner
product $\langle\cdot,\cdot\rangle_{\mathcal{H_{S}}}$. It satisfies two
important properties: (i) $k(x,\cdot)\in\mathcal{H_{S}}$ for all
$x\in\mathcal{S}$, (ii) the reproducing property: for all
$h\in\mathcal{H_{S}}$ and $x\in\mathcal{S},h(x)=\langle
h,k(x,\cdot)\rangle_{\mathcal{H_{S}}}$. For any distribution $p$ on
$\mathcal{S}$, $\mu_{p}\vcentcolon=\int k(x,\cdot)p(x)dx$ is an element of
$\mathcal{H_{S}}$ and is referred to as the kernel mean embedding of $p$
(Smola et al. [2007]). Similarly, for any conditional distribution $p(x|z)$,
$\mu_{{{\mathcal{P}}}_{X|z}}\vcentcolon=\int k(x,\cdot)p(x|z)dx$ is a
conditional mean embedding (CME) of $p(x|z)$ (Song et al. [2009, 2013]); see
Muandet et al. [2017] for a review.

###  3.3 Structure learning using kernel mean embeddings

Provided that the structural function $f$ lies in the RKHS
${{\mathcal{H}}}_{{{\mathcal{X}}}}$, then its conditional expectation under
${{\mathcal{P}}}_{X|Z}$ can be written as ${{\mathbb{E}}}[f(X)|Z]=\langle
f,\mu_{{{\mathcal{P}}}_{X|Z}}\rangle_{\mathcal{H_{X}}}$. In Singh et al.
[2019b], the conditional mean embedding is estimated by the standard
regression formula using the observed samples
$\\{z_{j},x_{j}\\}_{j=1}^{s_{1}}$ before the structural function $f$ is
estimated using a second-stage sample
$\\{\check{z}_{j},\check{y}_{j}\\}_{j=1}^{s_{2}}$. We present their solution
here.

The CME estimator of ${{\mathcal{P}}}_{X|z}$ is estimated using the samples
$\\{z_{j},x_{j}\\}_{j=1}^{s_{1}}$

$\displaystyle\hat{\mu}^{(s_{1})}_{{{\mathcal{P}}}_{X|z}}$
$\displaystyle=\Phi_{X}(K_{ZZ}+s_{1}\hat{\lambda}I)^{-1}\Phi^{\prime}_{Z}\phi(z)$
(2)

where $\hat{\lambda}$ is the ridge regression hyperparameter chosen using the
validation procedure described in [Singh et al., 2019a, App.7.4.2]. $K_{ZZ}$
denote the kernel matrix where $(K_{ZZ})_{jl}=k(z_{j},z_{l})$,
$(\Phi_{X})_{(:,j)}=\phi(x_{j})$. This is precisely the adaptation of ridge
regression to multi-dimensional feature spaces to the case where the number of
features can be infinite. Furthermore, if we assume that the structure
function lies in an RKHS, then we can learn the function $f$ in two steps of
regression: first a regression to get the CME, followed by a regression from
the CME to $Y$ to obtain $f$. We go ahead to make this assumption.
Importantly, we stress that the purpose of this assumption is for the
nonparametric modelling of $f$, and is not to do with the correction of
measurement error.

###### Assumption 3

$f\in{{\mathcal{H}}}_{{{\mathcal{X}}}}$

Assuming $f\in{{\mathcal{H}}}_{{{\mathcal{X}}}}$, the estimated CME
$\hat{\mu}^{(s_{1})}_{{{\mathcal{P}}}_{X|z}}$ is used to learn the structural
function $f$ by solving the empirical analogue of the following:

$\displaystyle{{\mathbb{E}}}[Y|Z]$ $\displaystyle=\langle
f,\mu_{{{\mathcal{P}}}_{X|z}}\rangle_{\mathcal{H_{X}}}$ (3)

We solve for $f$ via least squares in two stages: 1. Use
$\\{\check{z}_{j},\check{y}_{j}\\}_{j=1}^{s_{1}}$ to Monte-Carlo estimate
${{\mathbb{E}}}[Y|Z]$ and $\mu_{{{\mathcal{P}}}_{X|z}}$ (call the latter
$\hat{\mu}^{(s_{1})}_{{{\mathcal{P}}}_{X|z}}$); 2. Use
$\\{\check{z}_{j},\check{y}_{j}\\}_{j=1}^{s_{2}}$ to estimate $f$ via

$\displaystyle\hat{f}^{(s_{2})}(x)$ $\displaystyle=\hat{\beta}^{\prime}K_{Xx}$
(4) $\displaystyle\hat{\beta}$
$\displaystyle=(VV^{\prime}+s_{2}\hat{\xi}K_{XX})^{-1}V\check{y}$ (5)
$\displaystyle V$
$\displaystyle=K_{XX}(K_{ZZ}+s_{1}\hat{\lambda}I)^{-1}K_{Z\check{Z}}$ (6)

where $\hat{\xi}$ is a hyperparameter. Note that
$\hat{\mu}^{(s_{1})}_{{{\mathcal{P}}}_{X|z}}$ enters in eq. (6):
$V_{jl}=\phi(x_{j})^{T}\Phi_{X}(K_{ZZ}+s_{1}\hat{\lambda}I)^{-1}\Phi^{\prime}_{Z}\phi(\check{z}_{l})=\hat{\mu}^{(s_{1})}_{{{\mathcal{P}}}_{X|\check{z}_{l}}}(x_{j})$.
We refer the readers to Singh et al. [2019b] for the full derivation and for
tuning $\hat{\xi}$.

This approach works when we observe treatment $X$. When $X$ is unobserved,
this is not possible. Thus, we propose a method to learn the CME directly from
corrupted measurements of $X$; then, $f$ is yielded as a mapping from the
learnt CME to $Y$ as in Eq. (4) to Eq. (6). Our method is detailed in Section
4. We note that the solution of Singh et al. [2019b] requires standard
conditions for kernel causal learning, which we inherit. For clarity of
presentation, we detail them in the Section C of the Supplementary Materials.

###  3.4 Characteristic function identification of a latent variable using
mismeasured observations

The main obstacle in the learning of the CME $\mu_{\mathcal{X|Z}}$ is the lack
of observed data of $X$. To this end, we first review a strongly related
problem, which is to identify the characteristic function of $p(x|z)$ using
corrupted observations $M$ and $N$. The following assumptions are needed.

###### Assumption 4

Measurement errors enter additively:

$\displaystyle M$ $\displaystyle=X+\Delta M$ (7) $\displaystyle N$
$\displaystyle=X+\Delta N$ (8)

###### Assumption 5

The measurement errors are uncorrelated with each other, $\Delta M$ is
uncorrelated with $X$, $\Delta N$ is independent with $X$, and $\epsilon$ is
uncorrelated with $\Delta N$:

$\displaystyle{{\mathbb{E}}}[\Delta M|X,\Delta N]=0$ (9) $\displaystyle
X\perp\\!\\!\\!\perp\Delta N$ (10)
$\displaystyle{{\mathbb{E}}}[\epsilon|\Delta N]=0$ (11)

As $X$ is unobserved and can be redefined up to any invertible transformation,
Eq. (7) is not imposing further constraints besides a monotonic relation
between $M$ and $X$ in expectation. Eqs. (9) and (11) are weaker formulations
of conditional independence statements $\Delta M\perp\\!\\!\\!\perp\\{X,\Delta
N\\}$ and $\epsilon\perp\\!\\!\\!\perp\Delta N$.

###### Remark 1

Eq. (8) is a restrictive assumption. However, we point out that it can be
relaxed and the relaxed setting can be reduced to our setting. Thus we focus
on the simplified setting where future methods can extend from; we discuss one
way to relax the assumption in Section B of the Supplementary Materials.

With two measurements, Schennach [2004] provides a constructive estimator for
the moments of latent variables. Our work uses a special case of their theorem
which we state below.

###### Assumption 6

${{\mathbb{E}}}[|X|]<\infty$ and ${{\mathbb{E}}}[|\Delta M|]<\infty$

###### Corollary 1

Given Assumptions 4-6, the characteristic function of $X$ given $Z=z$, i.e.
$\psi_{{{\mathcal{P}}}_{X|z}}(\alpha)$, is equal to

$\displaystyle\overbrace{{{\mathbb{E}}}_{{{\mathcal{P}}}_{X|z}}[e^{i\alpha
X}]}^{\psi_{{{\mathcal{P}}}_{X|z}}(\alpha):=}$
$\displaystyle=\exp\left(\int_{0}^{\alpha}i\frac{{{\mathbb{E}}}[Me^{i\nu
N}|z]}{{{\mathbb{E}}}[e^{i\nu N}|z]}d\nu\right).$ (12)

###### Proof.

Follows directly from [Schennach, 2004, Theorem 1], where the original phrased
the equality for the marginal distribution $p(x,m,n)$. ∎

Since characteristic functions are exact representations of probability
distributions, Corollary 1 says that we may model ${{\mathcal{P}}}_{X|z}$
through modelling ${{\mathcal{P}}}_{M,N|z}$ and ${{\mathcal{P}}}_{N|z}$, and
the mathematical relation is specified by Eq. (12).

##  4 Method

In this section we will show how to recover $\mathbb{E}[Y\leavevmode\nobreak\
|\leavevmode\nobreak\ do(X\\!=\\!x)]$. To do so, recall that all we need is
the kernel mean embedding $\mu_{{{\mathcal{P}}}_{X|Z}}$. We begin by
demonstrating that estimating $\mu_{{{\mathcal{P}}}_{X|Z}}$ boils down to
estimating the characteristic function $\psi_{{{\mathcal{P}}}_{X|Z}}$. We then
introduce a trick for solving integral equations that we call the
_differentiation trick_ which allows us to estimate
$\psi_{{{\mathcal{P}}}_{X|Z}}$ without explicitly estimating the integral.
Finally, we give a full procedure for estimating
$\mathbb{E}[Y\leavevmode\nobreak\ |\leavevmode\nobreak\ do(X\\!=\\!x)]$ and
describe advantages of our approach.

###  4.1 From kernel mean embeddings to characteristic functions

For simplicity, we limit our description to ${{\mathbb{R}}}$. However, all of
the following arguments can be extended trivially to ${{\mathbb{R}}}^{d},d>1$.
First recall the Fourier transform:

$\displaystyle\tilde{h}(\alpha)$
$\displaystyle=\frac{1}{2\pi}\int_{-\infty}^{\infty}h(x)e^{-i\alpha x}dx$

and the inverse Fourier transform:

$\displaystyle h(x)$
$\displaystyle=\int_{-\infty}^{\infty}\tilde{h}(\alpha)e^{i\alpha x}d\alpha.$

Further, we assume the following.

######  Assumption 7 (Symmetric, characteristic and translation-invariant
kernels)

$k(x,\cdot),k(m,\cdot),k(n,\cdot)$ are symmetric, characteristic and
translation-invariant kernels.

Kernel symmetry is a standard assumption in ML as kernel functions are
generally real. Characteristic kernels allow us to embed probability
distributions uniquely in an RKHS. Translation-invariant kernels allow us to
consider the probability measure associated with kernel functions.

Under Assumption 7, we can write $k(x,y)=k(x-y)$ and $k(t)$ is positive
definite. By Bochner’s theorem, we know that $k$ can be written as the Fourier
transform of a unique measure $\tilde{k}$:

$\displaystyle k(t)$
$\displaystyle=\frac{1}{2\pi}\int_{-\infty}^{\infty}e^{-i\alpha
t}\tilde{k}(\alpha)d\alpha$ $\displaystyle\text{i.e. }\;k(x,y)$
$\displaystyle=\int_{-\infty}^{\infty}e^{-i\alpha(x-y)}q(\alpha)d\alpha$

where $q(\alpha):=\frac{1}{2\pi}\tilde{k}(\alpha)$. As illustrated in e.g.
Fukumizu [2008], we may construct an RKHS on the entire real line using
Fourier transforms as feature maps:

$\displaystyle\mathcal{H}_{X}=\left\\{f\in{{\mathcal{L}}}^{2}(\mathbb{R},dx)\Bigg{|}\int_{-\infty}^{\infty}\frac{\left|\tilde{f}(\alpha)\right|^{2}}{q(\alpha)}d\alpha<\infty\right\\}$
$\displaystyle\langle
f,g\rangle_{{{\mathcal{H}}}_{X}}=\int_{-\infty}^{\infty}\frac{\tilde{f}(\alpha)\overline{\tilde{g}(\alpha)}}{q(\alpha)}d\alpha$

Now consider the Fourier transform of $k(x,\cdot)$, where $x$ is fixed. Since
we know that $k(x,y)=\int e^{-i\alpha x}e^{i\alpha y}q(\alpha)d\alpha$, by
inspection we realise $\tilde{k}(x,\alpha)=e^{-i\alpha x}q(\alpha)$,
recovering the identity that $k(x,y)=\int_{-\infty}^{\infty}\frac{e^{-i\alpha
x}q(\alpha)e^{i\alpha y}q(\alpha)}{q(\alpha)}d\alpha=\langle
k(x,\cdot),k(y,\cdot)\rangle_{{{\mathcal{H}}}_{X}}$.

Recall the definition of the conditional mean embedding of $\mathcal{P}_{X|z}$
for a particular $z$: $\mu_{\mathcal{P}_{X|z}}(y)\vcentcolon=\int
k(x,y)p(x|z)dx$. When all variables are observed, the conditional mean
embedding (CME) can be estimated by samples $\\{x_{j},z_{j}\\}_{j=1}^{s}$:

$\displaystyle\hat{\mu}^{(s)}_{X|z}(y)$
$\displaystyle=\sum_{j=1}^{s}\hat{\gamma}_{j}^{(s)}(z)k(x_{j},y)$ (13)

where

$\displaystyle\hat{\gamma}_{j}^{(s)}(z)=(K_{ZZ}+s\hat{\lambda}^{(s)}I)^{-1}K_{Zz}$
(14)

Taking the Fourier transform of $\hat{\mu}^{(s)}_{X|z}(y)$:

$\displaystyle\tilde{\hat{\mu}}^{(s)}_{X|z}(\alpha)$
$\displaystyle=\sum_{j=1}^{s}\hat{\gamma}_{j}^{(s)}(z)e^{-i\alpha
x_{j}}q(\alpha)$
$\displaystyle=q(\alpha)\underbrace{\sum_{j=1}^{s}\hat{\gamma}_{j}^{(s)}(z)e^{-j\alpha
x_{j}}}_{=\vcentcolon\hat{\psi}^{(s)}_{\mathcal{P}_{X|z}}(-\alpha)}$

Define the $s-$sample estimate of the characteristic function
$\hat{\psi}^{(s)}_{\mathcal{P}_{X|z}}(\alpha)\vcentcolon=\sum_{j=1}^{s}\hat{\gamma}_{j}^{(s)}(z)e^{i\alpha
x_{j}}$ with $\\{x_{j}\\}_{j=1}^{s}\sim\mathcal{P}_{X|z}$. Next, we show that
$\hat{\psi}^{(s)}_{\mathcal{P}_{X|z}}\longrightarrow\psi_{\mathcal{P}_{X|z}}$
in $\mathcal{L}^{2}(\mathbb{R},q)$ if and only if
$\hat{\mu}_{\mathcal{P}_{X|z}}^{(s)}\longrightarrow\mu_{\mathcal{P}_{X|z}}$ in
$\mathcal{H}_{X}$.

######  Theorem 1 (Convergence in CME is identical to convergence in
characteristic function)

. Let $k:\mathcal{X}\times\mathcal{X}\longrightarrow\mathbb{R}$ be a
symmetric, positive definite, and translationally invariant characteristic
kernel, then for a (conditional) probability measure on $\mathcal{X}$, denoted
$\mathcal{P}_{X|z}$, we have that
$\hat{\psi}^{(s)}_{\mathcal{P}_{X|z}}\longrightarrow\psi_{\mathcal{P}_{X|z}}$
in $\mathcal{L}^{2}(\mathbb{R},q)$ if and only if
$\hat{\mu}_{\mathcal{P}_{X|z}}^{(s)}\longrightarrow\mu_{\mathcal{P}_{X|z}}$ in
$\mathcal{H_{X}}$. Moreover, whenever either converges, the other converges at
the same rate.

We provide the proof in Section F of the Supplementary Materials.

This means learning the characteristic function $\psi_{{{\mathcal{P}}}_{X|z}}$
in ${{\mathcal{L}}}^{2}(\mathbb{R},q)$ simultaneously gives us a precise
estimate of the kernel mean embedding $\mu_{{{\mathcal{P}}}_{X|z}}$ in
${{\mathcal{H}}}_{X}$.

###  4.2 Learning the Latent Characteristic Function

We now show how to learn the latent characteristic function which will give us
the latent kernel mean embedding.

Notation. To lighten notation, from now on we will use $\hat{f}$ to denote the
empirical estimate of a quantity $f$, and only use $\hat{f}^{(s)}$ when we
need to be specify the sample size $s$.

What if we are able to observe $X$? When $X$ is observed,
$\hat{\mu}^{(s)}_{\mathcal{P}_{X|z}}$ can be obtained directly and it can be
shown that
$\hat{\mu}^{(s)}_{\mathcal{P}_{X|z}}\longrightarrow\mu_{\mathcal{P}_{X|z}}$ as
$s\longrightarrow\infty$. By Theorem 1, the same samples and $\lambda$ which
closely estimate the CME $\mu_{{{\mathcal{P}}}_{X|z}}$ would also closely
estimate the characteristic function $\psi_{\mathcal{P}_{X|z}}$, and vice
versa 111This should be possible for $z$ from an unseen distribution
${{\mathcal{P}}}_{\check{\mathcal{Z}}}$ provided the unseen distribution has
the same support as the training distribution ${{\mathcal{P}}}_{Z}$.. Thus,
when $s$ is suitably large, we can accurately approximate the right hand side
of $\eqref{eq: char_cme}$ as

$\displaystyle\exp\left(\int_{0}^{\alpha}i\frac{{{\mathbb{E}}}[Me^{i\nu
N}|z]}{{{\mathbb{E}}}[e^{i\nu N}|z]}d\nu\right)$
$\displaystyle\approx\sum_{j=1}^{s}\hat{\gamma}_{j}(z)e^{i\alpha x_{j}}$ (15)

where $\hat{\gamma}_{j}(z)$ is specified by Eq. (14). Recall that this term
also depends on $\hat{\lambda}$. To make this explicit we write
$\hat{\gamma}^{\hat{\lambda}}_{j}(z)$.

Solving for $X$. Given eq. 15 we make the following observation: given samples
of $\\{z_{j}\\}_{j}$, the estimate $\hat{\psi}_{\mathcal{P}_{X|z}}$ only
depends on $\\{x_{j}\\}_{j}$ and $\hat{\lambda}$.

Therefore, we can solve for $\\{x_{j}\\}_{j},\hat{\lambda}$ by minimising the
discrepancy between both sides of Eq. (15) over
$\\{x_{j}\\}_{j},\hat{\lambda}$:

$\displaystyle\\{\hat{x}_{j}\\}_{j},\hat{\lambda}_{X}$
$\displaystyle=\operatorname*{argmin}_{\\{x_{j}\\}_{j},\hat{\lambda}}{{\mathbb{E}}}_{q(\alpha),{{\mathcal{P}}}_{\check{Z}}}\left[\left(\sum_{j=1}^{s}\hat{\gamma}^{\hat{\lambda}}_{j}(\check{Z})e^{i\alpha\hat{x}_{j}}-\eta\right)^{2}\right]$
(16) $\displaystyle\text{with }\eta$
$\displaystyle=\exp\int_{0}^{\alpha}\left(i\frac{{{\mathbb{E}}}[Me^{i\nu
N}|\check{Z}]}{{{\mathbb{E}}}[e^{i\nu N}|\check{Z}]}d\nu\right)$

The expectation is taken over $q(\alpha)$ and ${{\mathcal{P}}}_{\check{Z}}$
because, had the $X-$samples been observed, the convergence of characteristic
function is in ${{\mathcal{L}}}^{2}(\mathbb{R},q)$ and the $\check{Z}$
distribution does not have to equal to the one used to learn the CME, as long
as the two have the same support. To estimate $\eta$ requires two components
of approximation: a) finite-sample approximation of ${{\mathbb{E}}}[e^{i\nu
N}|\check{Z}]$ and ${{\mathbb{E}}}[Me^{i\nu N}|\check{Z}]$, b) computation of
the integral $\int_{0}^{\alpha}\left(i\frac{{{\mathbb{E}}}[Me^{i\nu
N}|\check{Z}]}{{{\mathbb{E}}}[e^{i\nu N}|\check{Z}]}d\nu\right)$, given a).
While it is possible to use numerical methods such as quadrature to
approximate the integral, we propose to save the second component by
differentiation.

The Differentiation Trick. We now describe a trick for handling intractable
integrals when solving a system of equations. First, let us reproduce eq. (12)
below

$\displaystyle\overbrace{{{\mathbb{E}}}_{{{\mathcal{P}}}_{X|z}}[e^{i\alpha
X}]}^{\psi_{{{\mathcal{P}}}_{X|z}}(\alpha):=}$
$\displaystyle=\exp\left(\int_{0}^{\alpha}i\frac{{{\mathbb{E}}}[Me^{i\nu
N}|z]}{{{\mathbb{E}}}[e^{i\nu N}|z]}d\nu\right).$

We can take the natural logarithm and differentiate both sides of eq. (12),
and substitute the samples of $\check{\mathcal{Z}}$:

$\displaystyle\frac{{{\mathbb{E}}}[Xe^{i\alpha
X}|\check{z}]}{{{\mathbb{E}}}[e^{i\alpha X}|\check{z}]}$
$\displaystyle=\frac{{{\mathbb{E}}}[Me^{i\alpha
N}|\check{z}]}{{{\mathbb{E}}}[e^{i\alpha N}|\check{z}]}$ (17)

Since differentiation is a many-to-1 operation, we need to verify that the
solution to Eq. (17) is also the solution to Eq. (12).

###### Lemma 1

Considering differentiable functions $\mathbb{C}^{n}\rightarrow\mathbb{C}$.
Denote $f^{\prime}(x):=\frac{d}{dx}f(x)$. Then if $f^{\prime}=g^{\prime}$ and
$f(a)=g(a)=b,a,b\in\mathbb{C}$, then $f=g$.

###### Proof.

If $f^{\prime}=g^{\prime}$, then $f=g+C$ for some $C\in\mathbb{C}$. But
$f(a)-g(a)=b-b=0$, so $C=0$. ∎

###### Theorem 2

The (conditional) distribution of $X$, denoted by $\mathcal{P}_{X|z}$, which
satisfies Eq. (17) is unique, and therefore is the same as the solution to
(12).

The proof relies on the fact that characteristic functions are always $1$ at
$\alpha=0$ (Section F of the Supplementary Materials).

When should one use the differentiation trick? When estimation for the target
function/parameter requires evaluating an intractable integral, one can think
of using the differentiation trick. Lemma 1 specifies one condition where this
can be done. Note that there are more situations where the differentiation
trick can be applied, such as when all functions in the target class have the
same normalization constant. We summarize two situations where the
differentiation trick can be applied:

  * •

When the target function class is itself normalized, or fixed at certain input
values. Examples of this which may be of interest to machine learning
practitioners are: a) probability densities, which always integrates to 1, b)
cumulative distributions, which is always $1$ at $\infty$.

  * •

When an invertible transformation of the function class is normalized or fixed
at certain inputs. In those cases, one can in principle solve the problem in
the normalized function class, and then apply the invertible transformation to
go back to original class.

Towards a sample-based estimator. As discussed, we may replace
${{\mathbb{E}}}[e^{i\alpha X}|\check{z}]$ and ${{\mathbb{E}}}[e^{i\alpha
N}|\check{z}]$ with their finite-sample estimates
$\hat{\psi}_{\mathcal{P}_{X|\check{z}}}$ and
$\hat{\psi}_{\mathcal{P}_{N|\check{z}}}$. For ${{\mathbb{E}}}[Xe^{i\alpha
X}|\check{z}]$ and ${{\mathbb{E}}}[Me^{i\alpha N}|\check{z}]$, we realise that
${{\mathbb{E}}}[Xe^{i\alpha
X}|\check{z}]=\frac{\partial}{\partial\alpha}{{\mathbb{E}}}[e^{i\alpha
X}|\check{z}]$, and ${{\mathbb{E}}}[Me^{i\alpha
N}|\check{z}]=\frac{\partial}{\partial\upsilon}\bigg{|}_{\upsilon=0}{{\mathbb{E}}}[e^{i(\alpha
N+\upsilon M)}|\check{z}]$. Thus, we replace them with
$\frac{\partial}{\partial\alpha}\hat{\psi}_{{{\mathcal{P}}}_{X|z}}(\alpha)$
and
$\frac{\partial}{\partial\upsilon}\bigg{|}_{\upsilon=0}\hat{\psi}_{{{\mathcal{P}}}_{M,N|z}}(\alpha,\upsilon)$
respectively. The full expressions of $s-$sample estimates for
$\hat{\psi}_{{{\mathcal{P}}}_{X|z}}(\alpha)$,
$\hat{\psi}_{{{\mathcal{P}}}_{N|z}}(\alpha)$,
$\hat{\psi}_{{{\mathcal{P}}}_{M,N|z}}(\upsilon,\alpha)$ and the relevant
derivatives are stated in Section D of the Supplementary Materials.

Therefore, we arrive at the new objective function:

$\displaystyle\\{\hat{x}_{j}\\}_{j=1}^{s},\hat{\lambda}_{X}=$
$\displaystyle\operatorname*{argmin}_{\\{x_{j}\\}_{j=1}^{s},\hat{\lambda}_{X}}{{\mathbb{E}}}_{q(\alpha),{{\mathcal{P}}}_{\check{Z}}}\left[\left(w_{X}(\alpha,\check{Z})-w_{MN}(\alpha,\check{Z})\right)^{2}\right]$
(18) $\displaystyle\text{with}\hskip
14.22636ptw_{X}(\alpha,\check{Z})=\frac{\sum_{j=1}^{s}x_{j}\hat{\gamma}_{X}(\check{Z})_{j}e^{i\alpha
x_{j}}}{\sum_{j=1}^{s}\hat{\gamma}_{X}(\check{Z})_{j}e^{i\alpha x_{j}}}$ (19)
$\displaystyle
w_{MN}(\alpha,\check{Z})=\frac{\sum_{j=1}^{s}m_{j}\hat{\gamma}_{M,N}(\check{Z})_{j}e^{i\alpha
n_{j}}}{\sum_{j=1}^{s}\hat{\gamma}_{N}(\check{Z})_{j}e^{i\alpha n_{j}}}$ (20)

$w_{MN}$ is the sample estimate for the integrand in $\eta$ from Eq. (16). We
can interpret the output values of $w_{MN}$ as the labels for the supervised
learning task defined by Eq. (18), the $(\alpha,\check{z})$ as inputs, and the
$\\{x_{j}\\}$ and $\hat{\lambda}_{X}$ are the parameters. As soon as we have
obtained the optimal $\\{\hat{x}_{j}\\}_{j=1}^{s}$ and $\hat{\lambda}_{X}$, we
can substitute into Eq. (13) and Eq. (14) to obtain the CME estimate
$\hat{\mu}_{{{\mathcal{P}}}_{X|z}}$.

###  4.3 Algorithm

We propose MEKIV: Measurement-Error-corrected Kernel Instrumental Variable
regression. Two independent samples are needed:
$\\{z_{j},m_{j},n_{j}\\}_{j=1}^{s_{1}}$ and
$\\{\check{z}_{j},\check{y}_{j}\\}_{j=1}^{s_{2}}$.

Thanks to Theorem 1, In step 1 of the MEKIV, we use
$\\{z_{j},m_{j},n_{j}\\}_{j=1}^{s_{1}}$ to compute the sample estimates of the
conditional kernel mean embeddings of ${{\mathcal{P}}}_{N|z}$ and
${{\mathcal{P}}}_{M,N|z}$, which in large sample size is guaranteed to
converge to the ground truth Singh et al. [2019b]. By Theorem 1, this also
gives us a sample estimate of the characteristic functions which converges in
${{\mathcal{L}}}^{2}$ of their measures induced by their respective kernels.

Step 2 of the MEKIV learns the characteristic function of $\mathcal{P}_{X|Z}$
by optimising for the $X$ samples using the training objective in Eq. (18).
Again by Theorem 1, a good estimate of the characteristic function gives us a
good estimate of the conditional kernel mean embedding.

In Step 3, MEKIV uses the learnt kernel conditional mean embedding and the
second samples $\\{\check{z}_{j},\check{y}_{j}\\}_{j=1}^{s_{2}}$ to estimate
the structural function $f$ \- equivalent to the stage 2 of the KIV (Singh et
al. [2019b]).

The pseudocode of our complete algorithm can be found in Algorithm 1 and 2 in
the Supplementary Materials.

Step 1. From the first sample $\\{z_{j},m_{j},n_{j}\\}_{j=1}^{s_{1}}$, learn
the conditional mean embedding of $p(m|z)$ and $p(m,n|z)$ using the result
stated in Eq. (2), Section 3.3:

$\displaystyle\hat{\mu}^{(s_{1})}_{{{\mathcal{P}}}_{N|z}}(\cdot)$
$\displaystyle=\sum_{j=1}^{s_{1}}(\hat{\gamma}^{(s_{1})}_{N}(z))_{j}k(n_{j},\cdot),$
(21) $\displaystyle\text{with}\hskip 8.5359pt\hat{\gamma}^{(s_{1})}_{N}(z)$
$\displaystyle=(K_{ZZ}+s_{1}\hat{\lambda}_{N}I)^{-1}K_{Zz}$ (22)

Similarly, it can be shown that:

$\displaystyle\hat{\mu}^{(s_{1})}_{{{\mathcal{P}}}_{M,N|z}}(\cdot)$
$\displaystyle=\sum_{j=1}^{s_{1}}(\hat{\gamma}_{M,N}(z))_{j}k((m_{j},n_{j}),\cdot),$
(23) $\displaystyle\text{where}\hskip 8.5359pt\hat{\gamma}^{(s_{1})}_{M,N}(z)$
$\displaystyle=(K_{ZZ}+s_{1}\hat{\lambda}_{M,N}I)^{-1}K_{Zz}$ (24)

###### Remark 2

(23) allows the use of product kernels.

Step 2. After obtaining from Step 1 the quantities: $\hat{\gamma}_{N}$ and
$\hat{\gamma}_{MN}$, Step 2 creates samples $\\{\alpha_{j}\\}$,
$\\{\check{z}_{j}\\}$ and $\\{(w_{MN})_{j}\\}$. To this end, Step 2 samples
$\\{\alpha_{j}\\}_{j=1}^{s_{2}}$ from $q(\alpha)$, and uses
$\\{\check{z}_{j}\\}_{j=1}^{s_{2}}$ unseen in Step 1. In general,
$\\{\check{z}_{j}\\}_{j=1}^{s_{2}}$ can be drawn from any distribution
${{\mathcal{P}}}_{\check{Z}}$ with the same support as ${{\mathcal{P}}}_{Z}$.
To maximize sample usage, we take all pairs in the cross product
$\\{\alpha_{j}\\}_{j=1}^{s_{2}}\times\\{z_{j}\\}_{j=1}^{s_{2}}$, giving
$(s_{2})^{2}$ pairs: $\\{\alpha_{j},\check{z}_{j}\\}_{j=1}^{(s_{2})^{2}}$ \-
here we overload notation $\\{\check{z}_{j}\\}$ to be both before and after
taking the cross product. We input each pair of
$\\{\alpha_{j},\check{z}_{j}\\}$ into Eq. (20) to generate the labels
$\\{(w_{MN})_{j}\\}_{j=1}^{(s_{2})^{2}}$. The process of sampling
$\\{\alpha_{j}\\}$ from $q(\alpha)$ has a close connection with the Random
Fourier Features literature (Bach [2017], Sriperumbudur and Szabó [2015],
Rahimi and Recht [2007]).

We now seek $\\{x_{j}\\}_{j=1}^{s_{1}}$ and $\hat{\lambda}_{X}$ in order to
minimize the following objective, which is the empirical analogue of Eq. (18):

$\displaystyle\\{\hat{x}_{j}\\}_{j=1}^{s_{1}},\hat{\lambda}_{X}$
$\displaystyle=\operatorname*{argmin}_{\\{x_{j}\\}_{j=1}^{s_{1}},\hat{\lambda}_{X}}\sum_{j=1}^{(s_{2})^{2}}\left[\left(w_{X}(\alpha_{j},\check{z}_{j})-(w_{MN})_{j}\right)^{2}\right]$
(25)

For clarity, Step 2 is illustrated in Algorithm 2 (see Supplementary
Materials).

Step 3. Given estimates of $\\{x_{j}\\}_{j=1}^{s_{1}}$ and
$\hat{\lambda}_{X}$, we obtain the empirical estimate
$\hat{\mu}_{{{\mathcal{P}}}_{X|z}}$. Along with the samples
$\\{\check{z}_{j},\check{y}_{j}\\}_{j=1}^{s_{2}}$, we obtain the solution for
$\hat{f}^{s_{1}}$. The procedure is identical to the Stage 2 estimation of KIV
Singh et al. [2019b], for which we stated the derived estimator in Section
3.3. Our solution for $f$ is:

$\displaystyle\hat{f}^{(s_{2})}(x)$
$\displaystyle=(\hat{\beta})^{\prime}K_{\hat{X}x}$ (26)
$\displaystyle\text{with }\hat{\beta}$
$\displaystyle=(VV^{\prime}+s_{2}{\hat{\xi}}K_{\hat{X}\hat{X}})^{-1}V\check{y}$
(27) $\displaystyle V$
$\displaystyle=K_{\hat{X}\hat{X}}(K_{ZZ}+s_{1}\hat{\lambda}I)^{-1}K_{Z\check{Z}}$
(28)

###  4.4 Advantages of MEKIV

We highlight the benefits of MEKIV:

  * •

MEKIV is free of distributional assumptions: as long as the measurement error
satisfies the mean-independence conditions in Eq. (9)-(11), the distributions
can have any shape.

  * •

Computational efficiency: MEKIV models only the CME of
${{\mathcal{P}}}_{X|Z}$, and in particular, no modelling of the full joint
distribution ${{\mathcal{P}}}_{X|Z,M,N}$ as is commonly done in standard
latent variable modelling.

  * •

Ease of implementation: Unlike standard latent variable modelling, which is
typically hard to train due to the large number of hyperparameters, MEKIV is
easy to implement and works stably without large efforts in tuning.

##  5 Experiments

Figure 3: Out of sample MSEs ($\log_{10}$) for linear and sigmoid designs.
Figure 4: Out of sample MSEs ($\log_{10}$) for demand design.

In this section we evaluate the empirical performance of MEKIV across multiple
designs and against baselines. In particular, we compare to three baselines:
A) KernelIV Singh et al. [2019b] with ground truth X provided from an oracle
(KIV-Oracle); B) KernelIV taking $M$ as the true treatment observations
(KIV-M); C) since taking the average of independent errors reduces the error
variance, we also compare with KernelIV taking $(M+N)/2$ as the true treatment
observations (KIV-MN).

We run each estimator on three designs. The linear design Chen and Christensen
[2017] involves learning the structural function $f(x)=4x-2$, where $X$ is
unseen and we are only given corrupted measurements of treatment $(M,N)$,
continuous instrument $Z$, and observations of outcome variables $Y$ which is
confounded with the true treatments $X$. The sigmoid design Chen and
Christensen [2017] involves learning the structural $f(x)=\ln(|16x-8|+1)\cdot
sgn(x-0.5)$ under the same data generating process otherwise. The demand
design Hartford et al. [2017] involves learning demand function
$h(p,t,s)=100+(10+p)\cdot s\cdot\psi(t)-2p$ where $\psi(t)$ is a complicated
nonlinear function. A data tuple including the ground truth treatments
consists of $(Y,P,T,S,C)$ where $Y$ is sales, $P$ is price, $T$ is time of
year, $S$ is customer sentiment (a discrete variable), and $C$ parameterizes
the supply cost shift. A parameter $\rho\in\\{0.25,0.5,0.9\\}$ calibrates the
confounding level of $P$ by supply-side market forces. We set
$X\vcentcolon=(P,T,S)$ and instruments are $Z\vcentcolon=(C,T,S)$.

Since the originally proposed design is one where $X$ is observed, we
construct $M$ and $N$ from $X$ and we mask $X$ from all algorithms except KIV-
Oracle. For the demand design where $X$ is 3-dimensional, we mask only the
dimension corresponding to $P$. For each design we construct $M$ and $N$ from
adding noise on $X$. We analyze the robustness of MEKIV in two dimensions.
First, we vary the measurement error distribution: we implement a Gaussian
additive noise design and a multi-modal Mixture of Gaussian additive noise
design where we mix two Gaussian distributions, centred at twice the standard
deviation of $X$ away from 0 on either side. Second, for each measurement
error distribution, we vary their standard deviation. For both designs, we set
the standard deviation of the Gaussian(s) to be $\\{0.5,1,2\\}$ times the
standard deviation of the ground truth $X$.

For the linear and sigmoid design, we implement 30 simulations for each
algorithm, measurement error distribution (merror type) and measurement error
standard deviation (merror level). For the demand dataset, due to time
constraints, we implement 30 simulations for the Mixture of Gaussian
measurement error distribution and 10 for the Gaussian distribution, for each
algorithm and measurement error standard deviation. We calculate MSE with
respect to the true structural function $f$. Figure 3, 4 and Figure 6
(Supplementary Materials) plots the results in each design, measurement error
distribution type, and measurement error level. We expect KIV-Oracle to be the
best across all methods and its performance is viewed as an upper bound for
the other algorithms. MEKIV beats all other baselines in the highest
measurement error level setting and is robust to non-classical measurement
error as demonstrated by its performance under Mixture of Gaussian error.

##  6 Exemplary Real World Scenarios

Measurement error from survey data: effect of income on children’s cognitive
outcome. Dahl and Lochner [2012] investigated the impact of family income on
children’s development. The primary concern with using a regression-type
method is that family income and children’s development is confounded by other
family characteristics, such as parents’ cognitive ability. Dahl and Lochner
thus proposed the state’s Earned Income Tax Credit (EITC) scheme as an
instrumental variable to correct for the confounding. Here, they exploit the
fact that the EITC scheme expands over the years, so, via this, they can
capture the variation of total family income independent from that caused by
intrinsic family characteristics. They base their analysis on the panel
dataset in the Children of the National Longitudinal Survey of Youth. Survey
data are known to contain measurement errors (Carroll et al. [2006]).
Moreover, the family income measured by the survey in two consecutive years
can be posed as repeated measurements of true total family income - assuming
that family income is a stable variable that does not vary drastically over a
short number of years. Moreover, Dahl and Lochner [2012] took a linear model
approach for simplicity, but our method can be used for a nonlinear analysis.
We apply our method to this dataset and discuss the experiment in detail in
Supplementary Materials.

In conclusion, we find that EITC as an instrument is weak, so we prescribe
that for a meaningful analysis of the hypothesis of income-on-
children’s-outcome, a stronger perturbation on the income is required. For
example, this can be done by selecting a neighbourhood for which the strength
of EITC parameters is increased for some number of years.

###  6.1 Understanding how student skills impact their long-term outcome

We consider the following thought experiment: an education trial may take
place such that the teachers exercise certain educational strategies to
improve the skills of students, in the hopes of ultimately improving their
long-term outcome. Such an educational strategy may be the introduction of
challenging science projects; this would be $Z$. This may be hypothesized to
encourage the students to understand taught concepts better and apply their
knowledge to more complex scenarios. The resultant short-term changes in these
skills ($X$) may be measured by test scores ($M$, $N$), which contain
measurement error. The project should then follow the cohort of students to
see what they achieve years later when they reach adulthood ($Y$). We may then
run our method to determine the nonlinear causal relationship from skills,
such as logical thinking and creative application of knowledge, to long-term
outcomes.

##  7 Conclusion and Future Work

We propose MEKIV, an instrumental variable approach for confounded structural
learning when the treatment variable is measured with error. We clarify a
connection between mean embedding learning and characteristic function
learning, showing that the two can be done simultaneously. In constructing our
algorithm, we introduce the ‘differentiation trick’ which allows target
function recovery while avoiding the computation of an intractable integral.
Our method performs well on both Gaussian and non-Gaussian measurement error,
and is robust over increasing measurement error levels.

Our method should work well when interventional data is present, but when only
purely observational data is present, the instrumental variable assumption may
need to be relaxed. This is due to the rarity of instrumental variables in
observational studies - instrumental variables in observational studies are
often weak, and in some cases they might not even be valid. We leave this for
future work. Nevertheless, the ubiquity of instrumental variable assumptions
suggests that our approach should be widely applicable; our proposed
methodology connecting kernel learning and characteristic function learning
also carries independent interest and may find applications outside of the
topic of treatment effect estimation considered in this paper.

#### Acknowledgements

We are grateful to Amlan Banaji and François-Xavier Briol for their insightful
comments. We also thank the reviewers for the thoughtful reviews. YZ
acknowledges support by the Engineering and Physical Sciences Research Council
with grant number EP/S021566/1. This work was partially supported by an ONR
grant number N62909-19-1-2096 to RS.

## References

  * Agarwal and Singh [2021] A. Agarwal and R. Singh.  Causal inference with corrupted data: Measurement error, missing values, discretization, and differential privacy.  _arXiv:2107.02780_ , 2021.
  * Allman et al. [2009] E. S. Allman, C. Matias, and J. A. Rhodes.  Identifiability of parameters in latent structure models with many observed variables.  _Annals of Statistics_ , 37(6A):3099–3132, 2009\.
  * Bach [2017] Francis Bach.  On the equivalence between kernel quadrature rules and random feature expansions.  _J. Mach. Learn. Res._ , 18(1):714–751, jan 2017\.  ISSN 1532-4435.
  * Balke and Pearl [1994] A. Balke and J. Pearl.  Counterfactual probabilities: Computational methods, bounds and applications.  _Proceedings of the Tenth Conference on Uncertainty in Artificial Intelligence (UAI1994)_ , pages 46–54, 1994.
  * Battistin and Chesher [2014] Erich Battistin and Andrew Chesher.  Treatment effect estimation with covariate measurement error.  _Journal of Econometrics_ , 178(2):707–715, 2014\.
  * Bennett et al. [2019] Andrew Bennett, Nathan Kallus, and Tobias Schnabel.  Deep generalized method of moments for instrumental variable analysis.  In _Advances in Neural Information Processing Systems 32_ , pages 3564–3574. Curran Associates, Inc., 2019.
  * Bollen [1989] K. Bollen.  _Structural Equations with Latent Variables_.  Wiley & Sons, 1989.
  * Carroll et al. [2006] R.J. Carroll, D. Ruppert, L.A. Stefanski, and C.M. Crainiceanu.  _Measurement Error in Nonlinear Models: A Modern Perspective, Second Edition_.  Chapman & Hall/CRC Monographs on Statistics & Applied Probability. CRC Press, 2006.  ISBN 9781420010138.  URL https://books.google.co.uk/books?id=9kBx5CPZCqkC.
  * Chen and Christensen [2017] Xiaohong Chen and Timothy M. Christensen.  Optimal sup-norm rates and uniform inference on nonlinear functionals of nonparametric iv regression, 2017.
  * Dahl and Lochner [2012] Gordon B. Dahl and Lance Lochner.  The impact of family income on child achievement: Evidence from the earned income tax credit.  _American Economic Review_ , 102(5):1927–56, May 2012.  10.1257/aer.102.5.1927.  URL https://www.aeaweb.org/articles?id=10.1257/aer.102.5.1927.
  * Finkelstein et al. [2021] N. Finkelstein, R. Adams, S. Saria, and I. Shpitser.  Partial identifiability in discrete data with measurement error.  In _Proceedings of the 37th Conference on Uncertainty in Artificial Intelligence_ , PMLR 161, page 1798–1808, 2021.
  * Fukumizu [2008] Kenji Fukumizu.  Elements of positive definite kernels and reproducing kernel hilbert spaces, October 2008.
  * Ghassami et al. [2022] A. Ghassami, A. Ying, I. Shpitser, and E Tchetgen Tchetgen.  Minimax kernel machine learning for a class of doubly robust functionals with application to proximal causal inference.  In _Proceedings of the 25th International Conference on Artificial Intelligence and Statistics_ , 2022.
  * Gultchin et al. [2021] Limor Gultchin, David Watson, Matt Kusner, and Ricardo Silva.  Operationalizing complex causes: A pragmatic view of mediation.  In Marina Meila and Tong Zhang, editors, _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pages 3875–3885. PMLR, 18–24 Jul 2021.  URL https://proceedings.mlr.press/v139/gultchin21a.html.
  * Hartford et al. [2017] Jason Hartford, Greg Lewis, Kevin Leyton-Brown, and Matt Taddy.  Deep IV: A flexible approach for counterfactual prediction.  In _Proceedings of the 34th International Conference on Machine Learning_ , volume 70, pages 1414–1423. PMLR, 2017.
  * Hernán and Robins [2020] M. A. Hernán and J. M. Robins.  _Causal Inference: What If_.  Chapman & Hall/CRC, 2020.
  * Hu and Sasaki [2015] Yingyao Hu and Yuya Sasaki.  Closed-form estimation of nonparametric models with non-classical measurement errors.  _Journal of Econometrics_ , 185(2):392–408, 2015\.  ISSN 0304-4076.  https://doi.org/10.1016/j.jeconom.2014.11.004.  URL https://www.sciencedirect.com/science/article/pii/S0304407614002796.
  * Kallus et al. [2018] Nathan Kallus, Xiaojie Mao, and Madeleine Udell.  Causal inference with noisy and missing covariates via matrix factorization.  _Advances in neural information processing systems_ , 31, 2018.
  * Kuroki and Pearl [2014] Manabu Kuroki and Judea Pearl.  Measurement bias and effect restoration in causal inference.  _Biometrika_ , 101(2):423–437, 03 2014.  ISSN 0006-3444.  10.1093/biomet/ast066.  URL https://doi.org/10.1093/biomet/ast066.
  * Mastouri et al. [2021] A. Mastouri, Y. Zhu, L. Gultchin, A. Korba, R. Silva, M. Kusner, A. Gretton, and K. Muandet.  Proximal causal learning with kernels: Two-stage estimation and moment restriction.  In _Proceedings of the 38th International Conference on Machine Learning_ , PMLR 139, pages 7512–7523, 2021.
  * Miao et al. [2018] Wang Miao, Zhi Geng, and Eric J Tchetgen Tchetgen.  Identifying causal effects with proxy variables of an unmeasured confounder.  _Biometrika_ , 105(4):987–993, 08 2018.  ISSN 0006-3444.  10.1093/biomet/asy038.  URL https://doi.org/10.1093/biomet/asy038.
  * Muandet et al. [2017] Krikamol Muandet, Kenji Fukumizu, Bharath Sriperumbudur, and Bernhard Schölkopf.  Kernel mean embedding of distributions: A review and beyond.  _Foundations and Trends in Machine Learning_ , 10(1-2):1–141, 2017.
  * Pearl [2009] Judea Pearl.  _Causality_.  Cambridge University Press, 2nd edition, 2009.
  * Rahimi and Recht [2007] Ali Rahimi and Benjamin Recht.  Random features for large-scale kernel machines.  In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, _Advances in Neural Information Processing Systems_ , volume 20. Curran Associates, Inc., 2007.  URL https://proceedings.neurips.cc/paper/2007/file/013a006f03dbc5392effeb8f18fda755-Paper.pdf.
  * Schennach [2004] Susanne M. Schennach.  Estimation of nonlinear models with measurement error.  _Econometrica_ , 72(1):33–75, 2004.  ISSN 00129682, 14680262.  URL http://www.jstor.org/stable/3598849.
  * Schennach [2016] Susanne M. Schennach.  Recent advances in the measurement error literature.  _Annual Review of Economics_ , 8(1):341–377, 2016\.  10.1146/annurev-economics-080315-015058.  URL https://doi.org/10.1146/annurev-economics-080315-015058.
  * Silva et al. [2006] R. Silva, R. Scheines, C. Glymour, and P. Spirtes.  Learning the structure of linear latent variable models.  _Journal of Machine Learning Research_ , 7:191–246, 2006\.
  * Singh et al. [2019a] Rahul Singh, Maneesh Sahani, and Arthur Gretton.  Kernel instrumental variable regression.  In _Advances in Neural Information Processing Systems_ , pages 4595–4607, 2019a.
  * Singh et al. [2019b] Rahul Singh, Maneesh Sahani, and Arthur Gretton.  Kernel instrumental variable regression.  In _Advances in Neural Information Processing Systems_ , pages 4595–4607, 2019b.
  * Smola et al. [2007] Alexander J. Smola, Arthur Gretton, Le Song, and Bernhard Schölkopf.  A Hilbert space embedding for distributions.  In _Proceedings of the 18th International Conference on Algorithmic Learning Theory (ALT)_ , pages 13–31. Springer-Verlag, 2007.
  * Song et al. [2009] Le Song, Jonathan Huang, Alex Smola, and Kenji Fukumizu.  Hilbert space embeddings of conditional distributions with applications to dynamical systems.  In _Proceedings of the 26th Annual International Conference on Machine Learning_ , pages 961–968, 2009.
  * Song et al. [2013] Le Song, Kenji Fukumizu, and Arthur Gretton.  Kernel embeddings of conditional distributions: A unified kernel framework for nonparametric inference in graphical models.  _IEEE Signal Processing Magazine_ , 30(4):98–111, 2013.
  * Song et al. [2015] S. Song, S. M. Schennach, and H. White.  Estimating nonseparable models with mismeasured endogenous variables.  _Quantitative Economics_ , 6:749–794, 2015.
  * Sriperumbudur and Szabó [2015] Bharath K. Sriperumbudur and Zoltán Szabó.  Optimal rates for random fourier features.  In _Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 1_ , NIPS’15, page 1144–1152, Cambridge, MA, USA, 2015. MIT Press.
  * Vansteelandt et al. [2009] Stijn Vansteelandt, Manoochehr Babanezhad, and Els Goetghebeur.  Correcting instrumental variables estimators for systematic measurement error.  _Statistica Sinica_ , 19:1223–1246, 07 2009.
  * Xu et al. [2020] Liyuan Xu, Yutian Chen, Siddarth Srinivasan, Nando Freitas, Arnaud Doucet, and Arthur Gretton.  Learning deep features in instrumental variable regression.  10 2020.
  * Zhang et al. [2018] K. Zhang, M. Gong, J. Ramsey, K. Batmanghelich, P. Spirtes, and C. Glymour.  Causal discovery with linear non-gaussian models under measurement error: Structural identifiability results.  In _Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence_ , 2018.
  * Zhang et al. [2020] Rui Zhang, Masaaki Imaizumi, Bernhard Schölkopf, and Krikamol Muandet.  Maximum moment restriction for instrumental variable regression.  _arXiv preprint arXiv:2010.07684_ , 2020.

##  Appendix A Pseudocode

See Figure 5 for the pseudocode of our method.

Algorithm 1 MEKIV training

Input: $M_{1}$, $M_{2}$, $N_{1}$, $N_{2}$, $Z_{1}$, $Z_{2}$, $Y_{1}$, $Y_{2}$
, kernelType:=RBF kernel

Step 1 Input: $M_{1}$, $N_{1}$, $Z_{1}$, kernelType

1:$\hat{\gamma}_{N}\leftarrow$ KRR($N_{1},Z_{1}$, kernelType) [Singh et al.,
2019a, Stage 1 estimate]

2:Stack $M_{1}$ and $N_{1}$ to get $M_{1}N_{1}$.

3:$\hat{\gamma}_{MN}\leftarrow$ KRR($M_{1}N_{1},Z_{1}$, kernelType)

4:return $\hat{\gamma}_{MN},\hat{\gamma}_{N}$

5:

Step 2 Input: kernelType, $\gamma_{N}^{(s_{1})}$, $\gamma_{MN}^{(s_{1})}$,
$M_{1}$, $N_{1}$, $Z_{2}$, number of $\alpha$ samples $\vcentcolon=C$,

1:Take $q(\alpha)$ as the Inverse Fourier Transform of the kernel rescaled by
$\frac{1}{2\pi}$.

2:Take $\\{\check{z}_{j}\\}_{j=1}^{s_{2}}$ to be the set of data points in
$Z_{2}$.

3:$\\{\hat{x}_{j}\\}_{j=1}^{s_{1}},\hat{\lambda}_{X}\leftarrow$
OptimiseX1($q(\alpha)$, $\gamma_{N}^{(s_{1})}$, $\gamma_{MN}^{(s_{1})}$,
$M_{1}$, $N_{1}$, $\\{\check{z}_{j}\\}_{j=1}^{s_{2}}$, $C$)

4:return $\\{\hat{x}_{j}\\}_{j=1}^{s_{1}},\hat{\lambda}_{X}$

5:

Step 3 Input: $\\{\hat{x}_{j}\\}_{j=1}^{s_{1}},\hat{\lambda}_{X}$, $Y_{2}$,
$Z_{2}$, $Z_{1}$

1:$\xi\leftarrow$ KIVStage2Validation [Singh et al., 2019a, A.5.2]

2:$\hat{f}\leftarrow$
KIVStage2($\\{\hat{x}_{j}\\}_{j=1}^{s_{1}},\hat{\lambda}_{X}$, $Y_{2}$,
$Z_{2}$, $Z_{1}$, $\xi$)

3:return $\hat{f}$

Algorithm 2 Step 2: Learning the CME for $\mathcal{P}_{X|Z}$

Input: $q(\alpha)$, $\gamma_{N}^{(s_{1})}$, $\gamma_{MN}^{(s_{1})}$, $M_{1}$,
$N_{1}$, number of $\alpha$ samples $\vcentcolon=s_{2}$,
$\\{\check{z}_{j}\\}_{j=1}^{s_{2}}$,

1:function OptimiseX1

2: $\\{\alpha_{j},\check{z}_{j},(w_{MN})_{j}\\}_{j=1}^{(s_{2})^{2}}$ =
CreateTrainData($q(\alpha)$, $\hat{\gamma}_{N}$, $\hat{\gamma}_{MN}$, $M_{1}$,
$N_{1}$ )

3: initialize $\hat{X}=(M_{1}+N_{1})/2$

4: initialize $\hat{\lambda}_{X}=\hat{\lambda}_{N}$

5: while not converged do

6: Use Eq. (19) to calculate $\\{(w_{X})_{j}\\}_{j=1}^{(s_{2})^{2}}$ from
$\\{\alpha_{j},\check{z}_{j}\\}_{j=1}^{(s_{2})^{2}}$.

7: Compute loss = MSE($\\{(w_{X})_{j},(w_{MN})_{j}\\}_{j=1}^{(s_{2})^{2}}$)
$\triangleright$ Eq.(25)

8: Compute $\nabla_{\hat{X}}(loss)$, $\nabla_{\hat{\lambda}_{X}}(loss)$

9: $\hat{X}\leftarrow\hat{X}-\text{step}\times\nabla_{\hat{X}}(loss)$;
$\hat{\lambda}_{X}\leftarrow\hat{\lambda}_{X}-\text{step}\times\nabla_{\hat{\lambda}_{X}}(loss)$

10: end while

11:return $\hat{X}$, $\hat{\lambda}_{X}$

12:end function

13:

14:function CreateTrainData

15: Sample $\\{\alpha_{j}\\}_{j=1}^{C}$ from $q(\alpha)$

16: Take all pairs in
$\\{\alpha_{j}\\}_{j=1}^{C}\times\\{\check{z}_{j}\\}_{j=1}^{s_{2}}$ to get
$\\{(\alpha_{j},\check{z}_{j})\\}_{j=1}^{C\times s_{2}}$

17: Substitute $\\{(\alpha_{j},\check{z}_{j})\\}_{j=1}^{C\times s_{2}}$, along
with $M_{1}$, $N_{1}$, $\hat{\gamma}_{N}$, $\hat{\gamma}_{MN}$ into Eq. (20)
to calculate the labels $\\{w_{j}\\}_{j=1}^{C\times s_{2}}$.

18:return $\\{\alpha_{j},\check{z}_{j},w_{j}\\}_{j=1}^{C\times s_{2}}$

19:end function

Figure 5: Our proposed algorithm. Algorithm 1 outlines the end-to-end
algorithm from training data to the structural estimator $\hat{f}$. Algorithm
2 outlines our main contribution, step 2 of the algorithm where we learn the
CME for the latent variable $X$.

##  Appendix B Relaxing classical measurement error assumptions

In Hu and Sasaki [2015], the authors assume the noise on the second
measurement $N$, is an unknown monotonic polynomial function of $X$ with
additive noise. The estimation procedure amounts of first identifying the
polynomial function of $X$, before applying a technique similar to Schennach
[2004]. In this work we take the first step to extend the estimator of
Schennach [2004] to the confounded setting, and leave for future work the
relaxation on the assumptions of the second measurement.

##  Appendix C Further assumptions on kernel identification

We also employ the following technical assumptions to enable causal effect
estimation in the latent treatment setting.

###### Assumption 8

$\mathcal{Z,X,M,N,Y}$ are measurable, separable Polish spaces.

Assumption 8 is a regularity condition that allows us to define the
conditional mean embedding operator.

###### Assumption 9

$Y$ is bounded.

###### Assumption 10

$k(x,\cdot),k(m,\cdot),k(n,\cdot)$ are continuous, bounded by $\kappa>0$, and
their feature maps are measurable. (ii) $k(x,\cdot),k(m,\cdot),k(n,\cdot)$ are
characteristic kernels.

Assumption 10 is a standard assumption employed in kernel causal learning
(Singh et al. [2019a] Mastouri et al. [2021]).

##  Appendix D $s-$sample estimates

For clarity, we state the $s-$sample estimates for
$\hat{\psi}_{{{\mathcal{P}}}_{X|z}}(\alpha)$,
$\hat{\psi}_{{{\mathcal{P}}}_{N|z}}(\alpha)$,
$\hat{\psi}_{{{\mathcal{P}}}_{M,N|z}}(\upsilon,\alpha)$, which are obtained
from Kernel Ridge Regression, and the relevant derivatives below:

$\displaystyle\hat{\psi}_{{{\mathcal{P}}}_{X|z}}(\alpha)$
$\displaystyle=\sum_{j=1}^{s}\hat{\gamma}_{X}(z)_{j}e^{i\alpha x_{j}}$ (29)
$\displaystyle\hat{\psi}_{{{\mathcal{P}}}_{N|z}}(\alpha)$
$\displaystyle=\sum_{j=1}^{s}\hat{\gamma}_{X}(z)_{j}e^{i\alpha n_{j}}$ (30)
$\displaystyle\hat{\psi}_{{{\mathcal{P}}}_{M,N|z}}(\alpha)$
$\displaystyle=\sum_{j=1}^{s}\hat{\gamma}_{M,N}(z)_{j}e^{i(\upsilon
m_{j}+\alpha n_{j})}$ (31)

With:

$\displaystyle\hat{\gamma}_{X}(z)$
$\displaystyle=(K_{ZZ}+s\hat{\lambda}_{X}I)^{-1}K_{Zz}$ (32)
$\displaystyle\hat{\gamma}_{N}(z)$
$\displaystyle=(K_{ZZ}+s\hat{\lambda}_{N}I)^{-1}K_{Zz}$ (33)
$\displaystyle\hat{\gamma}_{M,N}(z)$
$\displaystyle=(K_{ZZ}+s\hat{\lambda}_{M,N}I)^{-1}K_{Zz}$ (34)

And the derivatives:

$\displaystyle\frac{\partial}{\partial\alpha}\hat{\psi}_{{{\mathcal{P}}}_{X|z}}(\alpha)$
$\displaystyle=\sum_{j=1}^{s}ix_{j}\hat{\gamma}_{X}(z)_{j}e^{i\alpha x_{j}}$
(35)
$\displaystyle\frac{\partial}{\partial\upsilon}\bigg{|}_{\upsilon=0}\hat{\psi}_{{{\mathcal{P}}}_{M,N|z}}(\alpha,\upsilon)$
$\displaystyle=\sum_{j=1}^{s}im_{j}\hat{\gamma}_{M,N}(z)_{j}e^{i\alpha n_{j}}$
(36)

##  Appendix E Demand design - further results

(a) $\rho=0.25$

(b) $\rho=0.5$

(c) $\rho=0.9$

Figure 6: Demand design - Gaussian Measurement Error.

See Figure 6 for further results on Demand design with Gaussian measurement
error.

##  Appendix F Proofs

Proof of Theorem 1.

###### Proof.

First we note that by Fubini’s theorem the Fourier Transform of the (ground
truth) conditional mean embedding $\mu_{{{\mathcal{P}}}_{X|z}}$ can be
computed as:

$\displaystyle\tilde{\mu}_{{{\mathcal{P}}}_{X|z}}(\alpha)$
$\displaystyle=q(\alpha)\psi_{{{\mathcal{P}}}_{X|z}}(-\alpha)$ (37)

$\displaystyle\|\hat{\mu}_{\mathcal{P}_{X|z}}^{(s)}-\mu_{\mathcal{P}_{X|z}}\|_{{{\mathcal{H}}}_{{{\mathcal{X}}}}}$
(38)
$\displaystyle=\int_{-\infty}^{\infty}\frac{\left|\tilde{\hat{\mu}}_{\mathcal{P}_{X|z}}^{(s)}(\alpha)-\tilde{\mu}_{\mathcal{P}_{X|z}}(\alpha)\right|^{2}}{q(\alpha)}d\alpha$
(39)
$\displaystyle=\int_{-\infty}^{\infty}q(\alpha)\left|\hat{\psi}_{\mathcal{P}_{X|z}}^{(s)}(-\alpha)-\psi_{\mathcal{P}_{X|z}}(-\alpha)\right|^{2}d\alpha$
(40)

Since $k$ is a symmetric kernel i.e. even function,
$q(\alpha)=\frac{1}{2\pi}\tilde{k}(\alpha)$ is a real and even measure, so

$\displaystyle\int_{-\infty}^{\infty}q(\alpha)\left|\hat{\psi}_{\mathcal{P}_{X|z}}^{(s)}(-\alpha)-\psi_{\mathcal{P}_{X|z}}(-\alpha)\right|^{2}d\alpha$
(41)
$\displaystyle=\int_{-\infty}^{\infty}q(\alpha)\left|\hat{\psi}_{\mathcal{P}_{X|z}}^{(s)}(\alpha)-\psi_{\mathcal{P}_{X|z}}(\alpha)\right|^{2}d\alpha$
(42)
$\displaystyle=\|\hat{\psi}_{\mathcal{P}_{X|z}}^{(s)}(\alpha)-\psi_{\mathcal{P}_{X|z}}(\alpha)\|_{\mathcal{L}^{2}(\mathbb{R},q)}$
(43)

Consequentially, whenever
$\|\hat{\mu}_{\mathcal{P}_{X|z}}^{(s)}-\mu_{\mathcal{P}_{X|z}}\|_{{{\mathcal{H}}}_{{{\mathcal{X}}}}}<\epsilon$,
$\|\hat{\psi}_{\mathcal{P}_{X|z}}^{(s)}-\psi_{\mathcal{P}_{X|z}}\|_{\mathcal{L}^{2}(\mathbb{R},q)}<\epsilon.$
and vice versa. Therefore,
$\hat{\psi}^{(s)}_{\mathcal{P}_{X|z}}\longrightarrow\psi_{\mathcal{P}_{X|z}}$
in $\mathcal{L}^{2}(\mathbb{R},q)$ if and only if
$\hat{\mu}_{\mathcal{P}_{X|z}}^{(s)}\longrightarrow\mu_{\mathcal{P}_{X|z}}$ in
$\mathcal{H_{X}}$. Moreover, if they converge, the convergence happen at the
same rate. ∎

Proof of Theorem 2.

###### Proof.

Since there is a bijection between characteristic functions and probability
distributions, we only have to show that the characteristic function
satisfying Eq. (17) is unique.

Now Eq. (17) can be rewritten as

$\displaystyle\frac{d\psi_{{{\mathcal{P}}}_{X|\check{z}}}(\alpha)/d\alpha}{\psi_{{{\mathcal{P}}}_{X|\check{z}}}(\alpha)}$
$\displaystyle=ig(\alpha)$ (44)
$\displaystyle\frac{d}{d\alpha}\log(\psi_{{{\mathcal{P}}}_{X|\check{z}}}(\alpha))$
$\displaystyle=ig(\alpha)$ (45) $\displaystyle\text{with }g(\alpha)$
$\displaystyle=\frac{{{\mathbb{E}}}[Me^{i\alpha
N}|\check{z}]}{{{\mathbb{E}}}[e^{i\alpha N}|\check{z}]}$ (46)

Now suppose there is another characteristic function $\psi(\alpha)$ which also
satisfies Eq. (17) for all $\alpha\in{{\mathbb{R}}}$, i.e.

$\displaystyle\frac{d}{d\alpha}\log(\psi(\alpha))$ $\displaystyle=ig(\alpha)$
(47)

Let $f(\alpha)=\log(\psi_{{{\mathcal{P}}}_{X|z}}(\alpha))$,
$g(\alpha)=\log(\psi(\alpha))$. $f^{\prime}=g^{\prime}$. But since
characteristic functions are always $1$ at $\alpha=0$, $f(0)=g(0)=\log(1)=0$.
So by Lemma 1 $f=g$. Since $\log$ is an invertible function whose inverse is
$\exp$, we must have $\psi_{{{\mathcal{P}}}_{X|z}}=\exp(f)=\exp(g)=\psi$. i.e.
the solution to Eq. (17) is unique. ∎

##  Appendix G Real-world experiment: Income on children’s outcome

Method | MSE
---|---
KIV-Oracle | 0.0345 $\pm$ 0.0190
MEKIV | 0.0295 $\pm$ 0.0144
KIV-M | 0.0318 $\pm$ 0.0199
KIV-MN | 0.0310 $\pm$ 0.0142
Table 1: MSE, income-on-children’s-outcome data

As described in Section 6 of the main paper, we apply our algorithm to the
dataset described in Dahl and Lochner [2012]. In order to obtain causal ground
truth, we fit a simulation model to the observed data, obtaining the
structural equation $f$. We then generate data from the fitted simulation
model, for which we now have access to causal ground truth. We then run MEKIV
along with the baselines on the generated dataset. Table 1 present the
results. We observe that the performance across all methods do not differ
much, and in particular the perturbations around the average MSE overlap. This
prompts us to look into the performance of the learnt estimators and we plot
the estimated ${{\mathbb{E}}}[Y|do(A)]$ in Figure 7. In Figure 7, we observe
that in fact none of the methods work well, including KIV-oracle. This
suggests that the instrumental variable is only weakly associated with the
input. A simple analysis on the dataset suggests exactly this: the average
increase in average yearly income from 1985 to 2000 is around $2000, whereas
the largest increase between the EITC credit rate of two consecutive years is
about 10%, which corresponds to only a 10% portion of the increase in income.

Figure 7: Dahl-Lochner Income on Cognitive outcome


# Existence of flipped orthogonal conjugate symmetric Jordan canonical bases
for real $H$-selfadjoint matrices

S. Dogruer Akgul  A. Minenkova  V. Olshevsky  Department of Mathematics,
University of Connecticut, Storrs CT 06269-3009, USA. Email:
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

For real matrices selfadjoint in an indefinite inner product there are two
special canonical Jordan forms, that is (i) flipped orthogonal (FO) and (ii)
$\gamma$-conjugate symmetric (CS). These are the classical Jordan forms with
certain additional properties induced by the fact that they are
$H$-selfadjoint. In this paper we prove that for any real $H$-selfadjoint
matrix there is a $\gamma$-FOCS Jordan form that is simultaneously flipped
orthogonal and $\gamma$-conjugate symmetric.

###### keywords:

Canonical Jordan bases , Indefinite inner product , $H$-selfadjoint matrices

††journal: TBD

##  1 Introduction

###  1.1 $H$-selfadjoint matrices and the affiliation relation

Let $[\cdot,\cdot]$ denote the indefinite inner product, that is
$[\cdot,\cdot]$ satisfies all the axioms of the usual inner product except for
positivity.

For example, for every $n\times n$ invertible hermitian matrix $H$

$[x,y]_{H}=y^{*}Hx,\,\text{ for }x,y\in\mathbb{C}^{n}$ (1.1)

determines an indefinite inner product. Conversely, for any indefinite inner
product we can find such $H$ that (1.1) holds true. If $H$ is positive-
definite then $[\cdot,\cdot]_{H}$ is a classical inner product, but in what
follows we assume that $H$ is just Hermitian.

H-selfadjoint matrices. A matrix $A$ is called H-selfadjoint if

$A=H^{-1}A^{*}H\text{ (or $[Ax,y]_{H}=[x,Ay]_{H}$)}.$ (1.2)

These matrices have many applications and have been studied by many authors
(e.g. see [2] and many references therein).

If follows from (1.2) that $H$-selfadjoint matrices have eigenvalues symmetric
about the real axis. Moreover, the sizes of Jordan blocks for the conjugate
eigenvalues are the same.

Affiliation relation.  Let us consider the change of basis

$x\mapsto u=T^{-1}x,\quad y\mapsto v=T^{-1}y.$

It follows that

$[x,y]_{H}=y^{*}Hx=(Tv)^{*}H(Tu)=v^{*}\overset{G}{\overbrace{(T^{*}HT)}}u=[u,v]_{G}.$

Therefore, if $T$ is a change of basis matrix, then in the new basis the same
inner product is given by a new congruent matrix $G=T^{*}HT$.

Two pairs $(A,H)$ and $(B,G)$ are called affiliated if

$T^{-1}AT=B\text{ and }T^{*}HT=G.$

The relation $(A,H)\overset{T}{\mapsto}(B,G)$ is called the affiliation
relation. That is, if we change the basis, the first matrix in a new basis is
similar (as in the general case), but the second is congruent as described
above.

Note that that the affiliation relation preserves selfadjointness in the
indefinite inner product, that is if $A$ is $H$-selfadjoint, then $B$ is
$G$-selfadjoint.

As to canonical forms, in the $H$-selfadjoint case we are looking for the
affiliation $(A,H)\mapsto(J,P)$ where not only $J$ is the Jordan form but also
$P$ has a certain simple form. One example of such a form is considered next.

###  1.2 Flipped-Orthogonal Bases

Let us consider the following example

$A=\begin{bmatrix}0&1&0&0\\\ 0&0&1&0\\\ 0&0&0&1\\\
-1&0&-2&0\end{bmatrix}=TJT^{-1},\quad H=\begin{bmatrix}0&2&0&1\\\ 2&0&1&0\\\
0&1&0&0\\\ 1&0&0&0\end{bmatrix},$ (1.3)

where $A=H^{-1}A^{*}H$ and

$J=\left[\begin{array}[]{cc|cc}i&1&0&0\\\ 0&i&0&0\\\ \hline\cr 0&0&-i&1\\\
0&0&0&-i\end{array}\right],\quad P=\left[\begin{array}[]{cc|cc}0&0&0&1\\\
0&0&1&0\\\ \hline\cr 0&1&0&0\\\ 1&0&0&0\end{array}\right],$ (1.4)

and

$T=\frac{1}{2}\begin{bmatrix}-i&0&i&1\\\ 1&-i&1&0\\\ i&2&-i&1\\\
-1&3i&-1&-2i\end{bmatrix}.$ (1.5)

Moreover, $J=P^{-1}J^{*}P$ and $P=T^{*}HT$, so that

$(A,H)\overset{T}{\mapsto}(J,P).$

This is a very special affiliation relation, since $(J,P)$ is of a particular
form with $J$ being the Jordan canonical form of $A$, and $P$ was called the
sip matrix in [2, Section 5.5], which is uniquely defined up-to perturbation
of the Jordan blocks in $J$.

Thus, $(J,P)$ is a canonical form. It first appeared in the works by
Weierstrass [5, 6] (see also [2, Chapter 5] and [4, Chapter 3]). It can be
seen that the columns of $T=[t_{i}]$ satisfy

$[t_{i},t_{j}]_{H}=[e_{i},e_{j}]_{P}=\delta_{i,4-j},$

where $\delta_{i,j}$ is the Kronecker symbol. Therefore, we suggest to call
the Jordan basis $\\{t_{1},\ldots,t_{n}\\}$ flipped orthogonal in agreement
with its usage in [1].

###  1.3 $\gamma$-Conjugate Symmetric Bases

While the above definitions were given for the general complex case, in this
paper we focus on the case, where $A$ and $H$ are real.

Are there any canonical forms for the real case?

One immediate example is given next. Here the matrices $A$ and $H$ are the
same as in (1.3).

Let us consider another Jordan basis for $A$.

$R=\frac{1}{2}\begin{bmatrix}-i&2&i&2\\\ 1&i&1&-i\\\ i&0&-i&0\\\
-1&i&-1&-i\end{bmatrix}.$ (1.6)

Note that the columns $R=[r_{1}\ r_{2}\ r_{3}\ r_{4}]$ are conjugate of each
other:

$r_{1}=\overline{r}_{3}\text{ and }r_{2}=\overline{r}_{4}.$

Hence, we say that $R$ captures a conjugate symmetric basis of $A$ from (1.3)
and $(A,H)\overset{R}{\mapsto}(J,G)$, where

$G=R^{*}HR=\begin{bmatrix}0&0&0&1\\\ 0&0&1&-3i\\\ 0&1&0&0\\\
1&3i&0&0\end{bmatrix}$

is not antidiagonal as was $P$ in (1.5). That is, $R$ is CS but not FO. Also,
if we look at the FO basis in $T$ from (1.4), it is clearly not CS.

###  1.4 FOCS Bases

Now that we have introduced the FO and $\gamma$-CS canonical bases we might
ask: Is there a Jordan basis for real $H$-selfadjoint matrices that is
simultaneously flipped orthogonal and $\gamma$-conjugate symmetric?

Consider the following matrix whose columns also capture a Jordan basis of the
same matrix $A$ as above.

$M=\frac{1}{4}\begin{bmatrix}-2i&1&2i&1\\\ 2&-i&2&i\\\ 2i&3&-2i&3\\\
-2&5i&-2&-5i\end{bmatrix}.$

In fact, $(A,H)\overset{M}{\mapsto}(J,P)$. Moreover, $M$ is CS.

We summarize all the above examples in the following figure.

$(J,P)$$(J,G)$$(J,P)$$(A,H)$$M$FOCS$T$FOnot CSnot FOCS$T$$R$

Figure 1: Jordan bases of $A$.

In this case, we say that $M$ captures the flipped orthogonal conjugate
symmetric basis.

This is only an example. We show the existence of such bases in the next
section.

###  1.5 Main results

In this paper, we consider the case of real matrices $A$ and $H$. For the real
case we prove the existence of a “refined” FO-basis which we call the $i$-FOCS
basis (i.e. flipped orthogonal and also $i$-conjugate symmetric). Namely, the
Jordan chains of $A$ corresponding to $\lambda$ and $\overline{\lambda}$ are
just scaled conjugates of each other, still enjoying the flipped orthogonal
property.

##  2 Three Canonical Bases

We have already presented an example of an FO basis. The next subsection shows
the existence of such a basis for any $H$-selfadjoint matrix.

###  2.1 FO Bases

The next proposition establishes the existence of FO bases for any
(potentially non-real) pair $(A,H)$.

######  Proposition 2.1 ([1]).

Let ${A},H\in\mathbb{C}^{n\times n}$ be given with $H=H^{*}$ and $A$ being
$H$-selfadjoint matrix. Let $J$ be its Jordan form

$J=J(\lambda_{1})\oplus\cdots
J(\lambda_{\alpha})\oplus\widehat{J}(\lambda_{\alpha+1})\oplus\cdots\oplus\widehat{J}(\lambda_{\beta})$
(2.7)

where $\lambda_{1},\ldots,\lambda_{\alpha}\in\mathbb{R}$,
$\lambda_{\alpha+1},\ldots,\lambda_{\beta}\notin\mathbb{R}$, $J(\lambda_{i})$
is a Jordan block for real eigenvalues $\lambda_{1},\ldots,\lambda_{\alpha}$
and

$\widehat{J}(\lambda_{k})=\left[\begin{array}[]{cc}J(\lambda_{k})&0\\\
0&J(\overline{\lambda}_{k})\\\ \end{array}\right]$ (2.8)

is the direct sum of two Jordan blocks of the same size corresponding to
$\lambda_{k}$ and $\overline{\lambda}_{k}$. Then there exists an invertible
matrix $T$ such that

$(A,H)\overset{T}{\mapsto}(J,P)$

where

$P=P_{1}\oplus\cdots\oplus
P_{\alpha}\oplus{P}_{\alpha+1}\oplus\cdots\oplus{P}_{\beta}$ (2.9)

where $P_{k}$ is a sip matrix $\epsilon_{k}\tilde{I}_{k}$ (i.e.
$\left[\begin{smallmatrix}&&&\\\ 0&\ldots&0&\epsilon_{k}\\\
\vdots&\mathinner{\mskip 1.0mu\raise 1.0pt\vbox{\kern 7.0pt\hbox{.}}\mskip
2.0mu\raise 4.0pt\hbox{.}\mskip 2.0mu\raise 7.0pt\hbox{.}\mskip
1.0mu}&\epsilon_{k}&0\\\ 0&\mathinner{\mskip 1.0mu\raise 1.0pt\vbox{\kern
7.0pt\hbox{.}}\mskip 2.0mu\raise 4.0pt\hbox{.}\mskip 2.0mu\raise
7.0pt\hbox{.}\mskip 1.0mu}&\mathinner{\mskip 1.0mu\raise 1.0pt\vbox{\kern
7.0pt\hbox{.}}\mskip 2.0mu\raise 4.0pt\hbox{.}\mskip 2.0mu\raise
7.0pt\hbox{.}\mskip 1.0mu}&\vdots\\\\[5.0pt] \epsilon_{k}&0&\cdots&0\\\
&&&\end{smallmatrix}\right]$) of the same size as $J({\lambda_{k}})$ and
$\epsilon_{k}=\pm{1}$ for $k=1,\ldots,\alpha$ and a sip matrix $\tilde{I}_{k}$
(i.e. $\left[\begin{smallmatrix}&&&\\\ 0&\ldots&0&1\\\
\vdots&\mathinner{\mskip 1.0mu\raise 1.0pt\vbox{\kern 7.0pt\hbox{.}}\mskip
2.0mu\raise 4.0pt\hbox{.}\mskip 2.0mu\raise 7.0pt\hbox{.}\mskip 1.0mu}&1&0\\\
0&\mathinner{\mskip 1.0mu\raise 1.0pt\vbox{\kern 7.0pt\hbox{.}}\mskip
2.0mu\raise 4.0pt\hbox{.}\mskip 2.0mu\raise 7.0pt\hbox{.}\mskip
1.0mu}&\mathinner{\mskip 1.0mu\raise 1.0pt\vbox{\kern 7.0pt\hbox{.}}\mskip
2.0mu\raise 4.0pt\hbox{.}\mskip 2.0mu\raise 7.0pt\hbox{.}\mskip
1.0mu}&\vdots\\\\[5.0pt] 1&0&\cdots&0\\\ &&&\end{smallmatrix}\right]$) of the
same size as $\hat{J}({\lambda_{k}})$ for $k=\alpha+1,\ldots,\beta$.

Why flipped orthogonal?

If $t_{i},t_{j}$ are the $i$th, $j$th columns of $T$ respectively, then

$[t_{i},t_{j}]_{H}=[e_{i},e_{j}]_{P}.$

In other words, if we partition $T$ in the following way

$T=[T_{1}\ldots T_{\alpha}\ |T_{\alpha+1}\ldots T_{\beta}],$

for $k=1,\ldots,\alpha$ the columns of

$T_{k}=[g_{0,k},\ldots,g_{{p_{k}}-1,k}]$

form the Jordan chain of $A$ corresponding to real $\lambda_{k}$. Similarly,
the columns of

$T_{k}=[\underbrace{g_{0,k},\ldots,g_{{p_{k}}-1,k}}_{\lambda_{k}}\
|\underbrace{h_{0,k},\ldots,h_{{p_{k}}-1,k}}_{\overline{\lambda}_{k}}]$

for $k=\alpha+1,\ldots,\beta$ form two Jordan chains, corresponding to
$\lambda_{k}$ and ${\overline{\lambda}_{k}}$ respectively. Then the structure
of the signature matrix $P$ implies the following orthogonality relation,

$g_{ik}^{*}Hg_{jm}=0,\;\;\;\;h_{ik}^{*}Hg_{jm}=0,\;\;\;\;h_{ik}^{*}Hh_{jm}=0,\;\;\text{
for }\;\;k\neq m.$

Further, we have that

$g_{i,k}^{*}Hg_{j,k}=\left\\{\begin{array}[]{ll}\epsilon_{k},\quad
j=p_{k}-1-i\\\ 0\quad\text{otherwise}\end{array}\right.\qquad\text{for}\quad
k=1,\ldots,\alpha$ $\left\\{\begin{array}[]{ll}g_{ik}^{*}Hg_{jk}=0,\\\
h_{ik}^{*}Hh_{jk}=0,\\\ h_{i,k}^{*}Hg_{j,k}=\left\\{\begin{array}[]{ll}1,\quad
j=p_{k}-1-i\\\
0\quad\text{otherwise}\end{array}\right.\end{array}\right.\qquad\text{for}\quad
k=\alpha+1,\ldots,\beta.$

In terms of our example it means that

$\begin{bmatrix}[t_{1},t_{1}]_{H}&[t_{1},t_{2}]_{H}&[t_{1},t_{3}]_{H}&[t_{1},t_{4}]_{H}\\\
[t_{2},t_{1}]_{H}&[t_{2},t_{2}]_{H}&[t_{2},t_{3}]_{H}&[t_{2},t_{4}]_{H}\\\
[t_{3},t_{1}]_{H}&[t_{3},t_{2}]_{H}&[t_{3},t_{3}]_{H}&[t_{3},t_{4}]_{H}\\\
[t_{4},t_{1}]_{H}&[t_{4},t_{2}]_{H}&[t_{4},t_{3}]_{H}&[t_{4},t_{4}]_{H}\end{bmatrix}=$
$\begin{bmatrix}[e_{1},e_{1}]_{P}&[e_{1},e_{2}]_{P}&[e_{1},e_{3}]_{P}&[e_{1},e_{4}]_{P}\\\
[e_{2},e_{1}]_{P}&[e_{2},e_{2}]_{P}&[e_{2},e_{3}]_{P}&[e_{2},e_{4}]_{P}\\\
[e_{3},e_{1}]_{P}&[e_{3},e_{2}]_{P}&[e_{3},e_{3}]_{P}&[e_{3},e_{4}]_{P}\\\
[e_{4},e_{1}]_{P}&[e_{4},e_{2}]_{P}&[e_{4},e_{3}]_{P}&[e_{4},e_{4}]_{P}\end{bmatrix}=\begin{bmatrix}0&0&0&1\\\
0&0&1&0\\\ 0&1&0&0\\\ 1&0&0&0\end{bmatrix}=P.$

As we showed by our example in Introduction – not every Jordan basis is
necessarily flipped-orthogonal. However, the above proposition yields that the
flipped orthogonal basis always exists for $H$-selfadjoint matrices. In fact,
in view of the structure of $P$, it is captured by the columns of $T$.

To show that $\gamma$-FOCS bases exist, we need to introduce yet another
canonical form.

###  2.2 $\gamma$-CS Bases

Revising example in (3.16), one question arises.

Why do the columns of $R$ from our example in Introduction capture the Jordan
basis?

For any real matrix $A$, if $\lambda$ is its non-real eigenvalue, then so is
$\overline{\lambda}$. Moreover, if $g_{k}\to g_{k-1}\to\ldots\to g_{0}\to 0$
is a Jordan chain corresponding to $\lambda$ then

$\gamma\overline{q_{k-1}}=\gamma\overline{(A-\lambda
I)q_{k}}={(\overline{A}-{\overline{\lambda}}\overline{I}){\gamma\overline{q_{k}}}}={({A}-{\overline{\lambda}}{I}){\gamma\overline{q_{k}}}},$

i.e.
$\gamma\overline{g}_{k}\to\gamma\overline{g}_{k-1}\to\ldots\to\gamma\overline{g}_{0}\to
0$ is also a Jordan chain of $A$ but corresponding to $\overline{\lambda}$ for
any non-zero $\gamma\in\mathbb{C}$.

This observation leads to the following definition.

Suppose $A\in\mathbb{R}^{n\times n}$ and that there exists an invertible
matrix $N$ such that $A=NJN^{-1}$, where

$J=J(\lambda_{1})\oplus\cdots\oplus
J(\lambda_{\alpha})\oplus\widehat{J}(\lambda_{\alpha+1})\oplus\cdots\oplus\widehat{J}(\lambda_{\beta})$

is the Jordan canonical form and $\widehat{J}(\lambda_{k})$ defined in (2.8).
The matrix

${}N=[N_{1}\lvert\ldots\lvert
N_{\alpha}\lvert{N}_{\alpha+1}\lvert\ldots\lvert{N}_{\beta}]$ (2.10)

can be chosen that

$N_{k}=[Q_{k}\lvert\gamma\overline{Q}_{k}]$ (2.11)

for any $\gamma\neq 0$ and $k=\alpha+1,\ldots,\beta$. The columns of $N$
capture the Jordan basis of $A$, and because of (2.11) we call it the
$\gamma$-conjugate symmetric basis.

In this paper we show that for any real $H$-selfadjoint matrix $A$ there exist
a Jordan basis that is simultaneously FO and $i$-CS. For this we need to
consider the real canonical form.

###  2.3 Real Canonical Form

The following well-known result (see [2, Theorem 6.1.5]) describes a purely
real relation

$(A,H)\overset{R}{\mapsto}(J_{R},P)$ (2.12)

where all five matrices are real.

######  Proposition 2.2.

Let ${A},H\in\mathbb{R}^{n\times n}$ be given with $H=H^{\top}$ and $A$ being
$H$-selfadjoint matrix. Let $J_{R}$ be its real Jordan form

$J_{R}=J(\lambda_{1})\oplus\cdots\oplus
J(\lambda_{\alpha})\oplus\widehat{J}_{R}(\lambda_{\alpha+1})\oplus\cdots\oplus\widehat{J}_{R}(\lambda_{\beta}),$
(2.13)

where $\lambda_{1},\ldots,\lambda_{\alpha}\in\mathbb{R}$,
$\lambda_{\alpha+1},\ldots,\lambda_{\beta}\notin\mathbb{R}$, $J(\lambda_{i})$
is a Jordan block for real eigenvalues $\lambda_{1},\ldots,\lambda_{\alpha}$
and

$\widehat{J}_{R}(\lambda_{k})={\left[\setcounter{MaxMatrixCols}{11}\begin{smallmatrix}\sigma_{k}&\tau_{k}&1&0&0&\cdots&&\cdots&&&0\\\
-\tau_{k}&\sigma_{k}&0&1&0&\ddots&&&&&\\\
0&0&\sigma_{k}&\tau_{k}&1&\ddots&\ddots&&&&\vdots\\\
0&0&-\tau_{k}&\sigma_{k}&0&1&\ddots&\ddots&&\\\
&\ddots&\ddots&\ddots&\ddots&\ddots&\ddots&\ddots&\ddots&&\vdots\\\
\vdots&&\ddots&\ddots&\ddots&\ddots&\ddots&\ddots&\ddots&\ddots&\\\
&&&\ddots&\ddots&\ddots&\ddots&\ddots&\ddots&\ddots&0\\\
&&&&\ddots&\ddots&0&\sigma_{k}&\tau_{k}&1&0\\\
\vdots&&&&&\ddots&\ddots&-\tau_{k}&\sigma_{k}&0&1\\\
&&&&&&\ddots&0&0&\sigma_{k}&\tau_{k}\\\\[6.00006pt]
0&&\ldots&&&\ldots&&0&0&-\tau_{k}&\sigma_{k}\\\ \end{smallmatrix}\right]},$

where $\lambda_{k}=\sigma_{k}+i\tau_{k}$. Then there exists an invertible real
matrix $R$ such that $(A,H)\overset{R}{\mapsto}(J_{R},P)$ where $P$ is a sip
matrix of the form

$P=P_{1}\oplus\cdots\oplus
P_{\alpha}\oplus{P}_{\alpha+1}\oplus\cdots\oplus{P}_{\beta},$

where $P_{k}$ is a sip matrix $\epsilon_{k}\widetilde{I}$ of the same size as
$J({\lambda_{k}})$ for $k=1,\ldots,\alpha$ and a sip matrix $\widetilde{I}$ of
the same size as $\hat{J}_{R}({\lambda_{k}})$ for $k=\alpha+1,\ldots,\beta$
and $\epsilon_{k}=\pm{1}$ for $k=1,\ldots,\alpha$.

Suppose that $A\in\mathbb{R}^{n\times n}$ and $J_{R}$ is the real Jordan form
in (2.13). We say that columns of matrix $R$ in (2.12) form a real canonical
basis of $A$.

Finally, we are ready to prove the main result.

##  3 Existence of $i$-FOCS Bases

The FO basis was defined for pairs of matrices $(A,H),$ where $A$ and $H$ are
not necessarily real. The $\gamma$-CS basis is defined for the case of $A$
being a real matrix. So what about real $H$-selfadjoint matrices?

Proposition 2.1 implies the existence of the FO basis for $(A,H)$, and the
latter, generally, does not have the CS property.

######  Theorem 3.1.

(Existence of an $i$-FOCS basis) Let $A$ be a real $H$-selfadjoint matrix
where $H$ is real, invertible, and Hermitian. Then $N$ in
$(A,H)\overset{N}{\mapsto}(J,P)$ can be chosen $i$-conjugate symmetric and
flipped orthogonal at the same time.

To establish this result, let us discuss the relation between RC and $i$-FOCS
bases. As we will see, for an arbitrary real pair $(A,H)$, the relation
between $i$-FOCS and RC bases is carried over with the help of the same fixed
matrix $S$.

######  Lemma 3.2.

Let $A,H\in\mathbb{R}^{n\times n}$, $H=H^{\top}$, and $A$ is $H$-selfadjoint,
and let the columns of $R$ capture the RC basis of $A$.

$R=[N_{1},\ldots,N_{\alpha}\lvert K_{\alpha+1},\ldots,K_{\beta}]$ (3.14)

capture the RC basis of $A$. Then for
$S=\operatorname{diag}({I_{1},\ldots,I_{\alpha}|S_{\alpha+1},\ldots,S_{\beta}})$,
where the explicit formula for $S_{j}$ is:

$S_{j}=\frac{1}{\sqrt{2}}\left[\begin{array}[]{ccccccccccccc}1&0&\cdots&0&i&0&\cdots&0\\\
i&0&{}\hfil&\vdots&1&0&{}\hfil&\vdots\\\ \hline\cr
0&1&\ddots&0&0&i&\ddots&0\\\ 0&i&\ddots&\vdots&0&1&\ddots&\vdots\\\
\hline\cr\vdots&\ddots&\ddots&0&\vdots&\ddots&\ddots&0\\\
\hline\cr\vdots&\ddots&\ddots&1&\vdots&\ddots&\ddots&i\\\
0&\cdots&0&i&0&\cdots&0&1\\\ \end{array}\right],$

the columns of $N=RS$ capture the i-FOCS basis of $A$.

The next result is the converse to the one in Lemma 3.2

######  Lemma 3.3.

If the columns of

$N=[N_{1},\ldots,N_{\alpha}\lvert N_{\alpha+1},\ldots,N_{\beta}]\text{ and
}N_{k}=[Q_{k}\lvert i\overline{Q}_{k}],\quad k=\alpha+1,\ldots,\beta$ (3.15)

capture the i-FOCS basis of $(A,H)$.

Further, note that
$S^{-1}=\operatorname{diag}({I_{1},\ldots,I_{\alpha}|S^{-1}_{\alpha+1},\ldots,S^{-1}_{\beta}})$,
where

$S_{j}^{-1}=\frac{1}{\sqrt{2}}\left[\begin{array}[]{ccccccccc}1&-i&0&0&\cdots&\cdots&0\\\
0&0&1&-i&0&\cdots&0\\\ \vdots&\ddots&\ddots&\ddots&\ddots&\ddots&\vdots\\\
\vdots&{}\hfil&\ddots&\ddots&-i&0&0\\\ 0&\cdots&\cdots&0&0&1&-i\\\
-i&1&0&0&\cdots&\cdots&0\\\ 0&0&-i&1&0&\cdots&0\\\
\vdots&\ddots&\ddots&\ddots&\ddots&\ddots&\vdots\\\
\vdots&{}\hfil&\ddots&\ddots&1&0&0\\\ 0&\cdots&\cdots&0&0&-i&1\\\
\end{array}\right]\\\ .$

Then the matrix

$R=NS^{-1}$ (3.16)

is real and its columns capture the RC basis of $A$. Moreover, from (3.14) we
get $K_{j}=N_{j}S_{j}^{-1}$ for $j=\alpha+1,\ldots,\beta$.

###### Proof of Lemma 3.2.

First, let us show that the columns of matrix $N$ in (3.16) capture a basis of
$A$, then that this basis is $i$-CS . Without loss of generality we consider
the case of a single real Jordan block, assuming that
$\sigma(A)=\big{\\{}\lambda,\overline{\lambda}\big{\\}}$. The relation
$S^{-1}{J_{R}}S={J}$ follows from

${J}S=\frac{1}{\sqrt{2}}{\left[\begin{smallmatrix}\sigma+i\tau&1&0&\dots&0&i\sigma+\tau&i&0&\dots&0\\\
-\tau+i\sigma&i&0&\dots&0&-i\tau+\sigma&1&0&\dots&0\\\
0&\sigma+i\tau&1&\dots&0&0&i\sigma+\tau&i&\dots&0\\\
0&-\tau+i\sigma&i&\dots&0&0&-i\tau+\sigma&1&\dots&0\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\
0&0&0&\dots&1&0&0&0&\dots&i\\\ 0&0&0&\dots&i&0&0&0&\dots&1\\\
0&0&0&\dots&\sigma+i\tau&0&0&0&\dots&i\sigma+\tau\\\
0&0&0&\dots&-\tau+i\sigma&0&0&0&\dots&-i\tau+\sigma\\\
\end{smallmatrix}\right]}=S{J}_{R},$

where $\lambda=\sigma+i\tau$. Therefore,

$A=RJ_{R}R^{-1}=(RS)(S^{-1}J_{R}S)(RS)^{-1}=NJN^{-1}.$

That is the columns of $N$ indeed capture a basis of $A$. For a pair of
vectors $a$ and $b$

$i\cdot\overline{a+ib}=i(a-ib)=ia+b.$

This is exactly what multiplication by $S$ on the left does to real columns of
$R$. Hence, we get the $i$-conjugate symmetry for $N$.

Next, we want to show that the columns of $N$ form an FO basis. The relation
$S^{\ast}PS=P$ in (3.17) follows from

$S^{*}PS=P\text{ being equivalent to }PS^{*}PS=PP=I.$

Thus, we just need to show that $PS^{*}PS=I$.

$PS^{*}PS=\frac{1}{2}\left[\begin{smallmatrix}&&&&&&&\\\
0&0&\dots&0&i&0&0&\dots&1\\\ 0&0&\dots&0&1&0&0&\dots&i\\\
0&0&\dots&i&0&0&0&\dots&0\\\ 0&0&\dots&1&0&0&0&\dots&0\\\
\vdots&\vdots&\iddots&\vdots&\vdots&\vdots&\vdots&\iddots&\vdots\\\
0&i&\dots&0&0&0&1&\dots&0\\\ 0&1&\dots&0&0&0&i&\dots&0\\\
i&0&\dots&0&0&1&0&\dots&0\\\ 1&0&\dots&0&0&i&0&\dots&0\\\ &&&&&&&\\\
\end{smallmatrix}\right]\\\ \left[\begin{smallmatrix}0&0&0&0&\dots&-i&1\\\
\vdots&\vdots&\vdots&\vdots&\iddots&\vdots&\vdots\\\ 0&0&-i&1&\dots&0&0\\\
-i&1&0&0&\dots&0&0\\\ 0&0&0&0&\dots&1&-i\\\
\vdots&\vdots&\vdots&\vdots&\iddots&\vdots&\vdots\\\ 0&0&1&-i&\dots&0&0\\\
1&-i&0&0&\dots&0&0\\\ \end{smallmatrix}\right]\\\ =I.$

Since $(A,H)\overset{R}{\mapsto}(J_{R},P)$, the above relation implies that

$({J_{R}},P)\overset{S}{\mapsto}({J},P).$ (3.17)

Hence, $(A,H)\overset{N}{\mapsto}(J,P)$ and the basis in question is FO as
well as $i$-CS, i.e. it is $i$-FOCS.

∎

The converse statement follows from the relation
$(J,P)\overset{S^{-1}}{\mapsto}(J_{R},P)$, using similar argument.

Combining Proposition 2.2 and Lemma 3.2, we get the result of Theorem 3.1.

## References

  * [1] T. Bella, V. Olshevsky, U. Prasad, Lipschitz stability of canonical Jordan bases of $H$-selfadjoint matrices under structure-preserving perturbations, Linear Algebra and its Applications, 428, 8–9, 2008, 2130–2176
  * [2] I. Gohberg, P. Lancaster, L. Rodman, Indefinite Linear Algebra and applications, Birkhäuser, 2005, xii+357 pp.
  * [3] I. Gohberg, P. Lancaster, L. Rodman, Invariant Subspaces of Matrices with Applications, Canadian Mathematical Society Series of Monographs and Advanced Texts. A Wiley-Interscience Publication. John Wiley& Sons, Inc., New York, 1986, xviii+692 pp.
  * [4] A.I. Mal’cev, Foundations of Linear Algebra, W. H. Freeman& Co., San Francisco, Calif.-London 1963 xi+304 pp. (Translation from Russian).
  * [5] K. Weierstrass, Zur Theorie der quadratischen und bilineareen Formen, Monatsber. Akad. Wiss., Berlin, 1868, 310–338.
  * [6] K. Weierstrass, Mathematische Werke, Zweiter Band. Abhandlungen II, Berlin, Mayer & Muller, 1895, 19–44.