# Precise Performance Analysis of the LASSO under Matrix Uncertainties

###### Abstract

In this paper, we consider the problem of recovering an unknown sparse signal
${\bf x}_{0}\in\mathbb{R}^{n}$ from noisy linear measurements ${\bf y}={\bf
H}{\bf x}_{0}+{\bf z}\in\mathbb{R}^{m}$. A popular approach is to solve the
$\ell_{1}$-norm regularized least squares problem which is known as the LASSO.
In many practical situations, the measurement matrix ${\bf H}$ is not
perfectely known and we only have a noisy version of it. We assume that the
entries of the measurement matrix ${\bf H}$ and of the noise vector ${\bf z}$
are iid Gaussian with zero mean and variances $1/n$ and $\sigma_{{\bf
z}}^{2}$. In this work, an imperfect measurement matrix is considered under
which we precisely characterize the limiting behavior of the mean squared
error and the probability of support recovery of the LASSO. The analysis is
performed when the problem dimensions grow simultaneously to infinity at fixed
rates. Numerical simulations validate the theoretical predictions derived in
this paper.

Index Terms—  LASSO, mean squared error, CGMT, measurement matrix
uncertainties, probability of support recovery

##  1 Introduction

The Least Absolute Shrinkage and Selection Operator (LASSO) [1] is a powerfull
method to recover a k-sparse unknown signal ${\bf x}_{0}$ $\in\mathbb{R}^{n}$
from noisy linear measurements: ${\bf y}={\bf H}{\bf x}_{0}+{\bf
z}\in\mathbb{R}^{m}$, where ${\bf H}\in\mathbb{R}^{m\times n}$ is the
measurement matrix, and ${\bf z}\in\mathbb{R}^{m}$ is the noise vector. In
this paper, we assume that ${\bf H}$ is not perfectly known, and we only have
a noisy version of it that is denoted by ${\bf A}$. Then, the LASSO solves the
following convex optimization proplem:

$\hat{{\bf x}}=\text{arg}\ \underset{{{\bf x}}}{\operatorname{\min}}\
\frac{1}{2}||{\bf y}-{\bf A}{\bf x}||^{2}+\lambda||{\bf x}||_{1},$ (1)

where $||\cdot||$ and $||\cdot||_{1}$ denote the $\ell_{2}$-norm and the
$\ell_{1}$-norm respectively, and $\lambda\geq 0$ is the regularization
parameter that balances between the deviation of ${\bf A}\hat{{\bf x}}$ from
the observations ${\bf y}$ on one side, and the sparsity of the solution as
promoted by the $\ell_{1}$-norm on the other side. Problems of the form of (1)
have many different diverse applications in science and engineering such as
image processing [2], machine learning [3], wireless communications [4], etc..
The LASSO has been studied from different prespectives over the years. In
recent years, the asymptotic exact characterization of the estimation
performance gained a lot of interest. General performance metrics have been
introduced such as the mean squared error and the probability support
recovery. The first well-known bounds on the estimation performance of the
lasso were order-wise in nature [5, 6, 7, 8]. The Approximate Message Passing
(AMP) framework has been used in [9, 10, 11] to derive precise asymptotic
analysis of the LASSO performance under the assumptions of iid Gaussian
sensing matrix ${\bf A}$. A recently developed framework, that is based on the
Convex Gaussian Min-max Theorem (CGMT) [12], has been used in a series of
works to precisely evaluate the estimation performance of non-smooth
regularized convex estimators under noisy iid Gaussian measurements (including
the LASSO) [12, 20, 19, 22, 13].

However, these results assume that the measurement matrix ${\bf A}$ is
perfectly known. In many practical applications it is reasonable to expect
uncertainty in the linear measurement matrix ${\bf A}$ due to, e.g.,
imperfections in the signal acquisition hardware, model mismatch, estimation
errors [14]. In this paper, we consider the additive uncertainty model: ${\bf
A}=\sqrt{1-\epsilon^{2}}{\bf H}+\epsilon\hbox{\boldmath$\Omega$},$ where ${\bf
H}$ is known and $\Omega$ is an unknown error matrix and
$\epsilon^{2}\in[0,1)$ is the variance of the error. Such model is commonly
used in communication theory and known as imperfect Channel State Information
(CSI) [15].

In this work, we derive precise asymptotic predictions of the mean squared
error and the support recovery of the LASSO under the presence of
uncertainties in the measurement matrix that has iid Gaussian entries (both
${\bf H}$ and $\Omega$ have iid Gaussian entries). The Gaussianity assumption
of the entries of ${\bf A}$ is met in a wide range of applications such as
MIMO application for Rayleigh fading model. The analysis is based on the CGMT
framework and is performed when the problem dimensions $m$, $n$ and $k$ all
grow simultaneously to infinity at fixed rates. Although our analysis is
asymptotic in nature, numerical simulations show that our theoretical
predictions are valid even for a few dozens of the problem dimensions.

##  2 Problem Setup

###  2.1 Performance Metrics

Finding a good estimate is an application dependent, since different
applications require different desired properties of $\hat{{\bf x}}$. This
results in a need for a variety of different performance metrics. Here we
discuss some of them.
Mean squared error (MSE): A natural and heavily used measure of performance is
the reconstruction mean squared error, which measures the deviation of
$\hat{{\bf x}}$ from the true signal ${\bf x}_{0}$. Formally, the MSE is
defined as MSE $:=\frac{1}{n}||\hat{{\bf x}}-{\bf x}_{0}||^{2}$.
Support Recovery: In the problem of sparse recovery, a natural measure of
performance that is used in many applications (e.g. parameter selection in
regression, sparse approximation, structure estimation in graphical models
[16]) is the support recovery, which is defined as identifying whether an
entry of ${\bf x}_{0}$ is on the support (i.e. non-zero), or it is off the
support (i.e. zero). The decison is based on the LASSO solution $\hat{{\bf
x}}$: we say the $i^{th}$ entry of $\hat{{\bf x}}$ is on the support if
$|\hat{{\bf x}}_{i}|\geq\xi$, where $\xi>0$ is a user-defined hard threshold
on the entries on $\hat{{\bf x}}.$ In Theorem 2, we precisely predict the per-
entry rate of successful on-support and off-support recovery. Formaly, let

$\displaystyle\Phi_{\xi,\text{on}}(\hat{{\bf x}})=\frac{1}{k}\sum_{i\in S({\bf
x}_{0})}\mathbbm{1}_{\\{|\hat{{\bf x}}_{i}|\geq\xi\\}}$ (2a)
$\displaystyle\Phi_{\xi,\text{off}}(\hat{{\bf x}})=\frac{1}{n-k}\sum_{i\notin
S({\bf x}_{0})}\mathbbm{1}_{\\{|\hat{{\bf x}}_{i}|\leq\xi\\}},$ (2b)

where $\mathbbm{1}_{\\{\mathcal{B}\\}}$ is the indicator function of a set
$\mathcal{B}$, and $S({\bf x}_{0})$ is the support of ${\bf x}_{0}$, i.e. the
set of the non-zero entries of ${\bf x}_{0}$.

###  2.2 Working Assumptions

The unkown signal ${\bf x}_{0}\in\mathbb{R}^{n}$ is a $k$-sparse signal, i.e.
only $k$ of its entries are sampled iid from a distribution $p_{X_{0}}$ which
has zero mean and unit variance ($\mathbb{E}[X_{0}^{2}]=1$), and the remaining
entires are zeros. For the measurement matrix ${\bf A}$, we consider the
following additive uncertainty model: ${\bf A}=\gamma{\bf
H}+\epsilon\hbox{\boldmath$\Omega$},$ where ${\bf
H},\hbox{\boldmath$\Omega$}\in\mathbb{R}^{m\times n}$ both have entries iid
$\mathcal{N}(0,1/n)$, and $\epsilon^{2}\in[0,1)$ is the variance of the error
such that $\gamma^{2}+\epsilon^{2}=1$. The noise vector ${\bf
z}\in\mathbb{R}^{m}$ has entries iid $\mathcal{N}(0,\sigma_{{\bf z}}^{2})$.
The analysis is performed when the system dimensions ($m$, $n$ and $k$) grow
simultaneously large at fixed ratios:
$\frac{m}{n}\longrightarrow\delta\in(0,\infty)$, and
$\frac{k}{n}\longrightarrow\kappa\in(0,1).$ Under these settings, the Signal
to Noise Ratio (SNR) becomes SNR :=$\kappa/\sigma_{{\bf z}}^{2}.$

###  2.3 Notation

Throughout this paper, we use boldface letters to represent vectors and
matrices. We use the standard notation $\mathbb{P[\cdot]}$ and
$\mathbb{E[\cdot]}$ to denote probability and expectation. We write $X\sim
p_{X}$ to denote that a random variable $X$ has a probability density/mass
function $p_{X}$. In particular, $H\sim\mathcal{N}(\mu,\sigma^{2})$ implies
that $H$ has Gaussian distribution of mean $\mu$ and variance $\sigma^{2}$.
$\phi(x)$ and $Q(x)$ denote the pdf of a standard normal distribution and its
associated Q-function respectively. For $a,\lambda\in\mathbb{R}$, such that
$\lambda>0$, we define the following functions:
The soft-thresholding operator: $\eta(a;\lambda)$ = $\text{arg min}_{x}$
$\frac{1}{2}(x-a)^{2}+\lambda|x|$, which can be written:

$\eta(a;\lambda)=\begin{cases}a-\lambda&,\text{if}\ a>\lambda\\\ 0&,\text{if}\
|a|\leq\lambda\\\ a+\lambda&,\text{if}\ a<-\lambda.\end{cases}$ (3)

and its optimal value
$e(a;\lambda)=\text{min}_{x}\frac{1}{2}(x-a)^{2}+\lambda|x|$

$e(a;\lambda)=\begin{cases}\lambda a-\frac{1}{2}\lambda^{2}&,\text{if}\
a>\lambda\\\ \frac{1}{2}a^{2}&,\text{if}\ |a|\leq\lambda\\\ -\lambda
a-\frac{1}{2}\lambda^{2}&,\text{if}\ a<-\lambda.\end{cases}$ (4)

Finaly, we write “$\overset{P}{\longrightarrow}$” to designate convergence in
probability.

##  3 Main Results

This section summarizes our main results on the precise analysis of the mean
squared error and the probability of support recovery of the LASSO.

######  Theorem 1 (LASSO MSE)

Fix $\lambda>0$, and let $\hat{{\bf x}}$ be a minimizer of the LASSO problem
in (1), where ${\bf A},{\bf z}$ and ${\bf x}_{0}$ satisfy the working
assumptions of Section 2.2. Then it holds in probability:

$\displaystyle\lim_{n\to\infty}\frac{1}{n}||\hat{{\bf x}}-{\bf
x}_{0}||^{2}=\delta\tau_{*}^{2}-\sigma_{{\bf z}}^{2}$
$\displaystyle+2(\gamma-1)\mathbb{E}_{\underset{H\sim\mathcal{N}(0,1)}{X_{0}\sim
p_{X_{0}}}}\biggr{[}\eta\biggr{(}\gamma
X_{0}+\tau_{*}H;\frac{2\lambda\tau_{*}}{\beta_{*}}\biggl{)}X_{0}\biggl{]},$
(5)

where $(\tau_{*},\beta_{*})$ is the unique solution to the following:

$\displaystyle\underset{\tau>0}{\operatorname{\min}}\
\underset{\beta>0}{\operatorname{\max}}\
D(\tau,\beta):=\frac{\beta\tau}{2}(\delta-1)+\frac{\beta\sigma_{{\bf
z}}^{2}}{2\tau}-\frac{\beta^{2}}{4}$
$\displaystyle+\frac{\beta\epsilon^{2}\kappa}{2\tau}+\frac{\beta}{\tau}\cdot\mathbb{E}_{X_{0},H}\biggr{[}e\biggr{(}\gamma
X_{0}+\tau H;\frac{2\lambda\tau}{\beta}\biggl{)}\biggl{]}.$ (6)

$\tau_{*}$ and $\beta_{*}$ can be efficiently computed by writing the first
order optimality conditions, i.e. $\nabla_{(\tau,\beta)}D(\tau,\beta).$ The
proof of Theorem 1 is based on the CGMT framework and is deferred to Section
5.
The following Theorem precisely characterizes the support recovery metrics
introduced in (2).

######  Theorem 2 (Probability of support recovery)

Under the same settings of Theorem 1 and for any fixed $\xi>0$, it holds in
probability that:

$\lim_{n\to\infty}\Phi_{\xi,on}(\hat{{\bf x}})=\mathbb{P}[\bigl{|}\eta(\gamma
X_{0}+\tau_{*}H;\frac{2\lambda\tau_{*}}{\beta_{*}})\bigr{|}\geq\xi],$

and

$\lim_{n\to\infty}\Phi_{\xi,\text{off}}(\hat{{\bf
x}})=\mathbb{P}[\bigl{|}\eta(\tau_{*}H;\frac{2\lambda\tau_{*}}{\beta_{*}})\bigr{|}\leq\xi]=1-2Q\biggl{(}\frac{\xi}{\tau_{*}}+\frac{2\lambda}{\beta_{*}}\biggr{)}.$

The proof of Theorem 2 is also based on the CGMT and largely follows the proof
of Theorem 1 and is omitted for space limitations.

##  4 Numerical Results

For illustration, we focus only on the case where ${\bf x}_{0}$, has enties
that are sampled from sparse Bernoulli distribution. i.e. most of the entries
of ${\bf x}_{0}$ are zeros and few are equal to 1. The mean squared error of
the LASSO is predicted by Theorem 1, and the particular term
$\mathbb{E}[e(\gamma X_{0}+\tau H;\chi)]$, for $\tau>0$ in (1) can be
expressed as:

$\kappa\int e(\gamma+\tau h;\chi)\phi(h)dh+(1-\kappa)\int e(\tau
h;\chi)\phi(h)dh.$

Figure 1 shows the accuracy of the mean squared error of the LASSO as
predicted by Theorem 1.
Remark (Optimal Tuning): from Figure 1, we can see that there is a value of
regularizer $\lambda$ for which the MSE is minimized.
The prediction of theorem 2 for the support recovery compaired with the
numerical simulations is shown in Figure 2. For the on-support recovery, the
term $\mathbb{P}[\bigl{|}\eta(\gamma
X_{0}+\tau_{*}H;\frac{2\lambda\tau_{*}}{\beta_{*}})\bigr{|}\geq\xi]=Q(\frac{\xi+\gamma}{\tau_{*}}+\frac{2\lambda}{\beta_{*}})+Q(\frac{\xi-\gamma}{\tau_{*}}+\frac{2\lambda}{\beta_{*}})$
for the sparse Bernoulli case. Both figures show the high accuracy of our
predictions.

$0$$2$$4$$6$$0$$0.2$$0.4$$0.6$$0.8$$1$$\lambda$MSETheorySimulation Fig. 1: The
MSE performance of the LASSO. Theoretical prediction from Theorem 1. For
simulations $\kappa=0.1,\epsilon^{2}=0.1,\delta=0.8,n=256$, SNR = 0.5, and the
data are averaged over 50 independent realizations of problem.
$0$$1$$2$$3$$0$$0.2$$0.4$$0.6$$0.8$$1$$\lambda$Prob. of Successful Recoveryon
supportoff support Fig. 2: Probability of scucessful on-support and off-
support entries for two problem setup. The theoretical prediction (Solid and
dashed lines) comes from Theorem 2. For the simulations (Squares and Circles),
we used $n=256$, SNR= 0.5, $\xi=10^{-3},\kappa=0.1,\epsilon^{2}=0.2,$ and the
data are averaged over 50 independent realizations of problem. For solid lines
and squares and circles, we used $\delta=0.8$, while for dashed lines and
empty squares and circles $\delta=1.2$.

##  5 Proof Outline

In this section, we provide a proof outline of Theorem 1. For clarity, the
steps of the proof are in divided into different subsections.

###  5.1 Convex Gaussian Min-max Theorem (CGMT)

We first need to state the key ingredient of the analysis which is the Convex
Gaussian Min-max Theorem CGMT. Here, we just recall the statement of the
theorem, and we refer the reader to [12] for the complete technical
requirements. Consider the following two min-max problems, which we refer to
as the Primary Optimization (PO) and the Auxiliary Optimization (AO) problems:

$\displaystyle\Phi({\bf G}):=\underset{{\bf
w}\in\mathcal{S}_{w}}{\operatorname{\min}}\ \underset{{\bf
u}\in\mathcal{S}_{u}}{\operatorname{\max}}\ {\bf u}^{T}{\bf G}{\bf
w}+\psi({\bf w},{\bf u}),$ (7a) $\displaystyle\phi({\bf g},{\bf
h}):=\underset{{\bf w}\in\mathcal{S}_{w}}{\operatorname{\min}}\ \underset{{\bf
u}\in\mathcal{S}_{u}}{\operatorname{\max}}\ ||{\bf w}||{\bf g}^{T}{\bf
u}-||{\bf u}||{\bf h}^{T}{\bf w}+\psi({\bf w},{\bf u}),$ (7b)

where ${\bf G}\in\mathbb{R}^{m\times n},{\bf g}\in\mathbb{R}^{m},{\bf
h}\in\mathbb{R}^{n},\mathcal{S}_{w}\subset\mathbb{R}^{n},\mathcal{S}_{u}\subset\mathbb{R}^{m}$
and $\psi:\mathbb{R}^{n}\times\mathbb{R}^{m}\mapsto\mathbb{R}$. Denote by
${\bf w}_{\Phi}:={\bf w}_{\Phi}({\bf G})$ and ${\bf w}_{\phi}:={\bf
w}_{\phi}({\bf g},{\bf h})$ any optimal minimizers of (7a) and (7b)
respectively. Let $\mathcal{S}_{w},\mathcal{S}_{u}$ be convex, $\psi({\bf
w},{\bf u})$ be convex-concave continuous on
$\mathcal{S}_{w}\times\mathcal{S}_{u}$, and ${\bf G},{\bf g}$ and ${\bf h}$
all have iid standard normal entries. Let $\mathcal{S}$ be any arbitrary open
subset of $\mathcal{S}_{w}$. Then, if
$\lim_{n\rightarrow\infty}\mathbb{P}[{\bf w}_{\phi}\in\mathcal{S}]=1,$ it also
holds $\lim_{n\rightarrow\infty}\mathbb{P}[{\bf w}_{\Phi}\in\mathcal{S}]=1.$

###  5.2 Identifying the (PO) and the (AO)

For convenience, we consider the vector ${\bf w}:=\gamma{\bf x}-{\bf x}_{0}$,
then the problem in (1) can be reformulated in terms of ${\bf w}$ as:

$\hat{{\bf w}}=\text{arg}\ \underset{{\bf w}}{\operatorname{\min}}\ ||{\bf
H}{\bf w}+\frac{\epsilon}{\gamma}\hbox{\boldmath$\Omega$}({\bf w}+{\bf
x}_{0})-{\bf z}||^{2}+\frac{2\lambda}{\gamma}||{\bf w}+{\bf x}_{0}||_{1}.$ (8)

The problem in (8) is still not a form of a (PO) of the CGMT, so first we need
to write it in form that suits the CGMT. To do so, we first express the loss
function of (8) in its dual form through the Fenchel conjugate, $||{\bf H}{\bf
w}+\frac{\epsilon}{\gamma}\hbox{\boldmath$\Omega$}({\bf w}+{\bf x}_{0})-{\bf
z}||^{2}$ $=\max_{{\bf u}}\sqrt{n}{\bf u}^{T}({\bf H}{\bf
w}+\frac{\epsilon}{\gamma}\hbox{\boldmath$\Omega$}({\bf w}+{\bf x}_{0})-{\bf
z})-\frac{n}{4}||{\bf u}||^{2}$. The dual variable ${\bf u}$ is scaled by a
factor $\sqrt{n}$ to have a proper normalization that guarantees the
convergence afterwards. Hence, the problem in (8) is equivalent to the
following:

$\displaystyle\underset{{\bf w}}{\operatorname{\min}}\ \underset{{\bf
u}}{\operatorname{\max}}\ \sqrt{n}{\bf u}^{T}{\bf H}{\bf
w}+\frac{\sqrt{n}\epsilon}{\gamma}{\bf u}^{T}\hbox{\boldmath$\Omega$}({\bf
w}+{\bf x}_{0})-\sqrt{n}{\bf u}^{T}{\bf z}$ $\displaystyle-\frac{n}{4}||{\bf
u}||^{2}+\frac{2\lambda}{\gamma}||{\bf w}+{\bf x}_{0}||_{1}.$ (9)

The above problem is in the form of a (PO) of the CGMT. Therefore, we can
define its corresponding (AO) as:

$\displaystyle\underset{{\bf w}}{\operatorname{\min}}\ \underset{{\bf
u}}{\operatorname{\max}}\ ||{\bf w}||{\bf g}^{T}{\bf u}-||{\bf u}||{\bf
h}^{T}{\bf w}+\frac{\sqrt{n}\epsilon}{\gamma}{\bf
u}^{T}\hbox{\boldmath$\Omega$}({\bf w}+{\bf x}_{0})-\frac{n}{4}||{\bf
u}||^{2}$ $\displaystyle-\sqrt{n}{\bf u}^{T}{\bf
z}+\frac{2\lambda}{\gamma}||{\bf w}+{\bf x}_{0}||_{1}.$ (10)

###  5.3 Simplifying the (AO)

The next step is to show that the (AO1) as it appears in (5.2) can be
transformed to a Scalar Optimization (SO) problem. Since the vectors ${\bf g}$
and ${\bf h}$ are independent, $||{\bf w}||{\bf g}^{T}{\bf u}-\sqrt{n}{\bf
u}^{T}{\bf z}\buildrel d\over{=}\sqrt{||{\bf w}||^{2}+n\sigma_{{\bf
z}}^{2}}{\bf g}^{T}{\bf u}$. Therefore, (5.2) is equivalent to

$\displaystyle\underset{{\bf w}}{\operatorname{\min}}\ \underset{{\bf
u}}{\operatorname{\max}}\ \sqrt{||{\bf w}||^{2}+n\sigma_{{\bf z}}^{2}}{\bf
g}^{T}{\bf u}-||{\bf u}||{\bf h}^{T}{\bf w}-\frac{n}{4}||{\bf u}||^{2}$
$\displaystyle+\frac{\sqrt{n}\epsilon}{\gamma}{\bf
u}^{T}\hbox{\boldmath$\Omega$}({\bf w}+{\bf
x}_{0})+\frac{2\lambda}{\gamma}||{\bf w}+{\bf x}_{0}||_{1}.$ (11)

Now, it is more convenient to work with ${\bf x}$ instead of ${\bf w}$,

$\displaystyle\underset{{\bf x}}{\operatorname{\min}}\ \underset{{\bf
u}}{\operatorname{\max}}\sqrt{n}\epsilon{\bf
u}^{T}\hbox{\boldmath$\Omega$}{\bf x}+\sqrt{||\gamma{\bf x}-{\bf
x}_{0}||^{2}+n\sigma_{{\bf z}}^{2}}{\bf g}^{T}{\bf u}$ $\displaystyle-||{\bf
u}||{\bf h}^{T}(\gamma{\bf x}-{\bf x}_{0})-\frac{n}{4}||{\bf
u}||^{2}+2\lambda||{\bf x}||_{1}.$ (12)

The optimization problem in (5.3) can be seen as another primary optimization
problem (PO2). Hence, we can define another auxiliary optimization problem
(AO2) that corresponds to the new (PO2). First, let ${\bf r}\in\mathbb{R}^{m}$
and ${\bf s}\in\mathbb{R}^{n}$ be standard Gaussian vectors, then the (AO2)
can be defined as:

$\displaystyle\underset{{\bf x}}{\operatorname{\min}}\ \underset{{\bf
u}}{\operatorname{\max}}\ \epsilon||{\bf x}||{\bf r}^{T}{\bf u}-\epsilon||{\bf
u}||{\bf s}^{T}{\bf x}+\sqrt{||\gamma{\bf x}-{\bf x}_{0}||^{2}+n\sigma_{{\bf
z}}^{2}}{\bf g}^{T}{\bf u}$ $\displaystyle-||{\bf u}||{\bf h}^{T}(\gamma{\bf
x}-{\bf x}_{0})-\frac{n}{4}||{\bf u}||^{2}+2\lambda||{\bf x}||_{1}.$ (13)

Since ${\bf r}$ and ${\bf g}$ are independent standard Gaussian vectors, with
abuse of notation, we have the following:

$\epsilon||{\bf x}||{\bf r}^{T}{\bf u}+\sqrt{||\gamma{\bf x}-{\bf
x}_{0}||^{2}+n\sigma_{{\bf z}}^{2}}{\bf g}^{T}{\bf u}$ $\buildrel
d\over{=}\sqrt{||{\bf x}||^{2}+||{\bf x}_{0}||^{2}-2\gamma{\bf x}_{0}^{T}{\bf
x}+n\sigma_{{\bf z}}^{2}}{\bf g}^{T}{\bf u}.$

Therefore, the (AO2) becomes:

$\displaystyle\underset{{\bf x}}{\operatorname{\min}}\ \underset{{\bf
u}}{\operatorname{\max}}\ \sqrt{||{\bf x}||^{2}+||{\bf
x}_{0}||^{2}-2\gamma{\bf x}_{0}^{T}{\bf x}+n\sigma_{{\bf z}}^{2}}{\bf
g}^{T}{\bf u}-\frac{n}{4}||{\bf u}||^{2}$ $\displaystyle-||{\bf
u}||(\epsilon{\bf s}+\gamma{\bf h})^{T}{\bf x}+||{\bf u}||{\bf h}^{T}{\bf
x}_{0}+2\lambda||{\bf x}||_{1}.$ (14)

Fixing the norm of ${\bf u}$ to $\beta:=||{\bf u}||$, we can easily optimize
over its direction by aligning it with ${\bf g}$. Then the (AO2) simplifies
to:

$\displaystyle\underset{\beta\geq 0}{\operatorname{\max}}\ \underset{{\bf
x}}{\operatorname{\min}}\ \sqrt{n}\beta\sqrt{\frac{1}{n}(||{\bf
x}||^{2}+||{\bf x}_{0}||^{2}-2\gamma{\bf x}_{0}^{T}{\bf x})+\sigma_{{\bf
z}}^{2}}||{\bf g}||$ $\displaystyle-\beta(\epsilon{\bf s}+\gamma{\bf
h})^{T}{\bf x}+\beta{\bf h}^{T}{\bf x}_{0}-\frac{n\beta^{2}}{4}+2\lambda||{\bf
x}||_{1}.$ (15)

To have a separable optimization problem, we use the following identity:
$\sqrt{\chi}=\underset{\alpha>0}{\operatorname{\min}}\
\frac{\alpha}{2}+\frac{\chi}{2\alpha},$ where $\chi=\frac{1}{n}(||{\bf
x}||^{2}+||{\bf x}_{0}||^{2}-2\gamma{\bf x}_{0}^{T}{\bf x})+\sigma_{{\bf
z}}^{2}$. Also, define $\tau:=\frac{\sqrt{n}\alpha}{||{\bf g}||}$, and
$\tilde{{\bf h}}:=\epsilon{\bf s}+\gamma{\bf h}$. This yields the following
optimization problem:

$\displaystyle\underset{\tau>0}{\operatorname{\min}}\
\underset{\beta>0}{\operatorname{\max}}\ \frac{\beta\tau||{\bf
g}||^{2}}{2}+\frac{n\beta\sigma_{{\bf
z}}^{2}}{2\tau}-\frac{n\beta^{2}}{4}+\frac{\beta}{\gamma}(\tilde{{\bf
h}}-\epsilon{\bf s})^{T}{\bf x}_{0}$
$\displaystyle+\frac{\beta}{\tau}\biggr{(}\sum_{i=1}^{n}\frac{\epsilon^{2}}{2}{\bf
x}_{0,i}^{2}-\gamma\tilde{{\bf h}}_{i}{\bf
x}_{0,i}-\frac{\tau^{2}}{2}\tilde{{\bf h}}_{i}^{2}\biggl{)}$
$\displaystyle+\frac{\beta}{\tau}\biggr{(}\sum_{i=1}^{n}\underset{{\bf
x}_{i}}{\operatorname{\min}}\ \frac{1}{2}({\bf x}_{i}-\gamma{\bf
x}_{0,i}-\tau\tilde{{\bf h}}_{i})^{2}+\frac{2\lambda\tau}{\beta}|{\bf
x}_{i}|\biggl{)}.$ (16)

The optimization over ${\bf x}_{i}$ can be solved in a closed-form expression
using the soft-thresholding operator, which is exactly the function defined in
(3). Then, the above optimization problem simplifies to the following Scalar
Optimization (SO) problem:

$\displaystyle\underset{\tau>0}{\operatorname{\min}}\
\underset{\beta>0}{\operatorname{\max}}\ \tilde{D}(\tau,\beta,{\bf g},{\bf
h}):=\frac{\beta\tau||{\bf g}||^{2}}{2}+\frac{n\beta\sigma_{{\bf
z}}^{2}}{2\tau}-\frac{n\beta^{2}}{4}$
$\displaystyle+\frac{\beta}{\tau}\biggr{(}\sum_{i=1}^{n}\frac{\epsilon^{2}}{2}{\bf
x}_{0,i}^{2}-\gamma{\bf h}_{i}{\bf x}_{0,i}-\frac{\tau^{2}}{2}{\bf
h}_{i}^{2}\biggl{)}$ $\displaystyle+\frac{\beta}{\gamma}{\bf h}^{T}{\bf
x}_{0}+\frac{\beta}{\tau}\sum_{i=1}^{n}e\biggr{(}\gamma{\bf x}_{0,i}+\tau{\bf
h}_{i};\frac{2\lambda\tau}{\beta}\biggl{)}.$ (17)

###  5.4 Probabilistic asymptotic analysis of the (SO) problem

After simplifiying the (AO2) as in (5.3), we are now in a position to analyze
its limiting behavior. First, we need to properly normalize the objective
function in (5.3) by dividing it by $n$. Then, using the WLLN, we have:
$\frac{1}{n}||{\bf
g}||^{2}\overset{P}{\longrightarrow}\delta,\frac{1}{n}||{\bf
h}||^{2}\overset{P}{\longrightarrow}1$, $\frac{1}{n}||{\bf
x}_{0}||^{2}\overset{P}{\longrightarrow}\kappa$ and $\frac{1}{n}{\bf
h}^{T}{\bf x}_{0}\overset{P}{\longrightarrow}0$. Also, using the WLLN, it can
be shown that for all $\tau>0$ and $\beta>0$,
$\frac{1}{n}\sum_{i=1}^{n}e(\gamma{\bf x}_{0,i}+\tau{\bf
h}_{i};\frac{2\lambda\tau}{\beta})\overset{P}{\longrightarrow}\mathbb{E}[e(\gamma
X_{0}+\tau H;\frac{2\lambda\tau}{\beta})]$, and
$\frac{1}{n}\sum_{i=1}^{n}\tilde{{\bf
x}}_{i}\overset{P}{\longrightarrow}\mathbb{E}[\eta(\gamma X_{0}+\tau
H;\frac{2\lambda\tau}{\beta})]$, where $\tilde{{\bf x}}$ is the solution of
(AO2) defined in (5.3). Therefore, the point-wise convergence in $\tau$ and
$\beta$ of the objective function in (5.3) is the quantity $D(\tau,\beta)$
defined in Theorem 1. Furthermore, it is possible to show that with
probability one, the functions
$\tau\mapsto{\operatorname{\max}}_{\beta>0}\tilde{D}(\tau,\beta,{\bf g},{\bf
h})$ and $\tau\mapsto{\operatorname{\max}}_{\beta>0}D(\tau,\beta)$ are convex
in $\tau$. Hence, it is possible to show using theorem 2.7 in [17] that
$\tau_{n}({\bf g},{\bf h})\overset{P}{\longrightarrow}\tau_{*}$.

###  5.5 Applying the CGMT

We prove that the quantities $\hat{{\bf x}}-{\bf x}_{0}$ and $\tilde{{\bf
x}}-{\bf x}_{0}$ are concentarted in the same set. Formally, for any fixed
$\zeta>0$, we define the set: $\mathcal{S}=\bigl{\\{}{\bf
v}:\bigl{|}\frac{1}{n}||{\bf
v}||^{2}-M(\tau_{*},\beta_{*})\bigr{|}<\zeta\bigr{\\}}$, where
$M(\tau_{*},\beta_{*})=\delta\tau_{*}^{2}-\sigma_{{\bf
z}}^{2}+2(\gamma-1)\mathbb{E}[\eta(\gamma
X_{0}+\tau_{*}H;\frac{2\lambda\tau_{*}}{\beta_{*}})X_{0}]$, and $\tau_{*}$ and
$\beta_{*}$ are as defined in Theorem 1. Let $\check{{\bf x}}$ be the solution
of (AO1) defined in (5.3). The error can be written as: $||\tilde{{\bf
x}}-{\bf x}_{0}||^{2}=||\tilde{{\bf w}}||^{2}+2(\gamma-1)\tilde{{\bf
x}}^{T}{\bf x}_{0}$. Recall that $\tau_{n}({\bf g},{\bf
h})=\frac{\sqrt{n}}{||{\bf g}||}\sqrt{\frac{1}{n}||\tilde{{\bf
w}}||^{2}+\sigma_{{\bf z}}^{2}}$. Using $\tau_{n}({\bf g},{\bf
h})\overset{P}{\longrightarrow}\tau_{*}$, we find $\frac{||\tilde{{\bf
w}}||^{2}}{n}\overset{P}{\longrightarrow}\delta\tau_{*}^{2}-\sigma_{{\bf
z}}^{2}$. Also, it can be shown that $\frac{1}{n}\tilde{{\bf x}}^{T}{\bf
x}_{0}\overset{P}{\longrightarrow}\mathbb{E}[\eta(\gamma
X_{0}+\tau_{*}H;\frac{2\lambda\tau_{*}}{\beta_{*}})X_{0}]$. Putting all the
results together, it can be shown that $\frac{1}{n}||\tilde{{\bf x}}-{\bf
x}_{0}||^{2}\overset{P}{\longrightarrow}M(\tau_{*},\beta_{*})$. This proves
that for any $\zeta$, $\tilde{{\bf x}}-{\bf x}_{0}\in\mathcal{S}$ with
probability one. Then, we conclude using the CGMT that $\check{{\bf x}}-{\bf
x}_{0}\in\mathcal{S}$ with probability one. A second application of the CGMT
is needed to conclude that $\hat{{\bf x}}-{\bf x}_{0}\in\mathcal{S}$ with
probability one and is omitted for space considerations. This completes the
proof of Theorem 1.

##  6 Conclusion

In this paper, we proposed a precise asymptotic analysis of the MSE and the
probability of support recovery of the LASSO under imperfect Gaussian
measurement matrix assumptions. Although our analysis is asymptotic in nature,
numerical simulations show that our theoretical predictions are valid even for
a few dozens of the problem dimensions.

## References

  * [1] Robert Tibshirani,  “Regression shrinkage and selection via the lasso,”  Journal of the Royal Statistical Society. Series B (Methodological), pp. 267–288, 1996.
  * [2] Michael Ting, Raviv Raich, and Alfred O Hero III,  “Sparse image reconstruction for molecular imaging,”  IEEE Transactions on Image Processing, vol. 18, no. 6, pp. 1215–1227, 2009.
  * [3] Christopher M Bishop,  “Pattern recognition,”  Machine Learning, vol. 128, pp. 1–58, 2006.
  * [4] Guan Gui, Wei Peng, and Ling Wang,  “Improved sparse channel estimation for cooperative communication systems,”  International Journal of Antennas and Propagation, vol. 2012, 2012\.
  * [5] Emmanuel J Candes, Justin K Romberg, and Terence Tao,  “Stable signal recovery from incomplete and inaccurate measurements,”  Communications on pure and applied mathematics, vol. 59, no. 8, pp. 1207–1223, 2006.
  * [6] Emmanuel Candes and Terence Tao,  “The dantzig selector: Statistical estimation when p is much larger than n,”  The Annals of Statistics, pp. 2313–2351, 2007.
  * [7] Peter J Bickel, Ya’acov Ritov, and Alexandre B Tsybakov,  “Simultaneous analysis of lasso and dantzig selector,”  The Annals of Statistics, pp. 1705–1732, 2009.
  * [8] Sahand Negahban, Bin Yu, Martin J Wainwright, and Pradeep K Ravikumar,  “A unified framework for high-dimensional analysis of $m$-estimators with decomposable regularizers,”  in Advances in Neural Information Processing Systems, 2009, pp. 1348–1356.
  * [9] David L Donoho, Arian Maleki, and Andrea Montanari,  “Message-passing algorithms for compressed sensing,”  Proceedings of the National Academy of Sciences, vol. 106, no. 45, pp. 18914–18919, 2009.
  * [10] Mohsen Bayati and Andrea Montanari,  “The dynamics of message passing on dense graphs, with applications to compressed sensing,”  IEEE Transactions on Information Theory, vol. 57, no. 2, pp. 764–785, 2011.
  * [11] Mohsen Bayati and Andrea Montanari,  “The lasso risk for gaussian matrices,”  IEEE Transactions on Information Theory, vol. 58, no. 4, pp. 1997–2017, 2012.
  * [12] Christos Thrampoulidis, Ehsan Abbasi, and Babak Hassibi,  “Precise error analysis of regularized m-estimators in high-dimensions,”  arXiv preprint arXiv:1601.06233, 2016.
  * [13] Ehsan Abbasi, Christos Thrampoulidis, and Babak Hassibi,  “General performance metrics for the lasso,”  in Information Theory Workshop (ITW), 2016 IEEE. IEEE, 2016, pp. 181–185.
  * [14] Mathieu Rosenbaum, Alexandre B Tsybakov, et al.,  “Sparse recovery under matrix uncertainty,”  The Annals of Statistics, vol. 38, no. 5, pp. 2620–2651, 2010.
  * [15] Mohamed Ridha Zenaidi, Zouheir Rezki, Hamidou Tembine, and Mohamed-Slim Alouini,  “Performance limits of energy harvesting communications under imperfect channel state information,”  in Communications (ICC), 2016 IEEE International Conference on. IEEE, 2016, pp. 1–6.
  * [16] Martin J Wainwright,  “Sharp thresholds for high-dimensional and noisy sparsity recovery using -constrained quadratic programming (lasso),”  IEEE transactions on information theory, vol. 55, no. 5, pp. 2183–2202, 2009.
  * [17] Whitney K Newey and Daniel McFadden,  “Large sample estimation and hypothesis testing,”  Handbook of econometrics, vol. 4, pp. 2111–2245, 1994.
  * [18] Mihailo Stojnic,  “Recovery thresholds for ℓ 1 optimization in binary compressed sensing,”  in Information Theory Proceedings (ISIT), 2010 IEEE International Symposium on. IEEE, 2010, pp. 1593–1597.
  * [19] Mihailo Stojnic,  “A framework to characterize performance of lasso algorithms,”  arXiv preprint arXiv:1303.7291, 2013.
  * [20] Christos Thrampoulidis, Samet Oymak, and Babak Hassibi,  “Regularized linear regression: A precise analysis of the estimation error.,”  in COLT, 2015, pp. 1683–1709.
  * [21] Christos Thrampoulidis, Ehsan Abbasi, and Babak Hassibi,  “Lasso with non-linear measurements is equivalent to one with linear measurements,”  in Advances in Neural Information Processing Systems, 2015, pp. 3420–3428.
  * [22] Christos Thrampoulidis, Ashkan Panahi, Daniel Guo, and Babak Hassibi,  “Precise error analysis of the lasso,”  in Acoustics, Speech and Signal Processing (ICASSP), 2015 IEEE International Conference on. IEEE, 2015, pp. 3467–3471.


# Toy model illustrating the effect of measurement dependence on a Bell
inequality

Sophia M. Walls and Ian J. Ford  Department of Physics and Astronomy,
University College London, Gower Street, London, WC1E 6BT, United Kingdom

###### Abstract

Bell’s inequalities rely on the assumption of measurement independence, namely
that the probabilities of adopting configurations of hidden variables
describing a system prior to measurement are independent of the choice of
physical property that will be measured. Weakening this assumption can change
the inequalities to accommodate experimental data. We illustrate this by
considering quantum measurement to be the dynamical evolution of hidden
variables to attractors in their phase space that correspond to eigenstates of
system observables. The probabilities of adopting configurations of these
variables prior to measurement then depend on the choice of physical property
measured by virtue of the boundary conditions acting on the dynamics. Allowing
for such measurement dependence raises the upper limit of the CHSH parameter
in Bell’s analysis of an entangled pair of spin half particles subjected to
measurement of spin components along various axes, whilst maintaining local
interactions. We demonstrate how this can emerge and illustrate the relaxed
upper limit using a simple toy model of dynamical quantum measurement. The
conditioning of the hidden variable probability distribution on the chosen
measurement settings can persist far back in time in certain situations, a
memory that could explain the correlations exhibited in an entangled quantum
system.

Bell inequalities arise from analysis of the statistics of purported ‘hidden
variables’ that evolve according to local interactions and represent ‘elements
of reality’ with definite values prior to measurement. It has been
demonstrated that the inequalities can be violated, with recent experiments
removing areas of uncertainty in the analysis such as the fair-sampling and
locality loopholes [1, 2, 3, 4, 5, 6, 7]. Perhaps the most striking aspect of
quantum mechanics is that its predictions are consistent with these
violations. The implication is either that physical effects operate non-
locally between space-like separated points, or that we have to abandon the
concept of a reality independent of observation at microscopic scales [8, 9].

Should we wish to avoid these (arguably) unpalatable conclusions it is
necessary to examine the assumptions made in Bell’s analysis, one of which is
‘measurement independence’, or ‘statistical independence’ [10], according to
which the system prior to measurement is assumed to adopt states with
probabilities that are independent of the measurement settings. A stronger
version is that the prior state of a system should be capable of providing a
measurement outcome for any system property.

We examine the effect of relaxing this assumption in the standard situation
where two spin half particles in an entangled state have spin components
separately measured along arbitrarily chosen axes. We demonstrate, by
introducing measurement dependence, that the upper bound of the Clauser-Horne-
Shimony-Holt (CHSH) parameter,
$S(\hat{a},\hat{b},\hat{a}^{\prime},\hat{b}^{\prime})$, defined as [11]

$S=|C(\hat{a},\hat{b})-C(\hat{a},\hat{b}^{\prime})|+|C(\hat{a}^{\prime},\hat{b})+C(\hat{a}^{\prime},\hat{b}^{\prime})|,$
(1)

can be increased. $C(\hat{a},\hat{b})$ is the correlation function of spin
component measurement outcomes $A$ and $B$ (each taking values $\pm$1) for
particle 1 undergoing a spin measurement along axis $\hat{a}$ and particle 2
along axis $\hat{b}$, respectively, namely
$C(\hat{a},\hat{b})=\overline{AB}=P_{++}^{\hat{a},\hat{b}}-P_{+-}^{\hat{a},\hat{b}}-P_{-+}^{\hat{a},\hat{b}}+P_{--}^{\hat{a},\hat{b}}$
where $P_{\pm\pm}^{\hat{a},\hat{b}}$ are the probabilities of measurement
outcomes $A=\pm 1,B=\pm 1$ along the respective axes. Each correlation
function takes a value between $\pm 1$ and $S$ could therefore lie between 0
and 4. However, assuming that the outcome of measurement of particle 2 is
influenced neither by the choice of axis setting nor the outcome of
measurement of particle 1, and vice versa, and also assuming that the system
prior to measurement is specified by a set of hidden variables $\lambda$
adopted according to a probability density function (pdf) $\rho(\lambda)$,
then $P_{\pm\pm}^{\hat{a},\hat{b}}=\int
p_{1\pm}^{\hat{a}}(\lambda)p_{2\pm}^{\hat{b}}(\lambda)\rho(\lambda)d\lambda$
where $p_{1\pm}^{\hat{a}}(\lambda)$ are the probabilities of outcomes $\pm 1$
for the spin component of particle 1 along axis $\hat{a}$, for a given
specification of hidden variables, with a similar meaning for
$p_{2\pm}^{\hat{b}}(\lambda)$. Bell’s analysis requires $S$ to have an upper
bound of 2. The crucial observation is that

$|\bar{B}(\hat{b},\lambda)\\!-\\!\bar{B}(\hat{b}^{\prime},\lambda)|+|\bar{B}(\hat{b},\lambda)\\!+\\!\bar{B}(\hat{b}^{\prime},\lambda)|\leq
2,$ (2)

where
$\bar{B}(\hat{b},\lambda)=p_{2+}^{\hat{b}}(\lambda)-p_{2-}^{\hat{b}}(\lambda)$
is the mean outcome of measurement of the spin component of particle 2 along
axis $\hat{b}$ for a given set of hidden variables $\lambda$. Note also that
$|\bar{B}(\hat{b},\lambda)|\leq 1$. It has been shown that this upper bound
can be violated experimentally.

Measurement independence is the use in the analysis of a pdf $\rho(\lambda)$
that depends neither on the measurement axes nor the outcome of the
measurement. This can seem reasonable unless we entertain the view that
measurement is a dynamical process. The usual alternatives to this are the
classical acquisition of information without changing the system state, or the
quantum mechanical instantaneous projection of the system to one of the
eigenstates of the measured property. Instead, it could conceivably involve
the evolution of hidden variables, that specify the states of the system and a
coupled measuring device, towards attractors in their phase space that
correspond to system eigenstates and device readings correlated with those
eigenstates. This would create a relationship between initial state
probabilities and the final measurement outcomes that act as boundary
conditions. We could also imagine that deterministic rules could govern the
evolution of the complete set of hidden variables while those describing the
system alone could evolve stochastically, reflecting uncertainty in the
initial state of the measuring device.

This point of view suggests that probabilities of hidden variable
configurations might reasonably be conditioned on events taking place in the
future, also known as ‘future input dependence’ [10, 12]. This is as natural
as deducing the statistics of the position and velocity of a tennis ball, at
the moment when it is struck by a racket, using information on where and how
it later strikes the ground, assuming deterministic Newtonian dynamics,
perhaps supplemented by stochastic environmental effects such as air currents.
If measurement is dynamical, then the choice of the axes in a spin measurement
experiment, and indeed the outcome of the measurement, could similarly convey
information about the initial states adopted by the system and device.

The amount of measurement dependence required to reproduce the observed
violations of the CHSH upper limit has been quantified through a number of
parameters, such as the amount of mutual information shared between the
detectors and the hidden variables describing the entangled particle pair; a
distance measure quantifying the overlap or degree of distinguishability of
different choices of settings; or by requiring the probability of choosing
certain settings to be within a particular range [13, 14, 15, 16]. It has been
shown that the upper bound of the Bell inequalities may be relaxed by removing
all freedom of choice of settings [17]. It has subsequently been demonstrated
that only 0.046-0.080 bits of shared information is required to reproduce
quantum correlations for retrocausal or causal models [14, 16, 15, 13]. More
elaborate scenarios have also been studied [14, 18] and investigations have
been carried out into how measurement dependence and Bell inequality violation
are affected by imperfect measuring devices, and the role measurement
dependence has in randomness amplification and quantum causality [19, 20, 21,
22, 23, 24, 25, 26, 27, 28, 29, 30].

Experimental advances have also been made in an attempt to close the
‘measurement-dependence loophole’ by allowing measurement settings to be
chosen by random number generators, the wavelength of light from distant
quasars or stars, or participants in a video game [31, 32, 33, 34, 35]. Such
arrangements can indeed establish correlations between the settings and
distant or highly complex dynamical influences. We nonetheless take the view
that the settings, however they are determined, can still provide information
about the system variables prior to measurement, when the process of
measurement is dynamical. The question is then not how the measurement
settings are determined but how much such settings condition the system
variables prior to measurement. Such an effect is not retrocausality, but
instead a process of inference regarding the uncertain initial state of the
system.

Violation of measurement independence has the potential to render vulnerable
to attack any entanglement-based technologies that rely on true quantum
randomness. This particularly concerns quantum cybersecurity and encryption,
where it is possible that an adversary could exploit measurement dependence to
gain access [36, 37, 38, 39, 40, 41, 42, 43, 44, 45].

The effect of measurement dependence on the upper limit placed on the CHSH
parameter has been examined before [46, 47, 13, 18, 48, 49, 14] but our
analysis is novel since it rests on the dynamical evolution of the hidden
variables during measurement. We use a toy model, to explore conditions for
which the effect could be significant.

To be specific, let us imagine that quantum measurement drives hidden system
variables $\lambda$ towards measurement axis-dependent regions in their phase
space that correspond to spin component outcomes for those axis orientations.
The chosen measurement axes and the evolution model allow us, in principle, to
deduce the probability density over configurations of $\lambda$ prior to
measurement. The pdf $\rho$ is therefore conditioned on the choice of axes,
such that the correlation function should be written

$C(\hat{a},\hat{b})=\int\bar{A}(\hat{a},\lambda)\bar{B}(\hat{b},\lambda)\rho(\lambda|\hat{a},\hat{b})d\lambda,$
(3)

using previous notation extended to indicate the conditioning of $\rho$. We
still assume that the mean outcome of spin component measurement for particle
1 along axis $\hat{a}$ does not depend on the orientation of axis $\hat{b}$
specifying the spin component measurement of particle 2, and vice versa, so
the average of $AB$ given $\hat{a}$, $\hat{b}$ and $\lambda$ factorises,
namely
$\overline{AB}(\hat{a},\hat{b},\lambda)=\bar{A}(\hat{a},\lambda)\bar{B}(\hat{b},\lambda)$.

The CHSH parameter is built from correlation functions involving four pairs of
measurement axes, and hence four conditioned pdfs over $\lambda$, which we
denote $\rho(\lambda|\hat{a},\hat{b})$,
$\rho(\lambda|\hat{a},\hat{b}^{\prime})$,
$\rho(\lambda|\hat{a}^{\prime},\hat{b})$ and
$\rho(\lambda|\hat{a}^{\prime},\hat{b}^{\prime})$. We can use these to define
a normalised average pdf
$\bar{\rho}(\lambda,\hat{a},\hat{b},\hat{a}^{\prime},\hat{b}^{\prime})=\frac{1}{4}\left(\rho(\lambda|\hat{a},\hat{b})+\rho(\lambda|\hat{a},\hat{b}^{\prime})+\rho(\lambda|\hat{a}^{\prime},\hat{b})+\rho(\lambda|\hat{a}^{\prime},\hat{b}^{\prime})\right)$
together with combinations that describe the differences between them:

$\displaystyle\bar{\rho}\epsilon$
$\displaystyle=\frac{1}{4}\\!\left(\rho(\lambda|\hat{a},\hat{b})-\rho(\lambda|\hat{a},\hat{b}^{\prime})+\rho(\lambda|\hat{a}^{\prime},\hat{b})-\rho(\lambda|\hat{a}^{\prime},\hat{b}^{\prime})\right)$
$\displaystyle\bar{\rho}\sigma$
$\displaystyle=\frac{1}{4}\\!\left(\rho(\lambda|\hat{a},\hat{b})+\rho(\lambda|\hat{a},\hat{b}^{\prime})-\rho(\lambda|\hat{a}^{\prime},\hat{b})-\rho(\lambda|\hat{a}^{\prime},\hat{b}^{\prime})\right)$
$\displaystyle\bar{\rho}\eta$
$\displaystyle=\frac{1}{4}\\!\left(\rho(\lambda|\hat{a},\hat{b})-\rho(\lambda|\hat{a},\hat{b}^{\prime})-\rho(\lambda|\hat{a}^{\prime},\hat{b})+\rho(\lambda|\hat{a}^{\prime},\hat{b}^{\prime})\right),$
(4)

such that
$\rho(\lambda|\hat{a},\hat{b})=\bar{\rho}\left(1+\epsilon+\sigma+\eta\right)$,
$\rho(\lambda|\hat{a},\hat{b}^{\prime})=\bar{\rho}\left(1-\epsilon+\sigma-\eta\right)$,
$\rho(\lambda|\hat{a}^{\prime},\hat{b})=\bar{\rho}\left(1+\epsilon-\sigma-\eta\right)$,
and
$\rho(\lambda|\hat{a}^{\prime},\hat{b}^{\prime})=\bar{\rho}\left(1-\epsilon-\sigma+\eta\right)$.
The $\epsilon$, $\sigma$ and $\eta$ functions depend on all four axis
orientations as well as $\lambda$.

Now consider the first combination of correlation functions in the CHSH
parameter, $C(\hat{a},\hat{b})-C(\hat{a},\hat{b}^{\prime})$. By introducing
conditioning of the probability densities according to the chosen measurement
axes this can written as

$\displaystyle\int\bar{A}(\hat{a},\lambda)\left(\bar{B}(\hat{b},\lambda)\rho(\lambda|\hat{a},\hat{b})-\bar{B}(\hat{b}^{\prime},\lambda)\rho(\lambda|\hat{a},\hat{b}^{\prime})\right)d\lambda$
$\displaystyle=\int\bar{A}(\hat{a},\lambda)\left(\bar{B}(\hat{b},\lambda)-\bar{B}(\hat{b}^{\prime},\lambda)\right)\bar{\rho}(\lambda)d\lambda$
$\displaystyle+\int\bar{A}(\hat{a},\lambda)\left(\bar{B}(\hat{b},\lambda)+\bar{B}(\hat{b}^{\prime},\lambda)\right)\bar{\rho}(\lambda)\epsilon(\lambda)d\lambda$
$\displaystyle+\int\bar{A}(\hat{a},\lambda)\left(\bar{B}(\hat{b},\lambda)-\bar{B}(\hat{b}^{\prime},\lambda)\right)\bar{\rho}(\lambda)\sigma(\lambda)d\lambda$
$\displaystyle+\int\bar{A}(\hat{a},\lambda)\left(\bar{B}(\hat{b},\lambda)+\bar{B}(\hat{b}^{\prime},\lambda)\right)\bar{\rho}(\lambda)\eta(\lambda)d\lambda,$
(5)

which, since $|\bar{A}(\hat{a},\lambda)|\leq 1$, implies that

$\displaystyle|C(\hat{a},\hat{b})-C(\hat{a},\hat{b}^{\prime})|\leq\int\left|\bar{B}(\hat{b},\lambda)-\bar{B}(\hat{b}^{\prime},\lambda)\right|\bar{\rho}(\lambda)d\lambda$
$\displaystyle+\int\left|\bar{B}(\hat{b},\lambda)+\bar{B}(\hat{b}^{\prime},\lambda)\right|\bar{\rho}(\lambda)|\epsilon(\lambda)|d\lambda$
$\displaystyle+\int\left|\bar{B}(\hat{b},\lambda)-\bar{B}(\hat{b}^{\prime},\lambda)\right|\bar{\rho}(\lambda)|\sigma(\lambda)|d\lambda$
$\displaystyle+\int\left|\bar{B}(\hat{b},\lambda)+\bar{B}(\hat{b}^{\prime},\lambda)\right|\bar{\rho}(\lambda)|\eta(\lambda)|d\lambda.$
(6)

Similarly the combination
$C(\hat{a}^{\prime},\hat{b})+C(\hat{a}^{\prime},\hat{b}^{\prime})$ may be
written

$\displaystyle\int\bar{A}(\hat{a}^{\prime},\lambda)\left(\bar{B}(\hat{b},\lambda)\rho(\lambda|\hat{a}^{\prime},\hat{b})+\bar{B}(\hat{b}^{\prime},\lambda)\rho(\lambda|\hat{a}^{\prime},\hat{b}^{\prime})\right)d\lambda$
$\displaystyle=\int\bar{A}(\hat{a}^{\prime},\lambda)\left(\bar{B}(\hat{b},\lambda)+\bar{B}(\hat{b}^{\prime},\lambda)\right)\bar{\rho}(\lambda)d\lambda$
$\displaystyle+\int\bar{A}(\hat{a}^{\prime},\lambda)\left(\bar{B}(\hat{b},\lambda)-\bar{B}(\hat{b}^{\prime},\lambda)\right)\bar{\rho}(\lambda)\epsilon(\lambda)d\lambda$
$\displaystyle+\int\bar{A}(\hat{a}^{\prime},\lambda)\left(-\bar{B}(\hat{b},\lambda)-\bar{B}(\hat{b}^{\prime},\lambda)\right)\bar{\rho}(\lambda)\sigma(\lambda)d\lambda$
$\displaystyle+\int\bar{A}(\hat{a}^{\prime},\lambda)\left(-\bar{B}(\hat{b},\lambda)+\bar{B}(\hat{b}^{\prime},\lambda)\right)\bar{\rho}(\lambda)\eta(\lambda)d\lambda,$
(7)

which, since $|\bar{A}(\hat{a},\lambda)|\leq 1$, leads to

$\displaystyle|C(\hat{a}^{\prime},\hat{b})+C(\hat{a}^{\prime},\hat{b}^{\prime})|\leq\int\left|\bar{B}(\hat{b},\lambda)+\bar{B}(\hat{b}^{\prime},\lambda)\right|\bar{\rho}(\lambda)d\lambda$
$\displaystyle+\int\left|\bar{B}(\hat{b},\lambda)-\bar{B}(\hat{b}^{\prime},\lambda)\right|\bar{\rho}(\lambda)|\epsilon(\lambda)|d\lambda$
$\displaystyle+\int\left|\bar{B}(\hat{b},\lambda)+\bar{B}(\hat{b}^{\prime},\lambda)\right|\bar{\rho}(\lambda)|\sigma(\lambda)|d\lambda$
$\displaystyle+\int\left|\bar{B}(\hat{b},\lambda)-\bar{B}(\hat{b}^{\prime},\lambda)\right|\bar{\rho}(\lambda)|\eta(\lambda)|d\lambda.$
(8)

Combining Eqs. (6), (8) and (2), the CHSH parameter satisfies

$\displaystyle S$ $\displaystyle\leq 2+\mu,$ (9)

where
$\mu=2\left(\int\bar{\rho}|\epsilon|d\lambda+\int\bar{\rho}|\sigma|d\lambda+\int\bar{\rho}|\eta|d\lambda\right)\geq
0$ represents an elevation of the usual upper limit. Note that
$\epsilon=\sigma=\eta=0$ and hence $\mu=0$ in the absence of measurement
dependence. Also, if only one of the four probability densities is non-zero
for a given $\lambda$, an extreme case of measurement dependence, then
$\bar{\rho}|\epsilon|$, $\bar{\rho}|\sigma|$ and $\bar{\rho}|\eta|$ are all
normalised to unity, in which case $\mu=6$. Values of $\mu$ above 2 are
redundant since $S$ cannot exceed 4.

Figure 1: A discrete representation of the basins of attraction, over a phase
space of configurations of hidden variables, associated with four measurement
outcomes shown as crosses. All the configurations denoted by one of the four
shades of grey evolve under measurement towards the appropriately shaded
attractor coordinate pair $\left(\lambda_{1}^{\pm},\lambda_{2}^{\pm}\right)$
indicated by a cross $\times$. Situations (a) and (b) correspond to
measurement of different system properties with distinct sets (colours) of
attractors and associated basins.

The rather abstract discussion given so far can be illustrated using a toy
model. Consider a system described by two discrete hidden variables
$\lambda_{1,2}$ and a phase space in the form of a grid of squares labelled
with integer values. The measurement of properties $A$ and $B$ is represented
by attraction of each of $\lambda_{1}$ and $\lambda_{2}$ towards one of two
points, yielding four ‘targets’ at coordinates
$\left(\lambda_{1}^{\pm},\lambda_{2}^{\pm}\right)$. The idea is that
interactions between the system and measuring device bring about a dynamical
evolution of the $\lambda_{1,2}$ to attractors (here fixed points) located at
the targets. The outcome of the measurement of each property is $\pm$1, as
designated by the superscripts on the target coordinates.

We consider a particular situation where passage to each target arises from
separate basins of attraction, shown as four different shades of grey. For
example, in Figure 1(a) the measurement dynamics generate trajectories
starting from any of the black squares and all terminating at
$(\lambda_{1}^{+},\lambda_{2}^{+})$.

If there were information on the probabilities of adopting each black square
prior to measurement, then we would reasonably deduce from the dynamics that
these would accumulate to provide a probability $P_{++}$ of an outcome
$A=B=+1$ associated with system arrival at the
$(\lambda_{1}^{+},\lambda_{2}^{+})$ target. The suffixes in this probability
correspond to the superscripts on the target coordinates. However, we instead
wish to deduce the probabilities of having started out on a black square
conditioned on information about the type of measurement performed and its
outcome. Given that the probability of arrival at
$(\lambda_{1}^{+},\lambda_{2}^{+})$ after measurement is $P_{++}$, we need to
distribute this probability appropriately over the basin of attraction of that
target at earlier times, in accordance with the measurement dynamics. The
probability distribution in the past is conditioned on _future_ information:
this is the measurement dependence under consideration.

We can now see how such conditioned probabilities would change if the
measurement concerned a different property, represented in the toy model as
attraction towards a different set of targets. Consider the shifted targets
represented by the green crosses in Figure 1(b). The basins of attraction
under the measurement dynamics would, in general, form a different pattern for
these targets. There are therefore revised probabilities of adoption of
configurations prior to measurement when conditioned on a measurement process
defined by the green crosses. This is compounded if we consider sets of
probabilities of arrival $P_{\pm\pm}$ (outcome probabilities) at the green and
red targets that differ from one another.

It is crucial for the emergence of measurement dependence in this toy model
that the phase space should separate into a set of basins of attraction to
each outcome target for each measurement situation. In real systems where the
evolution is deterministic, outcomes are encoded in the coordinates describing
the initial state and such a situation would be natural. For systems governed
by effective stochastic dynamics arising from coupling to an uncertain
environment, such encoding could persist to some degree depending on the
situation.

Figure 2: Configurations of the toy model are represented by grid squares in a
two dimensional discrete phase space with integer coordinates $\lambda_{1}$
and $\lambda_{2}$. Measurement dynamics draws the configuration towards one of
four targets, shown as crosses in a specific colour, representing the four
outcomes of measurement of properties $A$ and $B$. Four different experimental
circumstances are designated by labels $\hat{a},\hat{b}$, etc, and
distinguished by different colours. Arrival at one of the targets yields an
outcome $A=\pm 1$ and $B=\pm 1$ according to the superscripts of the
$\lambda_{1}$ and $\lambda_{2}$ target coordinates, and the probability of
such an outcome is indicated by coloured circles at the targets. The darker
the shade, the higher the probability $P_{\pm\pm}^{\hat{x},\hat{y}}$ of
arrival at that target.

We now illustrate how a CHSH parameter greater than 2 can be accommodated
through this measurement dependence. In Figure 2 we define four sets of
targets based on the pairs of positions towards which the measurement dynamics
drive the variables $\lambda_{1,2}$. The target pairs $\lambda_{1}^{\pm}$ and
$\bar{\lambda}_{1}^{\pm}$ will be labelled ‘axis choices’ $\hat{a}$ and
$\hat{a}^{\prime}$, respectively, and $\lambda_{2}^{\pm}$ and
$\bar{\lambda}_{2}^{\pm}$ are to be associated with ‘axes’ $\hat{b}$ and
$\hat{b}^{\prime}$.The terminology is chosen to establish an analogy with spin
component measurement and the superscripts indicate the outcome values for
properties $A$and $B$. Four measurement situations can then be considered,
specified by the choice of blue, red, purple or green targets. The possible
measurement outcomes of $A$ and $B$ can be correlated $(\pm 1,\pm 1)$ or anti-
correlated ($\pm 1,\mp 1)$. In Figure 2 we associate +1 outcomes with targets
situated at even label positions on the grid and $-1$ outcomes with odd
labels.

We can then consider a set of probabilities $P_{\pm\pm}^{\hat{x},\hat{y}}$ for
arrival of the system after measurement at the four targets in each group, for
$\hat{x}=\hat{a}$ or $\hat{a}^{\prime}$ and $\hat{y}=\hat{b}$ or
$\hat{b}^{\prime}$. These are shown in Figure 2 as circular symbols with
different shades of colour to indicate magnitude. To simplify the situation,
we impose conditions $P_{++}^{\hat{x},\hat{y}}=P_{--}^{\hat{x},\hat{y}}$ and
$P_{+-}^{\hat{x},\hat{y}}=P_{-+}^{\hat{x},\hat{y}}$. Furthermore, we consider
identical outcome probabilities for the red, blue and purple measurement
situations, namely
$P_{\pm\pm}^{\hat{a},\hat{b}}=P_{\pm\pm}^{\hat{a}^{\prime},\hat{b}}=P_{\pm\pm}^{\hat{a}^{\prime},\hat{b}^{\prime}}$.
However, we design the green measurement situation to be different by setting
$P_{\pm\mp}^{\hat{a},\hat{b}^{\prime}}=P_{\pm\pm}^{\hat{a},\hat{b}}$, namely
that dark and light shades of green characterise measurement outcomes coloured
in light and dark shades, respectively, for the other three cases.We can then
combine this information with a chosen pattern of basins of attraction
associated with each target to derive the conditioned probabilities over the
phase space prior to measurement for each pair of chosen ‘axes’. Our aim is to
produce a probability distribution $P(\lambda_{1,2}|\hat{a},\hat{b}^{\prime})$
over the phase space conditioned on outcomes at the green targets that differs
from those conditioned on the blue, red and purple targets, which for
simplicity we shall choose to be the same, namely
$P(\lambda_{1,2}|\hat{a},\hat{b})=P(\lambda_{1,2}|\hat{a}^{\prime},\hat{b})=P(\lambda_{1,2}|\hat{a}^{\prime},\hat{b}^{\prime})\neq
P(\lambda_{1,2}|\hat{a},\hat{b}^{\prime})$.The prior distribution over the
hidden variables $\lambda_{1,2}$ then clearly depends on the measurement
situation. For the green measurement situation, there would be a higher
probability associated with the anti-correlated measurement outcomes, whereas
correlated outcomes would be more probable if any of the other three
measurement situations were considered.

Notice that our approach is to start with the correlation functions for each
measurement situation and then to deduce the conditioned probability
distributions on the phase space prior to measurement. In this way we can
construct a CHSH parameter of any magnitude between zero and 4 but we then
need to establish that such a parameter is compatible with an extended upper
limit by virtue of the additional term $\mu$ in Eq. (9) arising from
differences in the conditioned prior probabilities.

We consider measurement dynamics that generate independent random walks in two
dimensions with $|\Delta\lambda_{1}|=|\Delta\lambda_{2}|=2$ per timestep,
terminating at a target. We imagine that such a stochastic scheme can emerge
from the deterministic dynamics of the system together with a measuring device
whose initial state is uncertain. The scheme means that the basin of
attraction leading to a target where both $\lambda_{1}$ and $\lambda_{2}$ are
even is comprised of all locations in the phase space with similarly even-even
coordinates. The basin of attraction leading to a target where $\lambda_{1}$
is even and $\lambda_{2}$ is odd consists of all locations with even-odd
coordinates, and so on. Separate basins of attraction to each outcome are
maintained. We also assume a phase space with an even number of locations in
each dimension ($N$ locations in all) and periodic boundary conditions. This
means that the probability $P(\lambda_{1,2}|\hat{a},\hat{b})$ at any even-even
location in the phase space, at a sufficiently large interval of time prior to
measurement with settings $\hat{a},\hat{b}$, is a constant
$P_{ee}^{\hat{a},\hat{b}}$ given by the probability of arrival
$P_{++}^{\hat{a},\hat{b}}$ at red target $(\lambda_{1}^{+},\lambda_{2}^{+})$
divided by the number of such locations, $N/4$, which is
$P_{ee}^{\hat{a},\hat{b}}=4P_{++}^{\hat{a},\hat{b}}/N$. Similarly, the
conditioned probability $P_{eo}^{\hat{a},\hat{b}}$ at an even-odd location on
the grid at such a time prior to measurement is the arrival probability
$P_{+-}^{\hat{a},\hat{b}}$ at red target $(\lambda_{1}^{+},\lambda_{2}^{-})$
divided equally between all even-odd locations in the grid, or
$P_{eo}^{\hat{a},\hat{b}}=4P_{+-}^{\hat{a},\hat{b}}/N$. The conditioned
probability at an odd-even location is
$P_{oe}^{\hat{a},\hat{b}}=4P_{-+}^{\hat{a},\hat{b}}/N$ and for odd-odd
locations it is $P_{oo}^{\hat{a},\hat{b}}=4P_{--}^{\hat{a},\hat{b}}/N$. The
same arguments apply to measurement situation $\hat{a},\hat{b}^{\prime}$ with
arrival probabilities $P_{\pm\pm}^{\hat{a},\hat{b}^{\prime}}$ at green
targets, measurement situation $\hat{a}^{\prime},\hat{b}$ with arrival
probabilities $P_{\pm\pm}^{\hat{a}^{\prime},\hat{b}}$ at blue targets, and
measurement situation $\hat{a}^{\prime},\hat{b}^{\prime}$ with arrival
probabilities $P_{\pm\pm}^{\hat{a}^{\prime},\hat{b}^{\prime}}$ at purple
targets.

Figure 3: Probability distributions characterising the adoption of toy model
configurations prior to measurement of property $AB$ in experimental
circumstances (a) $\hat{a},\hat{b}$ and (b) $\hat{a},\hat{b}^{\prime}$, shown
on the left and right in pink and green, respectively, with the shades
representing magnitude. These are conditioned on (i) the locations of the
targets in the grid, to which the configurations are attracted by measurement
dynamics consisting of independent symmetric random walks in $\lambda_{1}$ and
$\lambda_{2}$ with a step length of 2, and (ii) on the overall probabilities
of reaching each of the targets. Notice that the two conditioned probability
distributions differ, which is measurement dependence.

What this means is that the conditioned probabilities on the phase space are
repeated versions of the patterns of probabilities of arrival at the targets
after measurement. This is illustrated in Figure 3(a) for the
$\hat{a},\hat{b}$ measurement situation. The dark and light shades of pink
represent the two probabilities $P_{ee}^{\hat{a},\hat{b}}$ and
$P_{eo}^{\hat{a},\hat{b}}$, respectively, recalling that we have imposed
$P_{ee}^{\hat{a},\hat{b}}=P_{oo}^{\hat{a},\hat{b}}$ and
$P_{eo}^{\hat{a},\hat{b}}=P_{oe}^{\hat{a},\hat{b}}$. The distribution
$P(\lambda_{1,2}|\hat{a},\hat{b})$ illustrated is the discrete analogue of the
pdf $\rho(\lambda|\hat{a},\hat{b})$ considered for the spin measurement
situation. With the assumptions we have made, the conditioned probability
distributions for measurement situations $\hat{a}^{\prime},\hat{b}$ and
$\hat{a}^{\prime},\hat{b}^{\prime}$ are identical to the distribution shown
for $\hat{a},\hat{b}$ (but would be illustrated in blue and purple,
respectively). However, the conditioned probability distribution for the
situation $\hat{a},\hat{b}^{\prime}$ shown in Figure 3(b) is different, with a
light shade of green, representing
$P_{ee}^{\hat{a},\hat{b}^{\prime}}=P_{eo}^{\hat{a},\hat{b}}$, at a location
where a dark shade of pink, representing $P_{ee}^{\hat{a},\hat{b}}$, lies in
Figure 3(a), and vice versa.

The analogue of the additional term in Eq. (9) for the toy model is a sum of
magnitudes of differences between the probability distribution shown in pink
in Figure 3(a) and its blue, purple and green counterparts, analogous to
$\rho(\lambda|\hat{a},\hat{b})$, $\rho(\lambda|\hat{a}^{\prime},\hat{b})$,
$\rho(\lambda|\hat{a}^{\prime},\hat{b}^{\prime})$ and
$\rho(\lambda|\hat{a},\hat{b}^{\prime})$, respectively. For the simplified
case under consideration, the first three distributions are identical and the
fourth is different. This implies, in the notation of a continuum phase space,
that
$\bar{\rho}\epsilon=-\bar{\rho}\sigma=\bar{\rho}\eta=\frac{1}{4}\left(\rho(\lambda|\hat{a},\hat{b})-\rho(\lambda|\hat{a},\hat{b}^{\prime})\right)$
and hence the additional term in the Bell inequality for $S$ in these
circumstances is
$\mu=\frac{3}{2}\int|\rho(\lambda|\hat{a},\hat{b})-\rho(\lambda|\hat{a},\hat{b}^{\prime})|d\lambda$.

For the discrete phase space the integral is replaced by a sum of moduli of
the differences in probability at each position of the grid conditioned on the
red and green measurement outcomes. For the situation we have constructed,
these differences are
$P_{ee}^{\hat{a},\hat{b}}-P_{ee}^{\hat{a},\hat{b}^{\prime}}$ at even-even and
odd-odd points on the grid, and
$P_{eo}^{\hat{a},\hat{b}}-P_{eo}^{\hat{a},\hat{b}^{\prime}}$ at even-odd and
odd-even points, and these quantities are given by
$\pm\left(P_{ee}^{\hat{a},\hat{b}}-P_{eo}^{\hat{a},\hat{b}}\right)$,
respectively. The sum of moduli of probability differences over the grid is
therefore
$N\left|P_{ee}^{\hat{a},\hat{b}}-P_{eo}^{\hat{a},\hat{b}}\right|=4\left|P_{++}^{\hat{a},\hat{b}}-P_{+-}^{\hat{a},\hat{b}}\right|$
and the additional term for the toy model is
$\mu=6\left|P_{++}^{\hat{a},\hat{b}}-P_{+-}^{\hat{a},\hat{b}}\right|$.

Similarly, all four correlation functions can be specified in terms of
$P_{++}^{\hat{a},\hat{b}}$ and $P_{+-}^{\hat{a},\hat{b}}$, specifically
$C(\hat{a},\hat{b})=C(\hat{a}^{\prime},\hat{b})=C(\hat{a}^{\prime},\hat{b}^{\prime})=-C(\hat{a},\hat{b}^{\prime})=2\left(P_{++}^{\hat{a},\hat{b}}-P_{+-}^{\hat{a},\hat{b}}\right)$.
Thus the CHSH parameter is $S=4|C(\hat{a},\hat{b})|$ and the additional term
is $\mu=3|C(\hat{a},\hat{b})|$. Bell’s analysis therefore requires that

$S=4|C(\hat{a},\hat{b})|\leq 2+\mu=2+3|C(\hat{a},\hat{b})|,$ (10)

which is clearly satisfied for the relevant range
$0\leq|C(\hat{a},\hat{b})|\leq 1$. We conclude that measurement dependence has
elevated the upper limit to accommodate an imposed value of the CHSH
parameter.

A toy model can merely illustrate a possibility of behaviour in more realistic
systems. It can focus attention on the elements required to be present in
those systems to produce an effect. Thus, for example, we see the need for a
dynamics of measurement that does not draw configurations towards measurement
outcome targets indiscriminately, but instead selects them from basins of
attraction in the phase space of hidden variables. We also speculate that a
measurement outcome should be associated with system adoption, post-
measurement, of a narrowly defined set of hidden variable configurations. The
measurement dependence effect might therefore be delicate, and could perhaps
emerge only in situations involving few degrees of freedom. The lack of Bell-
violating correlations in more complex experimental circumstances might be
explained in this way.

The freedom of choice of measurement settings often arises in discussions of
measurement dependence. Rather than deny this freedom, a view can be taken
that the settings are indeed under experimental control, or can be made
effectively random by coupling them to complex external systems. We reiterate
that our interest lies in the extent to which the given measurement settings
and outcomes can provide information about the subjectively uncertain
configuration of system hidden variables prior to measurement. The claim of
measurement independence is that _no_ such information is conveyed. But if
quantum measurement involves the evolution of hidden variables with
measurement settings and outcomes acting as boundary conditions on the
dynamics, then conditioning of the probabilities of adopting pre-measurement
configurations will follow. This conditioning, or dynamically imposed memory,
could extend far back in time, challenging the premise normally employed in
the Bell analysis. Perhaps this is the principal implication of the
experimental violation of Bell inequalities.

SMW is supported by a PhD studentship funded by EPSRC under grant codes
EP/R513143/1 and EP/T517793/1.

## References

  * Bell [1964] J. S. Bell, On the Einstein-Podolsky-Rosen paradox, Physics 1, 195 (1964).
  * Aspect  _et al._ [1982] A. Aspect, J. Dalibard, and G. Roger, Experimental Test of Bell’s Inequalities Using Time-Varying Analyzers, Physical Review Letters 49, 1804 (1982).
  * Giustina  _et al._ [2015] M. Giustina, M. A. M. Versteegh, S. Wengerowsky, J. Handsteiner, A. Hochrainer, K. Phelan, F. Steinlechner, J. Kofler, J.-Å. Larsson, C. Abellán, W. Amaya, V. Pruneri, M. W. Mitchell, J. Beyer, T. Gerrits, A. E. Lita, L. K. Shalm, S. W. Nam, T. Scheidl, R. Ursin, B. Wittmann, and A. Zeilinger, Significant-Loophole-Free Test of Bell’s Theorem with Entangled Photons, Physical Review Letters 115, 250401 (2015).
  * Christensen  _et al._ [2013] B. G. Christensen, K. T. McCusker, J. B. Altepeter, B. Calkins, T. Gerrits, A. E. Lita, A. Miller, L. K. Shalm, Y. Zhang, S. W. Nam, N. Brunner, C. C. W. Lim, N. Gisin, and P. G. Kwiat, Detection-Loophole-Free Test of Quantum Nonlocality, and Applications, Physical Review Letters 111, 130406 (2013).
  * Hensen  _et al._ [2015] B. Hensen, H. Bernien, A. E. Dréau, A. Reiserer, N. Kalb, M. S. Blok, J. Ruitenberg, R. F. L. Vermeulen, R. N. Schouten, C. Abellán, W. Amaya, V. Pruneri, M. W. Mitchell, M. Markham, D. J. Twitchen, D. Elkouss, S. Wehner, T. H. Taminiau, and R. Hanson, Loophole-free Bell inequality violation using electron spins separated by 1.3 kilometres, Nature 526, 682 (2015).
  * Shalm  _et al._ [2015] L. K. Shalm, E. Meyer-Scott, B. G. Christensen, P. Bierhorst, M. A. Wayne, M. J. Stevens, T. Gerrits, S. Glancy, D. R. Hamel, M. S. Allman, K. J. Coakley, S. D. Dyer, C. Hodge, A. E. Lita, V. B. Verma, C. Lambrocco, E. Tortorici, A. L. Migdall, Y. Zhang, D. R. Kumor, W. H. Farr, F. Marsili, M. D. Shaw, J. A. Stern, C. Abellán, W. Amaya, V. Pruneri, T. Jennewein, M. W. Mitchell, P. G. Kwiat, J. C. Bienfang, R. P. Mirin, E. Knill, and S. W. Nam, Strong Loophole-Free Test of Local Realism, Physical Review Letters 115, 250402 (2015).
  * Rowe  _et al._ [2001] M. A. Rowe, D. Kielpinski, V. Meyer, C. A. Sackett, W. M. Itano, C. Monroe, and D. J. Wineland, Experimental violation of a Bell’s inequality with efficient detection, Nature 409, 791 (2001).
  * Bell [2004] J. S. Bell,  _Speakable and Unspeakable in Quantum Mechanics: Collected Papers on Quantum Philosophy_, 2nd ed. (Cambridge University Press, Cambridge, 2004).
  * Norsen [2017] T. Norsen,  _Foundations of Quantum Mechanics: An Exploration of the Physical Meaning of Quantum Theory_ (Springer, Cham, Switzerland, 2017).
  * Hossenfelder and Palmer [2020] S. Hossenfelder and T. Palmer, Rethinking superdeterminism, Frontiers in Physics 8, 139 (2020).
  * Clauser  _et al._ [1969] J. F. Clauser, M. A. Horne, A. Shimony, and R. A. Holt, Proposed experiment to test local hidden-variable theories, Physical Review Letters 23, 880 (1969).
  * Wharton and Argaman [2020] K. B. Wharton and N. Argaman, Colloquium: Bell’s theorem and locally mediated reformulations of quantum mechanics, Reviews of Modern Physics 92, 021002 (2020).
  * Pütz and Gisin [2016] G. Pütz and N. Gisin, Measurement dependent locality, New Journal of Physics 18, 055006 (2016).
  * Friedman  _et al._ [2019] A. S. Friedman, A. H. Guth, M. J. W. Hall, D. I. Kaiser, and J. Gallicchio, Relaxed Bell inequalities with arbitrary measurement dependence for each observer, Physical Review A 99, 012121 (2019).
  * Toner and Bacon [2003] B. F. Toner and D. Bacon, Communication Cost of Simulating Bell Correlations, Physical Review Letters 91, 187904 (2003).
  * Hall and Branciard [2020] M. J. W. Hall and C. Branciard, Measurement-dependence cost for Bell nonlocality: Causal versus retrocausal models, Physical Review A 102, 052228 (2020).
  * Brans [1988] C. H. Brans, Bell’s theorem does not eliminate fully causal hidden variables, International Journal of Theoretical Physics 27, 219 (1988).
  * Banik  _et al._ [2012] M. Banik, M. R. Gazi, S. Das, A. Rai, and S. Kunkri, Optimal free will on one side in reproducing the singlet correlation, Journal of Physics A: Mathematical and Theoretical 45, 205301 (2012).
  * Sadhu and Das [2023] A. Sadhu and S. Das, Testing of quantum nonlocal correlations under constrained free will and imperfect detectors, Physical Review A 107, 012212 (2023).
  * Chaves  _et al._ [2021] R. Chaves, G. Moreno, E. Polino, D. Poderini, I. Agresti, A. Suprano, M. R. Barros, G. Carvacho, E. Wolfe, A. Canabarro, R. W. Spekkens, and F. Sciarrino, Causal Networks and Freedom of Choice in Bell’s Theorem, PRX Quantum 2, 040323 (2021).
  * Acín and Masanes [2016] A. Acín and L. Masanes, Certified randomness in quantum physics, Nature 540, 213 (2016).
  * Bierhorst  _et al._ [2018] P. Bierhorst, E. Knill, S. Glancy, Y. Zhang, A. Mink, S. Jordan, A. Rommal, Y.-K. Liu, B. Christensen, S. W. Nam, M. J. Stevens, and L. K. Shalm, Experimentally generated randomness certified by the impossibility of superluminal signals, Nature 556, 223 (2018).
  * Colbeck and Renner [2012] R. Colbeck and R. Renner, Free randomness can be amplified, Nature Physics 8, 450 (2012).
  * Kessler and Arnon-Friedman [2020] M. Kessler and R. Arnon-Friedman, Device-Independent Randomness Amplification and Privatization, IEEE Journal on Selected Areas in Information Theory 1, 568 (2020).
  * Koh  _et al._ [2012] D. E. Koh, M. J. W. Hall, Setiawan, J. E. Pope, C. Marletto, A. Kay, V. Scarani, and A. Ekert, Effects of Reduced Measurement Independence on Bell-Based Randomness Expansion, Physical Review Letters 109, 160404 (2012).
  * Liu  _et al._ [2018a] Y. Liu, Q. Zhao, M.-H. Li, J.-Y. Guan, Y. Zhang, B. Bai, W. Zhang, W.-Z. Liu, C. Wu, X. Yuan, H. Li, W. J. Munro, Z. Wang, L. You, J. Zhang, X. Ma, J. Fan, Q. Zhang, and J.-W. Pan, Device-independent quantum random-number generation, Nature 562, 548 (2018a).
  * Liu  _et al._ [2018b] Y. Liu, X. Yuan, M.-H. Li, W. Zhang, Q. Zhao, J. Zhong, Y. Cao, Y.-H. Li, L.-K. Chen, H. Li, T. Peng, Y.-A. Chen, C.-Z. Peng, S.-C. Shi, Z. Wang, L. You, X. Ma, J. Fan, Q. Zhang, and J.-W. Pan, High-Speed Device-Independent Quantum Random Number Generation without a Detection Loophole, Physical Review Letters 120, 010503 (2018b).
  * Pironio  _et al._ [2010] S. Pironio, A. Acín, S. Massar, A. B. de la Giroday, D. N. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, L. Luo, T. A. Manning, and C. Monroe, Random numbers certified by Bell’s theorem, Nature 464, 1021 (2010).
  * Wooltorton  _et al._ [2022] L. Wooltorton, P. Brown, and R. Colbeck, Tight Analytic Bound on the Trade-Off between Device-Independent Randomness and Nonlocality, Physical Review Letters 129, 150403 (2022).
  * Yuan  _et al._ [2015] X. Yuan, Z. Cao, and X. Ma, Randomness requirement on the Clauser-Horne-Shimony-Holt Bell test in the multiple-run scenario, Physical Review A 91, 032111 (2015).
  * Gallicchio  _et al._ [2014] J. Gallicchio, A. S. Friedman, and D. I. Kaiser, Testing Bell’s Inequality with Cosmic Photons: Closing the Setting-Independence Loophole, Physical Review Letters 112, 110405 (2014).
  * Handsteiner  _et al._ [2017] J. Handsteiner, A. S. Friedman, D. Rauch, J. Gallicchio, B. Liu, H. Hosp, J. Kofler, D. Bricher, M. Fink, C. Leung, A. Mark, H. T. Nguyen, I. Sanders, F. Steinlechner, R. Ursin, S. Wengerowsky, A. H. Guth, D. I. Kaiser, T. Scheidl, and A. Zeilinger, Cosmic Bell Test: Measurement Settings from Milky Way Stars, Physical Review Letters 118, 060401 (2017).
  * Rauch  _et al._ [2018] D. Rauch, J. Handsteiner, A. Hochrainer, J. Gallicchio, A. S. Friedman, C. Leung, B. Liu, L. Bulla, S. Ecker, F. Steinlechner, R. Ursin, B. Hu, D. Leon, C. Benn, A. Ghedina, M. Cecconi, A. H. Guth, D. I. Kaiser, T. Scheidl, and A. Zeilinger, Cosmic Bell Test Using Random Measurement Settings from High-Redshift Quasars, Physical Review Letters 121, 080403 (2018).
  * Wu  _et al._ [2017] C. Wu, B. Bai, Y. Liu, X. Zhang, M. Yang, Y. Cao, J. Wang, S. Zhang, H. Zhou, X. Shi, X. Ma, J.-G. Ren, J. Zhang, C.-Z. Peng, J. Fan, Q. Zhang, and J.-W. Pan, Random Number Generation with Cosmic Photons, Physical Review Letters 118, 140402 (2017).
  * Li  _et al._ [2018] M.-H. Li, C. Wu, Y. Zhang, W.-Z. Liu, B. Bai, Y. Liu, W. Zhang, Q. Zhao, H. Li, Z. Wang, L. You, W. J. Munro, J. Yin, J. Zhang, C.-Z. Peng, X. Ma, Q. Zhang, J. Fan, and J.-W. Pan, Test of Local Realism into the Past without Detection and Locality Loopholes, Physical Review Letters 121, 080404 (2018).
  * Das  _et al._ [2021] S. Das, S. Bäuml, M. Winczewski, and K. Horodecki, Universal Limitations on Quantum Key Distribution over a Network, Physical Review X 11, 041016 (2021).
  * Ekert [1991] A. K. Ekert, Quantum cryptography based on Bell’s theorem, Physical Review Letters 67, 661 (1991).
  * Holz  _et al._ [2020] T. Holz, H. Kampermann, and D. Bruß, Genuine multipartite Bell inequality for device-independent conference key agreement, Physical Review Research 2, 023251 (2020).
  * Horodecki  _et al._ [2022] K. Horodecki, M. Winczewski, and S. Das, Fundamental limitations on the device-independent quantum conference key agreement, Physical Review A 105, 022604 (2022).
  * Kaur  _et al._ [2022] E. Kaur, K. Horodecki, and S. Das, Upper Bounds on Device-Independent Quantum Key Distribution Rates in Static and Dynamic Scenarios, Physical Review Applied 18, 054033 (2022).
  * Li  _et al._ [2022] X. Li, Y. Wang, Y. Han, and S.-N. Zhu, Effects of reduced measurements independence on self-testing, Journal of Physics A: Mathematical and Theoretical 55, 495302 (2022).
  * Moroder  _et al._ [2013] T. Moroder, J.-D. Bancal, Y.-C. Liang, M. Hofmann, and O. Gühne, Device-Independent Entanglement Quantification and Related Applications, Physical Review Letters 111, 030501 (2013).
  * Primaatmaja  _et al._ [2023] I. W. Primaatmaja, K. T. Goh, E. Y.-Z. Tan, J. T.-F. Khoo, S. Ghorai, and C. C.-W. Lim, Security of device-independent quantum key distribution protocols: A review, Quantum 7, 932 (2023).
  * Vazirani and Vidick [2014] U. Vazirani and T. Vidick, Fully Device-Independent Quantum Key Distribution, Physical Review Letters 113, 140501 (2014).
  * Zapatero  _et al._ [2023] V. Zapatero, T. van Leent, R. Arnon-Friedman, W.-Z. Liu, Q. Zhang, H. Weinfurter, and M. Curty, Advances in device-independent quantum key distribution, npj Quantum Information 9, 1 (2023).
  * Hall [2010] M. J. W. Hall, Local deterministic model of singlet state correlations based on relaxing measurement independence, Physical Review Letters 105, 250404 (2010).
  * Pütz  _et al._ [2014] G. Pütz, D. Rosset, T. J. Barnea, Y.-C. Liang, and N. Gisin, Arbitrarily Small Amount of Measurement Independence Is Sufficient to Manifest Quantum Nonlocality, Physical Review Letters 113, 190402 (2014).
  * Šupić  _et al._ [2022] I. Šupić, J.-D. Bancal, and N. Brunner, Quantum nonlocality in presence of strong measurement dependence (2022), arxiv:2209.02337 [quant-ph] .
  * Kim  _et al._ [2019] M. Kim, J. Lee, H.-J. Kim, and S. W. Kim, Tightest conditions for violating the Bell inequality when measurement independence is relaxed, Physical Review A 100, 022128 (2019).