The extension of linear inequality method for generalised rational Chebyshev
approximation to approximation by general quasilinear functions.

Vinesha Peiris and Nadezda Sukhorukova

###### Abstract

In this paper we demonstrate that a well known linear inequality method
developed for rational Chebyshev approximation is equivalent to the
application of the bisection method used in quasiconvex optimisation. Although
this correspondence is not surprising, it naturally connects rational and
generalised rational Chebyshev approximation problems with modern developments
in the area of quasiconvex functions and therefore offers more theoretical and
computational tools for solving this problem. The second important
contribution of this paper is the extension of the linear inequality method to
a broader class of Chebyshev approximation problems, where the corresponding
objective functions remain quasiconvex. In this broader class of functions,
the inequalities are no longer required to be linear: it is enough for each
inequality to define a convex set and the computational challenge is in
solving the corresponding convex feasibility problems. Therefore, we propose a
more systematic and general approach for treating Chebyshev approximation
problems. In particular, we are looking at the problems where the
approximations are quasilinear functions with respect to their parameters,
that are also the decision variables in the corresponding optimisation
problems.

Keywords: generalised rational approximation, Chebyshev approximation,
quasiconvex functions, linear inequality method, bisection method.

MSC2010: 90C25, 90C26,90C90, 90C47, 65D15, 65K10.

##  1 Introduction

In Chebyshev (uniform) approximation problems, the goal is to minimise the
maximal deviation of the approximated function from the original function. In
other words, the best uniform aproximation ensures that the deviation is
minimal. The uniform polynomial approximation still draws an immense interest,
since polynomials are simple and easy to handle. However, when nonsmooth or
non-Lipschitz functions are subjected to approximate, polynomial approximation
is not very efficient.

Sometimes, this problem can be resolved by using piecewise polynomials or
polynomial splines [27, 28, 38, 39]. Polynomial splines are more flexible
approximation technique than polynomials. Overall, polynomial spline
approximation is efficient when the location of the knots (points of switching
from one polynomial to another) is known. In the case of polynomials and
piecewise polynomials with fixed knots, the optimisation problem is convex and
therefore, existing optimisation techniques can be used to tackle this problem
from the point of view of optimisation. When the knots are free (the location
of the knots are unknown), the problem becomes nonconvex and the complexity of
the corresponding optimisation problem increases [11, 22, 27, 28, 23, 41, 40].
In 1996, Nürnberger, Daubechies, Borwein, and Totik [6] identified this
problem as a very hard and important open problem in approximation. The
existing optimisation tools are not adapted to this problem due to its
nonconvex and nonsmooth nature. One way to overcome this problem is to use
rational functions (ratios of two polynomials).

Rational approximation attracted a significant research interest in 50s-60s of
the twentieth century [1, 5, 21, 32, 35] as a promising alternative to the
free knot spline approximation. Moreover, there are theoretical studies [19,
31] demonstrated that approximation by rational functions and free-knot spline
approximations are closely related to each other.

There are a number of efficient numerical methods for constructing rational
approximations: Remez method, originally developed for polynomial
approximation, was extended to rational approximation [15, 33, 34], the
differential correction algorithm [2], Loeb’s algorithm [18], the linear
inequality method [17] and Osborne-Watson algorithm [29]. The most recent
developments in this area [24] are dedicated to “nearly optimal” solutions,
whose construction is based on Chebyshev polynomials.

The linear inequality method is interesting from several points of view. It is
simple, easy to implement and converges to an optimal solution. Another
important characteristic of this methods is its applicability to generalised
rational approximation problems [9], where approximations are constructed as
the ratios of linear forms and not limited to ratios of polynomials. It was
also demonstrated in [9] that the corresponding optimisation problems in the
case of generalised rational approximation are quasiconvex and strictly
quasiconvex [3] in the case of classical rational approximation. These results
were used in the development of new theoretical characteristics of the
problems rather than constructing computational methods. The first main
purpose of this paper is to make a step towards covering this gap, in
particular, we will demonstrate that the linear inequality method for
generalised rational approximation is identical to the application of the
bisection method developed for quasiconvex optimisation problems. The second
main contribution of this paper is the extension of the linear inequality
method to a broader class of Chebyshev approximation problems. This class
includes all the approximation types, where the approximation is quasilinear
with respect to its parameters. The corresponding inequalities may be
nonlinear and therefore we change the name of the method to just “inequality
method”, but the set defined by each constraint is convex (that is, solving
convex feasibility problems).

The rest of the paper is organised as follows. Section 2 offers a detailed
introduction on rational approximation and the linear inequality method. In
section 3, we discuss the quasiconvexity of the problem and possible extension
to a broader class of functions. Section 4 provides of bisection method and
its applicability to Chebyshev approximation problems. Section 5 discusses
numerical experiments of the proposed method with the similarities and
differences of the two methods while section 6 provides conclusion and future
research directions.

##  2 Rational and generalised rational approximation

###  2.1 Problem formulation

Let $f(t)$ be a given real valued function defined on the closed interval
$[c,d]$. Let $R_{n,m}$ be a rational function (rational function of type
$(n,m)$) of degree $n$ in the numerator and degree $m$ in the denominator
where $n$ and $m$ being nonnegative integers.

$R_{n,m}(t)=P(t)/Q(t)=\frac{\sum_{i=0}^{n}p_{i}t^{i}}{\sum_{j=0}^{m}q_{j}t^{j}}.$

The best uniform rational approximation problem over the closed interval
$[c,d]$ is defined as follows:

$\min_{r\in R_{n,m}}\max_{t\in[c,d]}\left|{f(t)-r(t)}\right|.$ (1)

subject to,

$Q(t)>0,t\in[c,d].$

The objective is to determine the coefficients, $p_{i}$, $i=0,\cdots,n$ and
$q_{j}$, $j=0,\cdots,m$ which minimise the maximal deviation. This problem (1)
is also known as the minimax rational approximation problem. The rational
function, $r(t)$ is defined to be a ratio of two polynomials. Most prominent
methods (Remez method, differential correction method, linear inequality
method, etc.), developed for uniform rational approximation were originally
defined for the ratio of polynomials. Some of them (for example, linear
inequality and differential correction) were extended to generalised rational
Chebyshev approximation (ratios of linear forms, introduced in [9]).

In this paper we use the same definition of generalised rational Chebyshev
approximation. Specifically, we construct the approximations in the form of
the ratios of linear combinations of functions in both numerator and the
denominator. The generalised rational approximation problem in Chebyshev norm
can be formulated as follows [9]:

$\min_{\begin{subarray}{c}{\bf A},{\bf
B}\end{subarray}}\max_{t\in[c,d]}\left|f(t)-\frac{{\bf A}^{T}{\bf G}(t)}{{\bf
B}^{T}{\bf H}(t)}\right|.$ (2)

subject to,

${{\bf B}^{T}{\bf H}(t)}>0,t\in[c,d].$ (3)

where,

  * •

$f(t)\in{C_{[c,d]}^{0}}$ is the function to approximate,

  * •

${\bf A}=(a_{0},a_{1},\cdots,a_{n})^{T}\in\mathbb{R}^{n+1}$ and ${\bf
B}=(b_{0},b_{1},\cdots,b_{m})^{T}\in\mathbb{R}^{m+1}$ are the decision
variables,

  * •

${\bf G}(t)=(g_{0}(t),g_{1}(t),\cdots,g_{n}(t))^{T}$ and ${\bf
H}(t)=(h_{0}(t),h_{1}(t),\cdots,h_{m}(t))^{T}$, $g_{j},j=1,\cdots,n$ and
$h_{i},i=1,\cdots,m$ are known functions which are also known as the basis
functions.

The constraint set (strict linear inequality) is an open convex set. The
numerator and the denominator are linear combinations of basis functions. When
all the basis functions are monomials, the approximations are rational
functions from $R_{n,m}$, and the problem is reduced to the best uniform
rational approximation (1). Our approximations are not restricted to rational
functions with polynomials. All of the results are valid for any type of basis
functions when (3) is satisfied.

###  2.2 Linear inequality method

The linear inequality method [17] for solving rational and generalised
rational problems includes the following steps.

  1. Step 0

Identify upper and lower bounds ($M_{u}$ and $M_{l}$) for the maximal
deviation. In particular, zero is always a lower bound, while

$\max_{t\in[a,b]}f(t)-\min_{t\in[a,b]}f(t)$

can be used as an upper bound.

  2. Step 1

Set $z=\frac{1}{2}(M_{u}+M_{l})$. Check if the following system of
inequalities has a feasible solution.

$f(t)-\frac{{\bf A}^{T}{\bf G}(t)}{{\bf B}^{T}{\bf H}(t)}\leq z,$ (4)
$\frac{{\bf A}^{T}{\bf G}(t)}{{\bf B}^{T}{\bf H}(t)}-f(t)\leq z,$ (5) ${{\bf
B}^{T}{\bf H}(t)}>0,t\in[c,d].$ (6)

  3. Step 2

If (4)- (6) has a feasible solution, assign $M_{u}=z$, otherwise $M_{l}=z$. If
$M_{u}-M_{l}\geq\varepsilon$, go to Step 1.

Therefore, the algorithm stops when $M_{u}-M_{l}<\varepsilon$ (tolerance).

It was demonstrated in [9] that in the case when $t$ takes discrete values
(discretised system), Step 1 can be verified by solving a linear programming
problem. For computations purposes, constraint (6) is replaced by

${{\bf B}^{T}{\bf H}(t)}\geq\delta,t\in[c,d],.$ (7)

where $\delta$ is a small positive number.

##  3 Quasiconvexity of the problem

###  3.1 Quasiconvex functions

The notion of quasiconvexity was first introduced by mathematicians working
with the area of financial mathematics. There are two commonly used equivalent
definitions of quasiconvex functions.

###### Definition 1

A function $f:D\rightarrow\mathbb{R}$ defined on a convex subset $D$ of a real
vector space is called quasiconvex if and only if for any pair $x$ and $y$
from $D$ and $\lambda\in[0,1]$ one has

$f(\lambda x+(1-\lambda)y)\leq\max\\{f(x),f(y)\\}.$

###### Definition 2

Function $f(t)$ is quasiconvex if and only if its sublevel set

$S_{\alpha}=\\{x|f(x)\leq\alpha\\}$

is convex for any $\alpha\in\mathbb{R}$. The set $S_{\alpha}$ is also called
$\alpha$-sublevel set.

Definition 1 is due to to Bruno de Finetti’s work [13]. In this paper de
Finetti studied the behaviour of functions, whose sublevel set is convex. The
term quasiconvexity was introduced much later, as a result to generalised the
notion of convexity to a broader class of functions.

###### Definition 3

Function $f$ is quasiconcave if and only if $-f$ is quasiconvex.

This means that every superlevel set $\bar{S}_{\alpha}=\\{x|f(x)\geq\alpha\\}$
is convex.

###### Definition 4

Functions that are quasiconvex and quasiconcave at the same time are called
quasiaffine (sometimes quasilinear).

There are many studies devoted to quasiconvex optimisation [10, 12, 14, 36,
37] just to name a few.

It was demonstrated in [9] that the sublevel sets of the objective functions
(2) are convex ([9], Lemma 2). This result was considered by the authors as an
auxiliary result, but this also proves that the objective functions (2) is
quasiconvex. The same result can be obtained by applying the following two
properties of quasiconvex functions.

  1. 1.

The supremum of a family of quasiconvex functions is quasiconvex.

  2. 2.

The ratio of two affine functions is quasiaffine.

###### Remark 1

In the case of classical rational approximation (that is, all the basis
functions are monomials), it was proved that the objective function is
strictly quasiconvex [3].

Therefore, the problem of rational and generalised rational approximation can
be treated using a number of computational methods developed for quasiconvex
optimisation [20, 25]. One such method (called bisection method for
quasiconvex functions) will be described in section 4. In the same section we
demonstrate that the bisection method for quasiconvex functions is equivalent
to the linear inequality method for classical rational approximation and can
be extended to generalised rational approximation (the constraints remain
linear) or even to a broader class approximations, where the corresponding
optimisation problems remain quasiconvex. This class of approximations is
described in the next section.

###  3.2 Extension to broader classes of functions

The goal of this section is to identify the class of Chebyshev approximations
whose optimisation problems are quasiconvex and therefore can be solved by
applying quasiconvex optimisation techniques. The following lemma holds.

###### Lemma 1

If the approximation is quasilinear with respect to its parameters, that are
also the decision variable for the corresponding optimisation problems, then
the Chebyshev approximation problem is quasiconvex.

Proof: We need to prove that if the approximations are quasilinear with
respect to their parameters then the corresponding optimisation problem is
quasiconvex. The optimisation problem is as follows:

$\min_{A}\max_{t\in[c,d]}|F(A,t)-f(t)|,$ (8)

where $f(t)$ is the function to approximate, $F(A,t)$ is the approximation and
$A$ are the parameters of approximation that can be optimised. We need to
prove that if $F(A,t)$ is quasilinear with respect to $A$ then

$\Phi(A)=\max_{t\in[c,d]}|F(A,t)-f(t)|$

is quasiconvex. Indeed,

$\Phi(A)=\max_{t\in[c,d]}|F(A,t)-f(t)|=\max_{t\in[c,d]}\\{F(A,t)-f(t),f(t)-F(A,t)\\}.$

Since $F(A,t)$ is quasilinear for $A$, both functions $F(A,t)-f(t)$ and
$f(t)-F(A,t)$ are quasiconvex. Then the maximum of quasiconvex functions is
also quasiconvex.

$\square$

##  4 Bisection method for quasiconvex functions

In this section we describe a simple approach for solving quasiconvex
problems. This method is also known as a bisection method for quasiconvex
functions (see [7], section 4.2.5 for more information). The approach is based
on the representation of the sublevel set of quasiconvex functions. These sets
are convex (due to the definition of quasiconvex functions).

Let $\varphi_{z}(x):\mathbb{R}^{k}\rightarrow\mathbb{R}$ and $z\in\mathbb{R}$
be a family of convex functions, such that $\varphi_{z}(x)\leq 0$ if and only
if $x$ belongs to $z$-sublevel set of the quasiconvex function $\Phi$, that is
equivalent to $\Phi(x)\leq z$.

Consider the following quasiconvex optimiation problem:

$\min_{x}\Phi(x),$ (9)

subject to

$\Phi_{i}(x)\leq 0,i=1,\dots,l,\\\ $ (10) $Ax=b,$ (11)

where $\Phi(x)$ is a quasiconvex function, $\Phi_{i},$ $i=1,\dots,l$ are
convex functions and (11) is a set of linear equations. Then the feasibility
problem is

${\rm Find}~{}x,~{}{\rm subject~{}to}$ $\varphi_{z}(x)\leq 0,\\\ $ (12)
$\Phi_{i}(x)\leq 0,i=1,\dots,l,\\\ $ (13) $Ax=b.$ (14)

Since all the sublevel sets are convex, the goal of the feasibility problem
(12)-(14) is to find a point that belongs to a convex set (intersection of
convex sets). This class of problems is also called convex feasibility
problems. These problems may be very challenging, but there are a number of
efficient techniques for solving convex feasibility problems ([4, 8, 42, 26,
43, 44, 45] just to name a few). There are still several open problems.
However, in this paper we do not discuss these problems and concentrate of the
approximation side.

In the case of classical rational and generalised rational approximation, the
corresponding convex feasibility problems (discrete case) can be reduced to
solving linear programming problems [9, 17, 18, 29, 30], while for the
continuous case the corresponding convex feasibility problems are linear semi-
infinite. More details on linear semi-infinite problems can be found in [16].

In the case of discrete approximation by rational and generalised rational
functions, for a given level $\alpha=z$, the corresponding linear programming
problem is as follows:

$\min u$ (15)

subject to

$\displaystyle(f(t_{i})-z){{\bf{B}}^{T}{\bf{H}}(t_{i})}-{{\bf{A}}^{T}{\bf{G}}(t_{i})}\leq
u,\quad i=1,\dots,N$ (16)
$\displaystyle{{\bf{A}}^{T}{\bf{G}}(t_{i})}-(f(t_{i})+z){{\bf{B}}^{T}{\bf{H}}(t_{i})}\leq
u,\quad i=1,\dots,N$ (17)
$\displaystyle{\bf{B}}^{T}{\bf{H}}(t_{i})\geq\delta,\quad i=1,\dots,N,$ (18)

where $\delta$ is a small positive constant, sublevel set parameter $z$ is
also a constant and therefore (15)-(18) is a linear programming problem.

In the case of discrete approximation by a general quasiconvex function with
respect to the parameters, for a given level $\alpha=z$, the corresponding
linear programming problem is as follows:

${\rm Find}~{}A$ (19)

subject to

$\displaystyle f(t_{i})-F(A,t_{i})\leq z,\quad i=1,\dots,N$ (20)
$\displaystyle F(A,t_{i})-f(t_{i})\leq z,\quad i=1,\dots,N.$ (21)

Since $F(A,t)$ is quasilinear, the feasible set described by inequalities
(20)-(21) is convex.

We use a bisection method for quasiconvex optimisation. This method is simple
and reliable and can be applied to any quasiconvex function (see [7], section
4.2.5 for more information). Our bisection method relies on solving the
corresponding convex feasibility problem, which can be done by solving
(15)-(18) in the case of rational and generalised rational approximation. The
bisection method is given in Algorithm 1.

Algorithm 1 Bisection algorithm for quasiconvex optimisation

0: Maximal deviation $z$ (within $\varepsilon$ precision). Start with given
precision $\varepsilon>0$.

set $l\leftarrow 0$

set $u$

$z\leftarrow(u+l)/2$

while $u-l\leq\varepsilon$ do

Check if problem (19)-(21) has a feasible solution with $z$.

if feasible solution exists then

$u\leftarrow z$

else

$l\leftarrow z$

end if

update $z\leftarrow(u+l)/2$

end while

Therefore, the linear inequality method developed for rational and generalised
rational approximation is equivalent to applying the bisection method for
quasiconvex optimisation. In the case, the convex feasibility problem can be
formulated as a linear programming problem. In more general cases, where the
approximations are arbitrary quasilinear functions with respect to their
parameters (Lemma 1) more general convex feasibility problems have to be
solved. In this case, the set of inequalities are not restricted to linear:
the only requirement for the left hand side is to be quasilinear.

##  5 Numerical examples

###  5.1 Free knot linear approximations

We start with a numerical example from the area of free knot spline
approximation. A continuous function $f(t)$ is to be approximated by a
piecewise linear function with one internal knot (point of switching from one
linear piece to another). In general, in the case free knot polynomial spline
approximation the corresponding optimisation problems are very difficult. When
the knots are fixed and only the coefficients of polynomial pieces are subject
to approximation, the problems are convex. Therefore, there are a number of
methods that include block-coordinate approximation [28], where the polynomial
coefficients are subject to optimisation (knots are fixed) and then the
obtained coefficients are fixed and the knots are subject to optimisation.

Suppose that a continuous function $f(t)$ is approximated on an interval
$[c,d]$ by a piecewise linear function

$S(a_{0},a_{1},a_{2},\theta,t)=a_{0}+a_{1}t+a_{2}\max\\{0,t-\theta\\}.$

Assume that $a_{0},a_{1}$ and $a_{2}$ (coefficients) are fixed and the knot
$\theta$ is subject to optimisation. Then the corresponding optimisation
problem is as follows:

$\min_{\theta\in[c,d]}\max_{t\in[c,d]}|f(t)-(a_{0}+a_{1}t+a_{2}\max\\{0,t-\theta\\})|.$
(23)

Assume that $a_{2}\neq 0$, otherwise it is equivalent to $\theta=d$ (that is,
only one linear piece). Therefore, there is only one variable $\theta$.

The function $\max\\{0,t-\theta\\}$ is quasilinear with respect to $\theta$
and therefore
$\Phi(\theta)=\max_{t\in[c,d]}|f(t)-(a_{0}+a_{1}t+a_{2}\max\\{0,t-\theta\\})|$
is quasiconvex in $[c,d]$. Since there is only one variable, there are several
methods to minimise $\Phi(\theta)$. We use this example for illustrative
purposes to interpret bisection.

Fix $\alpha=\Delta\geq 0$ and then one needs to check if there exists a value
$\theta=\theta_{0}$, such that

$f(t)-a_{0}-a_{1}t-\Delta\leq a_{2}\max_{t\in[c,d]}\\{0,t-\theta\\}\leq
f(t)-a_{0}-a_{1}t+\Delta,$ (24)

then

$g(t)-z\leq\max_{t\in[c,d]}\\{0,t-\theta\\}\leq g(t)+z,$ (25)

where $g(t)=\frac{f(t)-a_{0}-a_{1}t}{a_{2}}$, $z=\Delta/|a_{2}|$ and therefore
$z\geq 0$. Hence, the feasibility problem is equivalent to fitting
$\max\\{0,t-\theta\\}$ in the area between $g(t)+z$ and $g(t)-z$.

Figure 1 depicts the situation there is more than one value for $\theta$, such
that there is a function of the form $\max\\{0,t-\theta\\}$ that fits in the
area between $g(t)+z$ and $g(t)-z$. Indeed, if $A=(t_{1},0)$ and
$B=(t_{2},0)$, then $t_{1}\leq\theta\leq t_{2}$. Figure 2 depicts the
situation where the corresponding feasibility problem has no solution. In this
case, there is no function of the form $\max\\{0,t-\theta\\}$ that fits in the
area between $g(t)+z$ and $g(t)-z$. This means that there is no $\theta$ that
satisfies the corresponding feasibility problem.

Figure 1: More than one possibility for $\theta$, any value between $A$ and
$B$ gives a feasible solution. Figure 2: There is no $\theta$, not feasible
solution.

###  5.2 Ratio of piecewise polynomial approximations

In this section we present two sets of numerical experiments where the
function $f(t)$ is approximated by a ratio of two piecewise polynomials. In
both cases, the ratio consists of linear combinations of basis functions in
the numerator and in the denominator. The piecewise polynomials are
constructed using the truncated power function:

$S({\bf
A},t,\theta)=a_{0}+\sum_{j=1}^{m}{a_{j}t^{j}}+\sum_{k=1}^{m}{a_{k+m}(\max\\{0,t-\theta\\})^{k}}$

where $m$ is the degree of the piecewise polynomial, $a_{i}\in{\bf
A},i=0,\dots,2m+1$ are the parameters and assume that the knots are fixed.

We consider approximating a nonlinear, non-Lipschitz function

$f(t)=\sqrt{|t-0.25|},\quad t\in[-1,1].$

The approximations are calculated via Algorithm 1 and the precision
($\varepsilon$) is set to be $10^{-5}$. The code for these numerical
experiments are implemented using Matlab.

####  5.2.1 First set of experiments

Suppose that the function $f(t)$ is approximated by a ratio of two piecewise
polynomials with fixed knots where the degrees of the numerator and the
denominator are $2,2$ respectively.

The corresponding optimisation problem is as follows:

$\min_{A,B}\max_{t\in[-1,1]}\left|f(t)-\frac{a_{0}+a_{1}t+a_{2}t^{2}+a_{3}\max\\{0,t-\theta_{1}\\}+a_{4}(\max\\{0,t-\theta_{1}\\})^{2}}{1+b_{1}t+b_{2}t^{2}+b_{3}\max\\{0,t-\theta_{2}\\}+b_{4}(\max\\{0,t-\theta_{2}\\})^{2}}\right|$

where, $a_{i}\in{\bf A},i=0,\dots,4$ and $b_{j}\in{\bf B},j=1,\dots,4.$

The set of parameters (${\bf A,B}$), are the coefficients of piecewise
polynomials and there are $9$ parameters in total (computed as $5+4$) to be
determined. Both numerator and denominator consist of linear functions with
respect to the parameters. Therefore, this ratio forms a quasilinear function
which leads to the bisections method defined for quasiconvex problems. Note
that the constant term of the denominator is fixed at 1 to avoid the ambiguity
of two solutions representing the same fraction.

One can fix the knots at anywhere between $[-1,1]$. Let us assume that both
knots in the numerator and the denominator are located at the same point. That
is, $\theta_{1}=\theta_{2}(=\theta)$ and the approximation comprise of two
intervals $[-1,\theta],[\theta,1]$. We consider four different cases where
$\theta$ is located at 0.25, 0.5, 0 and -0.5.

Figure 3 shows that when $\theta=0.25$, i.e. the knot is located at the same
point where the original function tends to have an abrupt change, the
alternation sequence contains 9 (5+4) maximum deviation points, and hence the
solution is optimal. The maximal deviation is around 0.01. In [30] the same
function $f(t)$ was approximated by a rational function where the basis
functions are just monomials and the maximum deviation was around 0.05.
Therefore, if the exact location of the knot is correctly identified, it is
more likely to get an enhanced result by using appropriate basis functions
which forms a quasilinear function.

Figure 4 illustrates 8 alternating error peaks that come with the same
magnitude when the $\theta$ is located at 0.5. However, by decreasing the
precision parameter of the algorithm 1, we may possibly end up with 9
alternating error peaks. The maximum deviation is around 0.1 which is 10 times
higher than the previous error.

Figure 5 and Figure 6 depict the corresponding approximations and the error
curves when $\theta=-0.5$ and $\theta=0$ respectively. There are less than 9
maximal deviation and the magnitude of the error is around 0.1 for both cases.

(a) The function and its approximation

(b) Error curves

Figure 3: The knot ($\theta_{1}=\theta_{2}$) is located at 0.25

(a) The function and its approximation

(b) Error curves

Figure 4: The knot ($\theta_{1}=\theta_{2}$) is located at 0.5

(a) The function and its approximation

(b) Error curves

Figure 5: The knot ($\theta_{1}=\theta_{2}$) is located at -0.5

(a) The function and its approximation

(b) Error curves

Figure 6: The knot ($\theta_{1}=\theta_{2}$) is located at 0

Let us now assume that the location of the knot in the numerator is different
to the location of the knot in the denominator. That is, the approximation
consist of 3 intervals $[-1,\theta_{1}],[\theta_{1},\theta_{2}]$ and
$[\theta_{2},1]$ or $\theta_{1}$ and $\theta_{2}$ are in different order. We
consider different combinations for the locations of the knots as stated in
table 1.

Table 1: Combinations for the locations of the knots $\theta_{1}$ | $\theta_{2}$ | Number of deviation points | Figure
---|---|---|---
0.25 | 0.5 | 7 | 7(b)
0.25 | 0 | 7 | 8(b)
0.5 | 0.25 | 5 | 9(b)
0.5 | 0 | 6 | 10(b)
0 | 0.25 | 7 | 11(b)
0 | 0.5 | 7 | 12(b)
$-\frac{1}{3}$ | $\frac{1}{3}$ | 7 | 13(b)
$\frac{1}{3}$ | $-\frac{1}{3}$ | 9 | 14(b)

In both Figure 7 and Figure 8, the approximations appear to be very similar
except for the location of the knot in the denominator. The knot in the
numerator is identified and located correctly. Both error curves have 7
alternating maximum deviation points. In Figure 8(b), there is a shorter peak
between -0.5 and 0 which is already in the positive side. This implies that we
attain exactly 9 error peaks that come with alternating signs but the
magnitude of these error peaks are not uniform. This establishes a good
starting point for the Remez method.

When the correctly identified knot is located in the denominator, Figure 9 and
Figure 11 show that the solutions are not optimal as they do not contain the
expected number of alternating deviation points in the error curve. Figure 10
and Figure 12 depict the instance where none of knots are positioned at a
correctly identified location. However, Figure 12(b) illustrates that it is
more closer to getting an optimal solution than in the case of Figure 10(b)
even though the maximum deviation for both cases is identical.

Figure 13 and Figure 14 correspond to equidistant knots which divide the
domain $[-1,1]$ into 3 equal sized intervals. If the exact locations of the
knots are unknown, then it is reasonable to take equidistant knots and ensure
that they do not coincide. We consider two scenariors; in the first case, knot
in the numerator is located at $-1/3$ and the knot in the denominator is
located at $1/3$; in the second case we simply interchange the knot values.
Figure 13(b) has 7 alternating error peaks whereas Figure 13(b) has 9
alternating error peaks although the maximum deviations are exactly the same
for both cases.

(a) The function and its approximation

(b) Error curves

Figure 7: The knot in the numerator $\theta_{1}=0.25$ and the knot in the
denominator $\theta_{2}=0.5$

(a) The function and its approximation

(b) Error curves

Figure 8: The knot in the numerator $\theta_{1}=0.25$ and the knot in the
denominator $\theta_{2}=0$

(a) The function and its approximation

(b) Error curves

Figure 9: The knot in the numerator $\theta_{1}=0.5$ and the knot in the
denominator $\theta_{2}=0.25$

(a) The function and its approximation

(b) Error curves

Figure 10: The knot in the numerator $\theta_{1}=0.5$ and the knot in the
denominator $\theta_{2}=0$

(a) The function and its approximation

(b) Error curves

Figure 11: The knot in the numerator $\theta_{1}=0$ and the knot in the
denominator $\theta_{2}=0.25$

(a) The function and its approximation

(b) Error curves

Figure 12: The knot in the numerator $\theta_{1}=0$ and the knot in the
denominator $\theta_{2}=0.5$

(a) The function and its approximation

(b) Error curves

Figure 13: The knot in the numerator $\theta_{1}=-\frac{1}{3}$ and the knot in
the denominator $\theta_{2}=\frac{1}{3}$

(a) The function and its approximation

(b) Error curves

Figure 14: The knot in the numerator $\theta_{1}=\frac{1}{3}$ and the knot in
the denominator $\theta_{2}=-\frac{1}{3}$

####  5.2.2 Second set of experiments

In this set of experiments, the degree of both numerator and denominator of
the above approximation is reduced by 1 and the number of knots in each
peicewise polynomial is increased by 2 in order to keep the number of
parameters unchanged. In particular, the function $f(t)$ is approximated by a
ratio of peicewise polynomials of degree 1 with fixed knots. This ratio falls
under the class of quasilinear functions leading to Algorithm 1.

The corresponding optimisation problem is as follows:

$\min_{A,B}\max_{t\in[c,d]}\left|f(t)-S({\bf A},{\bf B},t)\right|,$

where ${S({\bf A},{\bf
B},t)=\frac{a_{0}+a_{1}t+a_{2}\max\\{0,t-\theta_{1}\\}+a_{3}\max\\{0,t-\theta_{2}\\}+a_{4}\max\\{0,t-\theta_{3}\\}}{1+b_{1}t+b_{2}\max\\{0,t-\theta_{4}\\}+b_{3}\max\\{0,t-\theta_{5}\\}+b_{4}\max\\{0,t-\theta_{6}\\}}},$
$a_{i}\in A,i=0,\dots,4$ and $b_{j}\in B,j=1,\dots,4.$

The set of parameters (${\bf A,B}$) consist of $9~{}(5+4)$ parameters in total
to be determined. We consider equidistant knots for the experiments in this
section and we start by dividing the domain into 4 equal sized intervals. This
helps to reduce the overlapping between the knots in the numerator and the
denominator and it provides more flexibility for the knots. Hence the number
of parameters to be determined will be the same as before.

Assume $\theta_{1}$, $\theta_{2}$ and $\theta_{3}$ (knots in the numerator)
are distinct and they are equidistant. The knots in the denominator,
$\theta_{4}$, $\theta_{5}$ and $\theta_{6}$ coincide with the knots in the
numerator. Therefore, we take,

$\theta_{1}=-0.5=\theta_{4},$ $\theta_{2}=0=\theta_{5},$
$\theta_{3}=0.5=\theta_{6}$

.

Figure 15(a) clearly indicates that the approximation is made up of 4 small
rigid pieces of functions and Figure 15(b) only contain 4 alternating error
peaks with maximum deviation being around 0.25. One can expect to get an
accurate approximation when the number of knots is increased. But if none of
the knots are positioned at a correctly identified location or at least
somewhere close to an original (known) knot point, it is very unlikely to get
an optimal solution.

Another interesting aspect is shown in Figure 16 where all 6 knots in the
approximation are distributed equidistantly by dividing the domain into 7
equal sized intervals.

$\begin{split}\theta_{1}=-\frac{5}{7},\\\
\theta_{4}=\frac{1}{7},\end{split}\quad\begin{split}\theta_{2}=-\frac{3}{7},\\\
\theta_{5}=\frac{3}{7},\end{split}\quad\begin{split}\theta_{3}=-\frac{1}{7},\\\
\theta_{6}=\frac{5}{7}.\end{split}$

There is no overlapping between the knots in the numerator and the
denominator. However, the error curve contains only 3 alternating peaks and
the maximum deviation is much higher than any other cases that we considered
earlier.

(a) The function and its approximation

(b) Error curves

Figure 15: $\theta_{1}=-0.5=\theta_{4}$, $\theta_{2}=0=\theta_{5}$,
$\theta_{3}=0.5=\theta_{6}.$

(a) The function and its approximation

(b) Error curves

Figure 16:
$\theta_{1}=-5/7,\theta_{2}=-3/7,\theta_{3}=-1/7,\theta_{4}=1/7,\theta_{5}=3/7,\theta_{6}=5/7.$

##  6 Conclusions and future work

In this paper we demonstrated that the linear inequality method developed
decades ago for rational and generalised rational Chebyshev approximation is
the direct application of the bisection method for quasiconvex optimisation.
This correspondence is not surprising, since it is a well-known fact that the
optimisation problems in generalised rational chebyshev approximation is
quasiconvex. However, this observation leads to an extension of this method to
a broader class of functions.

In the future, we are planning to continue our work in the direction of
identifying the correspondence between generalised rational Chebyshev
approximation methods and general optimisation methods for quasiconvex and
psedoconvex problems. Another interesting research direction is to investigate
the extension of generalised Chebyshev approximation to multivariate settings,
where the application of general quasiconvex optimisation methods look very
promising.

## Acknowledgement

This research was supported by the Australian Research Council (ARC), Solving
hard Chebyshev approximation problems through nonsmooth analysis (Discovery
Project DP180100602).

## References

  * [1] Achieser, _Theory of approximation_ , Frederick Ungar, New York, 1965.
  * [2] I. Barrodale, M. Powell, and F. Roberts, _The differential correction algorithm for rational $l_{\infty}$-approximation_, SIAM Journal on Numerical Analysis 9 (1972), no. 3, 493–504.
  * [3] Ian Barrodale, _Best rational approximation and strict quasi-convexity_ , SIAM Journal on Numerical Analysis 10 (1973), no. 1, 8–12.
  * [4] Heinz H Bauschke and Adrian S Lewis, _Dykstras algorithm with bregman projections: A convergence proof_ , Optimization 48 (2000), no. 4, 409–427.
  * [5] Boehm, _Functions whose best rational chebyshev approximation are polynomials_ , Numer. Math. (1964), 235––242.
  * [6] P. Borwein, I. Daubechies, V. Totik, and G. Nürnberger, _Bivariate segment approximation and free knot splines: Research problems 96-4_ , Constructive Approximation 12 (1996), no. 4, 555–558.
  * [7] S. Boyd and L. Vandenberghe, _Convex optimization_ , Cambridge University Press, New York, NY, USA, 2010.
  * [8] Andrzej Cegielski and Nimit Nimana, _Extrapolated cyclic subgradient projection methods for the convex feasibility problems and their numerical behaviour_ , Optimization 68 (2019), no. 1, 145–161.
  * [9] E.W. Cheney and H.L. Loeb, _Generalized rational approximation_ , Journal of the Society for Industrial and Applied Mathematics, Series B: Numerical Analysis 1 (1964), no. 1, 11–25.
  * [10] J. P. Crouzeix, _Conditions for convexity of quasiconvex functions_ , Mathematics of Operations Research 5 (1980), no. 1, 120–125.
  * [11] J.P. Crouzeix, N. Sukhorukova, and J. Ugon, _Finite alternation theorems and a constructive approach to piecewise polynomial approximation in chebyshev norm_ , Set-Valued and Variational Analysis (2020), 1–25.
  * [12] Aris Daniilidis, Nicolas Hadjisavvas, and Juan-Enrique Martinez-Legaz, _An appropriate subdifferential for quasiconvex functions_ , SIAM Journal on Optimization 12 (2002), 407–420.
  * [13] Bruno de Finetti, _Sulle stratificazioni convesse_ , Ann. Mat. Pura Appl. (1949), 173–183.
  * [14] J Dutta and AM Rubinov, _Abstract convexity_ , Handbook of generalized convexity and generalized monotonicity 76 (2005), 293–333.
  * [15] W Fraser and JF Hart, _On the computation of rational approximations to continuous functions_ , Communications of the ACM 5 (1962), no. 7, 401–403.
  * [16] Miguel A Goberna and Marco A López, _A comprehensive survey of linear semi-infinite optimization theory_ , Semi-infinite programming, Springer, 1998, pp. 3–27.
  * [17] Henry L Loeb, _Algorithms for chebyshev approximations using the ratio of linear forms_ , Journal of the Society for Industrial and Applied Mathematics 8 (1960), no. 3, 458–465.
  * [18] H.L. Loeb, _On rational fraction approximations at discrete points, convair astronautics, math_ , 9 (1957).
  * [19] George G Lorentz, Manfred von Golitschek, and Yuly Makovoz, _Constructive approximation: advanced problems_ , vol. 304, Springer, 1996.
  * [20] J.E. Martínez-Legaz, _Quasiconvex duality theory by generalized conjugation methods_ , Optimization 19 (1988), no. 5, 603–652.
  * [21] G. Meinardus, _Approximation of functions: Theory and numerical methods_ , Springer-Verlag, Berlin, 1967.
  * [22] G. Meinardus, G. Nürnberger, M. Sommer, and H. Strauss, _Algorithms for piecewise polynomials and splines with free knots_ , Mathematics of Computation 53 (1989), 235–247.
  * [23] B. Mulansky, _Chebyshev approximation by spline functions with free knots_ , IMA Journal of Numerical Analysis 12 (1992), 95–105.
  * [24] Yuji Nakatsukasa, Olivier Sete, and Lloyd N. Trefethen, _The aaa algorithm for rational approximation_ , SIAM Journal on Scientific Computing 40 (2018), no. 3, A1494–A1522.
  * [25] J.X. Da Cruz Neto, J.O. Lopes, and M.V. Travaglia, _Algorithms for quasiconvex minimization_ , Optimization 60 (2011), no. 8-9, 1105–1117.
  * [26] Nimit Nimana, Ali P. Farajzadeh, and Narin Petrot, _Adaptive subgradient method for the split quasi-convex feasibility problems_ , Optimization 65 (2016), no. 10, 1885–1898.
  * [27] R. B. Northrop, _Signals and systems analysis in biomedical engineering_ , CRC Press, Boca Raton, Florida, USA, 2003.
  * [28] G. Nürnberger, _Approximation by spline functions_ , Springer-Verlag, 1989\.
  * [29] Michael R Osborne and G Alistair Watson, _An algorithm for minimax approximation in the nonlinear case_ , The Computer Journal 12 (1969), no. 1, 63–68.
  * [30] Vinesha Peiris, Nir Sharon, Nadezda Sukhorukova, and Julien Ugon, _Generalised rational approximation and its application to improve deep learning classifiers_ , Applied Mathematics and Computation 389 (In Press).
  * [31] P. Petrushev and V. Popov, _Rational approximation of real functions_ , Cambridge University Press, 1987.
  * [32] Anthony Ralston, _Rational chebyshev approximation by remes’ algorithms_ , Numer. Math. 7 (1965), no. 4, 322–330.
  * [33] Anthony Ralston and Philip Rabinowitz, _A first course in numerical analysis_ , Courier Corporation, 2001.
  * [34] J.R. Rice, _The approximation of functions: Nonlinear and multivariate theory_ , Addison-Wesley series in computer science and information processing, Mass., Addison-Wesley Publishing Company, 1969.
  * [35] TJ Rivlin, _Polynomials of best uniform approximation to certain rational functions_ , Numerische Mathematik 4 (1962), no. 1, 345–349.
  * [36] A. M. Rubinov and B. Simsek, _Conjugate quasiconvex nonnegative functions_ , Optimization 35 (1995), no. 1, 1–22.
  * [37] Alex M. Rubinov, _Abstract convexity and global optimization_ , Kluwer Academic Publishers, New York, 2000.
  * [38] L. Schumaker, _Uniform approximation by chebyshev spline functions. II: free knots_ , SIAM Journal of Numerical Analysis 5 (1968), 647–656.
  * [39] Nadezda Sukhorukova, _Uniform approximation by the highest defect continuous polynomial splines: necessary and sufficient optimality conditions and their generalisations_ , Journal of Optimization Theory and Applications 147 (2010), no. 2, 378–394.
  * [40] Nadezda Sukhorukova and Julien Ugon, _Characterization theorem for best linear spline approximation with free knots_ , Dyn. Contin. Discrete Impuls. Syst 17 (2010), no. 5, 687–708.
  * [41] Nadezda Sukhorukova and Julien Ugon, _Characterisation theorem for best polynomial spline approximation with free knots_ , Trans. Amer. Math. Soc. (2017), 6389–6405.
  * [42] Shin ya Matsushita and Li Xu, _On the finite termination of the douglas-rachford method for the convex feasibility problem_ , Optimization 65 (2016), no. 11, 2037–2047.
  * [43] Yuning Yang and Qingzhi Yang, _Some modified relaxed alternating projection methods for solving the two-sets convex feasibility problem_ , Optimization 62 (2013), no. 4, 509–525.
  * [44] A. J. Zaslavski, _Subgradient projection algorithms and approximate solutions of convex feasibility problems_ , Journal of Optimization Theory and Applications 157.
  * [45] Xiaopeng Zhao and Markus Arthur Köbis, _On the convergence of general projection methods for solving convex feasibility problems with applications to the inverse problem of image recovery_ , Optimization 67 (2018), no. 9, 1409–1427.


# Auger-spectroscopy in quantum Hall edge channels: a possible resolution to
the missing energy problem

T. Krähenmann  corresponding author<EMAIL_ADDRESS>Solid State Physics
Laboratory, ETH Zürich, CH-8093 Zürich, Switzerland  S. G. Fischer  Department
of Condensed Matter Physics, Weizmann Institute of Science, Rehovot, 76100
Israel  Department of Physics, Ben-Gurion University of the Negev, Beer-Sheva,
84105 Israel  M. Röösli  T. Ihn  C. Reichl  W. Wegscheider  K. Ensslin  Solid
State Physics Laboratory, ETH Zürich, CH-8093 Zürich, Switzerland  Y. Gefen
Department of Condensed Matter Physics, Weizmann Institute of Science,
Rehovot, 76100 Israel  Y. Meir  Department of Physics, Ben-Gurion University
of the Negev, Beer-Sheva, 84105 Israel  The Ilse Katz Institute for Nanoscale
Science and Technology, Ben-Gurion University of the Negev, Beer-Sheva, 84105
Israel

###### Abstract

Quantum Hall edge channels offer an efficient and controllable platform to
study quantum transport in one dimension. Such channels are a prospective tool
for the efficient transfer of quantum information at the nanoscale, and play a
vital role in exposing intriguing physics. Electric current along the edge
carries energy and heat leading to inelastic scattering, which may impede
coherent transport. Several experiments attempting to probe the concomitant
energy redistribution along the edge reported energy loss via unknown
mechanisms of inelastic scattering. Here we employ quantum dots to inject and
extract electrons at specific energies, to spectrally analyse inelastic
scattering inside quantum Hall edge channels. We show that the “missing
energy” puzzle can be untangled by incorporating non-local Auger-like
processes, in which energy is redistributed between spatially separate parts
of the sample. Our theoretical analysis, accounting for the experimental
results, challenges common-wisdom analyses which ignore such non-local decay
channels.

##  I introduction

The concept of quantum Hall edge channels is well supported by numerous
experiments bocquillon_electron_2014 . Directed transport in these channels
serves as a platform to realize electronic counterparts of optical
interferometers in mesoscopic devices henny_fermionic_1999 ;
ji_electronic_2003 ; neder_interference_2007 ; bocquillon_electron_2012 ;
bocquillon_coherence_2013 . The propagation of charge modes altimiras_non-
equilibrium_2010 ; le_sueur_energy_2010  as well as neutral modes
bid_observation_2010 ; deviatov_energy_2011 ; altimiras_chargeless_2012 ;
venkatachalam_local_2012  in quantum Hall edge channels have been
investigated. Relaxation of non-equilibrium electrons between edge channels
and possible coupling to the bulk of the sample, however, is not
satisfactorily understood. In fact, several experiments indicated the
existence of another, so far unknown channel for energy loss.

In a first experiment le_sueur_energy_2010  addressing the equilibration of
two edge channels in the integer quantum Hall regime, a non-equilibrium
distribution has been injected into the outermost channel via a quantum point
contact. Increasing the propagation distance, the channel has been probed by a
quantum dot (QD), to record the gradual equilibration of the initial
distribution. In the course of equilibration, a significant amount of energy
is lost to degrees of freedom that are not controlled in the setup
degiovanni_plasmon_2010 ; lunde_interaction-induced_2010 ;
kovrizhin_equilibration_2011 . In a follow-up experiment at the same filling
factor bocquillon_separation_2013 , the modes of the outer edge channel have
been excited at specific energies by an RF-circuit, to be probed by an Ohmic
contact downstream from the point of injection. That setup measured the
dispersion of one of the ensuing eigenmodes, which showed that the chiral
channels were dissipative. Also in that case, the concomitant energy loss
remained unaccounted for.

Here we demonstrate that, surprisingly, significant energy redistribution
occurs also between sample components that are spatially well-separated. To
this end, we use a QD to energy-selectively emit electrons from a biased
Source contact into a quantum Hall edge at integer filling factor. This edge
is subsequently probed by a second QD which serves as an energy-resolved
detector. In the ensuing Emitter-Detector energy landscape currents are
measured at detection energies that exceed emission energies, which ostensibly
indicates a violation of energy conservation. The apparent contradiction can
only be resolved by considering processes in which recombination energy is
transferred from the Source contact to the edge channel probed by the Detector
QD. This recombination energy stems from Source electrons that reoccupy empty
states left behind by electrons previously tunnelling through the Emitter QD
into the edge. The insight that such Auger-like recombination processes cause
the unexpected currents is underpinned by additional measurements with a
Sensor QD that solely detects currents generated by such processes, and
through a theoretical analysis employing non-equilibrium perturbation theory.
Our findings indicate that inter-edge interactions play a significant role in
quantum Hall edge channel equilibration, and constitute an energy loss
mechanism that has so far been disregarded.

##  II QUANTUM DOT ELECTRON SPECTROMETER

A scanning electron micrograph of a typical sample to investigate the
relaxation in quantum Hall edge channels is shown in Fig. 1a. Metallic top-
gates are used to electrostatically define QDs in a high-mobility two-
dimensional electron system (2DES) incorporated 90 nm below the surface of a
GaAs/AlGaAs heterostructure. The electron mobility is
$\mu_{\mathrm{el}}=2.2\times 10^{6}$ cm2V-1s-1 at $T=1.3$ K with an electron
density of $n_{\mathrm{s}}=2.0\times 10^{11}$ cm-2. Three QDs labelled Emitter
(red), Detector (blue) and Sensor (green) are defined. When a magnetic field
is applied perpendicular to the plane of the 2DES, chiral electron transport
along the sample edge will be present, as indicated with yellow arrows. Ohmic
contacts labelled Source, Drain, Reservoir, ”Right” and ”Left” allow us to
apply DC voltages as indicated. The currents flowing into these terminals of
the device are measured using current-voltage converters. All measurements
were performed in a dilution refrigerator at the electronic base temperature
$T_{\mathrm{el}}=25$ mK. In a typical experiment, current is injected from the
Source through the Emitter QD into the Reservoir. The Detector and Sensor QDs
are used to measure the edge-excitations of the Reservoir and ”Right” contact,
respectively, caused by the injected electrons. The barrier gate between the
Source and ”Right” regions of the 2DES is tuned such as to effectively
suppress electron transfer between the two regions.

Figure 1:  (a) Scanning electron micrograph of a typical sample to investigate
energy relaxation in the quantum Hall edge channels. Metallic top-gates
(light-grey) on the surface of the GaAs (dark grey) are used to define QDs
(indicated by circles). A magnetic field is applied perpendicular to the 2DES
(except in Fig. 2). The chirality of the resulting edge-channels is indicated
by arrows. The current through each QD is measured separately in the contacts
(yellow patches). (b) Energy schematic of the sample depicted in (a).

Figure 1b schematically illustrates the alignment of the different
electrochemical potentials ($\mu_{i}$) under the conditions of our experiment.
The electrochemical potentials of the Fermi seas (yellow in Fig. 1b) are kept
constant while the electrochemical potentials of the QDs are varied by
changing the voltages applied to the respective plunger gate. Finite bias
spectroscopy (data not shown) of the individual QDs allows us to relate the
plunger gate voltage to the energy of the QD electrochemical potential
quantitatively. In such a configuration, resonant single-electron transfer
from the Source to the Reservoir through the Emitter QD creates a single hole
and a single electron excitation in the edge channels of the respective
regions. The non-equilibrium single-electron excitation, for example,
propagates along the sample edge. If it remains unaffected by interactions
with other electrons it can be detected by the Detector QD at the injection
energy. However, if it interacts on its way with other electrons, it loses
energy and causes an edge channel shake-up.

Figure 2:  Current through the Emitter (red) and Detector (blue) QD as a
function of Detector plunger gate voltage in the absence of a perpendicular
magnetic field ($B=0$ T). The black dashed line indicates the background
contribution of the Detector QD current due to an experimentally unavoidable
slight misalignment between $\mu_{\mathrm{Res}}$ and $\mu_{\mathrm{Drain}}$.
The current through the Emitter QD stays constant for varying Detector QD
chemical potential. The current through the Emitter QD shows both elastic and
inelastic contributions. The insets show the schematic level alignment of the
respective configurations.

The result of such a transfer experiment from the Emitter to the Detector QD
at zero magnetic field, i.e. in the absence of chiral edge transport, is shown
in Fig. 2. A constant voltage $V_{\mathrm{Source}}=-400~{}\mu V$ is applied
between the Source and Reservoir contact. The currents through the Emitter QD
(in red) and through the Detector QD (in blue) for varying Detector QD plunger
gate voltage, i.e. for varying $\mu_{\mathrm{DET}}$, are shown in Fig. 2. The
black dashed line indicates the background contribution of the Detector QD
current due to an experimentally unavoidable slight misalignment between
$\mu_{\mathrm{Res}}$ and $\mu_{\mathrm{Drain}}$. Here the Emitter
electrochemical potential is kept constant inside the bias window, i.e. the
emission energy of the electrons ($\mu_{\mathrm{EM}}$) is fixed, only
$\mu_{\mathrm{DET}}$ is varied. The current through the Emitter QD stays
roughly constant as a function of Detector QD plunger gate. This is expected
due to the small cross-capacitive coupling between Detector and Emitter QD.

At large negative values of $V_{\mathrm{DET}}$ (around
$V_{\mathrm{DET}}=-0.6573$ V) the resonance condition
$\mu_{\mathrm{EM}}\approx\mu_{\mathrm{DET}}$ holds and we measure a peak of
elastic electron transfer between the QDs (see insets for the corresponding
level alignment). The elastic transfer probability
($|I_{\mathrm{DET}}/I_{\mathrm{EM}}|$ at
$\mu_{\mathrm{EM}}=\mu_{\mathrm{DET}}$) is rather small, here on the order of
0.2 $\%$. It depends on the emission energy and the tunnelling rates. At more
positive values of $V_{\mathrm{DET}}$ the detection energy is lower than the
emission energy ($\mu_{\mathrm{DET}}<\mu_{\mathrm{EM}}$) and the shake-up of
the Fermi sea is measured. The Detector current increases for lower detection
energies close to $\mu_{\mathrm{DET}}=0$. The ballistic transfer of electrons
between QDs, theoretically analysed in a different context in Ref.
takei_nonequilibrium_2010 , has already been measured previously and shows
quantitatively similar results hohls_ballistic_2006 ;
rossler_spectroscopy_2014 .

##  III SPECTROSCOPY OF EDGE CHANNEL TRANSFER

Figure 3: (a) 2D colour plot of the current through the Detector QD for
varying Detector QD ($x$-axis) and Emitter QD plunger gate voltage ($y$-axis).
The encircled numbers refer to the energetic points mentioned in the text and
are explained in detail in the Supplemental Material. The signal is plotted on
a logarithmic colour scale preserving the direction of electron tunnelling in
the colour code. (b) Calculated current through the Detector QD for the
experimental situation depicted in (a). (c) I-III schematic description of the
electron scattering processes involved in the transfer. IV shows the diagram
corresponding to the process in III, generating current in the triangle 1\-
2\- 4.

In the absence of a magnetic field electrons can scatter back from the
Detector QD and form a standing wave in the Reservoir 2DES area. Standing
waves have been shown to alter transport properties drastically
katine_point_1997 ; rossler_transport_2015 ; steinacher_scanning_2018 .
Applying a strong perpendicular magnetic field does not only reduce standing
waves by reducing backscattering but also introduces chiral transport along
the sample edge and favours the directed transfer of electrons. For all the
following measurements a perpendicular magnetic field $B=3$ T is applied,
corresponding to the quantum Hall plateau at filling factor $\nu=3$. In the
regime, where the magnetic field is strong enough to support quantum Hall edge
currents (here $B\geq 1$ T), we do not find a qualitative influence of the
magnetic field strength or the bulk filling factor on the results presented
below. The QDs are coupled mostly to the outermost edge channel, corresponding
to the energetically lowest Landau level. The presence of the outermost edge
channel is not influenced by the bulk filling factor or the compressibility of
the bulk. As for each different value of magnetic field the voltages applied
to the tunnelling barrier gates have to be adjusted slightly, a quantitative
analysis of the influence of the magnetic field strength on our measurement
results is not possible.

Changing the values of both $V_{\mathrm{DET}}$ and $V_{\mathrm{EM}}$ during a
transfer measurement, we measure the 2D-colour map of Detector current shown
in Fig. 3a. The signal is plotted on a logarithmic colour scale preserving the
direction of electron tunnelling. A red signal corresponds to electrons
tunnelling from the Reservoir lead to the Drain side (from Drain to Reservoir
for a blue signal). Each point in the 2D-map corresponds to specific energies
of the Emitter and Detector QD levels. Characteristic points are indicated by
numbers and the corresponding energy level alignments are shown in the
supplemental material. The current through the Emitter QD for the same
measurement (see supplemental material) depends only on $V_{\mathrm{EM}}$ and
is independent of $V_{\mathrm{DET}}$.

The peak of elastic transfer shown for the zero magnetic field case in Fig. 2a
is largely suppressed in the Detector current in Fig. 3a at finite magnetic
field. The diagonal line connecting 1 and 3 still marks the boundary between a
region of suppressed and sizeable Detector current. At points 1/ 3 we emit and
detect electrons close to the Fermi energy of the Reservoir/Source contact.

Emitted electrons can interact with other electrons (see Fig. 3c I and II) and
thereby dissipate energy. Hence, a non-equilibrium distribution function will
develop along the course of the outermost edge channel. This non-equilibrium
current can be observed as long as the detection energy is lower than the
emission energy and the Detector QD level is above the electrochemical
potentials of the grounded contacts
($\mu_{\mathrm{EM}}>\mu_{\mathrm{DET}}>\mu_{\mathrm{Res/D}}$; corresponding to
the region inside the triangle 1\- 3\- 4).

The Detector QD level is equal to the equilibrium electrochemical potential of
its connecting leads along line 1 to 4. Lowering the Detector QD level further
(more positive $V_{\mathrm{DET}}$) will fill the Detector QD with an electron,
hence enabling us to probe the Reservoir non-equilibrium distribution below
its equilibrium electrochemical potential. The shake-up of the Fermi system
will generate unoccupied states there exceeding the number of thermally
unoccupied states present in equilibrium.

The maximal energy an emitted electron can lose in a scattering event is its
energy above the Fermi energy, which we call the emission energy. This is also
the maximal amount of energy which can be transferred to another electron,
hence, the lowest lying state which will be emptied lies exactly this amount
of energy below the Fermi level. The symmetric outline of the negative signal
we observe supports this claim. Within the triangle 1\- 4\- 5 we hence probe
”holes” in the Reservoir, generated by collisions of emitted electrons with
Fermi sea electrons in the Reservoir (Fig. 3c II). The slight positive signal
close to the diagonal line 1\- 5 is due to the presence of an excited state in
the Detector QD, which we will not discuss further here (see supplemental
material for details).

Around points 2 and 6 we also observe a large shake-up of the edge channel
distribution, however, the previously described processes cannot account for
the involved energies. Around 2 the detection energy is much higher than the
emission energy. We attribute these high energy electrons to be the result of
an Auger-like recombination process occurring in the course of electron
tunnelling through the Emitter. An electron tunnelling through the Emitter
will leave behind an empty state in the Source Fermi sea. This ”hole” will
dissipate its excess energy, possibly by recombining with an energetically
higher lying electron in the same contact region. This recombination can, like
in Auger recombination, excite another electron in the Reservoir region (Fig.
3c III). The largest energy which could be transferred in such a process
corresponds to the energy difference of the Source Fermi level to the Emitter
QD level (explaining the negative slope diagonal from 2 to 4). The excited
electron will, due to the edge channels, be transported to the Detector QD
where it is spectroscopically investigated. The negative signal around 6 can
be understood as a consequence of ”holes” in the Reservoir generated in the
same process.

To substantiate that electron collisions cause the measured inelastic currents
displayed in Fig. 3a, the currents in the triangles described above are set in
relation to underlying physical processes by second order non-equilibrium
diagrammatic perturbation theory. The Source, Drain and Reservoir regions are
modelled as single, parallel and one-dimensional channels with linear
dispersion. Tunnelling connects these channels via Emitter and Detector QDs
represented by single resonant levels.

Dressing electron lines with tunnelling events in the self-energies of the
Reservoir and the Source-Reservoir interaction generates distinct diagrams for
processes which contribute to the inelastic current. The Detector current
obtained by this approach is displayed in Fig. 3b. A finite-range model
interaction between electrons in the Reservoir generates current in triangles
1\- 3\- 4 and 1\- 4\- 5. The same form of interaction between Source and
Reservoir electrons, additionally accounting for the spatial separation of the
respective channels, generates current in triangles 1\- 2\- 4 and 1\- 4\- 6.
Figure 3c IV shows an exemplary diagram which corresponds to the transition
amplitude of the Auger-like process depicted in Fig. 3c III, and contributes
in triangle 1\- 2\- 4.

While second order perturbation theory does not support strong enough
interactions to account for features such as the largely absent line of
elastic transfer in Fig. 3a (within the energy range defined by the Source-
Drain bias, second order perturbation theory breaks down for higher values of
interaction strength or transfer time), the treatment does show that Auger-
like recombination in the Source causes signals in regions of the Emitter-
Detector energy diagram, which cannot be explained in terms of interactions
between Reservoir electrons alone.

##  IV DIRECT MEASUREMENT OF AUGER-LIKE PROCESSES

Figure 4: (a) 2D colour plot of the current through the Sensor QD for varying
Sensor QD ($x$-axis) and Emitter QD plunger gate voltage ($y$-axis). The
signal is plotted on a logarithmic scale preserving the direction of electron
tunnelling in the colour code. The dashed line corresponds to the maximal
energy which can be transferred by Auger-like recombination:
$\mu^{\mathrm{max}}_{\mathrm{Sens}}-\mu_{\mathrm{S}}=\mu_{\mathrm{S}}-\mu_{\mathrm{EM}}$.
(b) Calculated current through the Sensor QD for the experimental situation
depicted in (a)

We now turn our attention to additional experimental investigations
consolidating the interpretation of the data suggested above. The sample shown
in Fig. 1a is explicitly designed to investigate the non-equilibrium
distribution of electrons while emitting electrons through a QD. In addition
to the two aforementioned QDs there is a third, the Sensor QD. The Sensor QD
is electrically isolated from the Emitter/Detector part of the sample, which
means that no electric current can flow from Source to Right. The gates
between the Source and the ”Right” contact are biased with a large negative
voltage which induces a barrier in the 2DES. The Source bias voltage (here
$V_{\mathrm{Source}}=-700~{}\mu$V) is also applied to both the ”Right” and the
”Left” lead of the Sensor QD (see Fig. 1b), i.e.
$\mu_{\mathrm{S}}=\mu_{\mathrm{R}}=\mu_{\mathrm{L}}$. In the following we use
the Sensor QD to measure the non-equilibrium distribution in the ”Right”
contact while electrons tunnel through the Emitter QD. Such a measurement is
shown in Fig. 4. The current through the Sensor QD, now plotted as a function
of $V_{\mathrm{EM}}$ and $V_{\mathrm{Sens}}$, is shown in Fig 4a. For a plot
of the current through the Emitter, as well as for the level schematics
corresponding to the highlighted points, we refer to the supplemental
material. The slight tilt in the data, seen for example along line 2\- 6, is
due to the cross-capacitance between the Sensor and Emitter QDs and their
respective plunger gates, which is larger than for the Emitter and Detector.
In the current through the Sensor QD (in Fig. 4a) we observe a positive
current in the triangle 1\- 2\- 4 and a negative current in the triangle 1\-
4\- 6. The signal in the triangle 1\- 3\- 4 is mostly absent, except for a
slight positive current along the line connecting 3 and 4. Similarly, also the
signal in the triangle 1\- 4\- 5 is absent, except for a slight negative
current along the line connecting 4 and 5. Away from the line connecting 1 and
4 the current through the Sensor QD is directly proportional to the non-
equilibrium distribution of the outermost edge channel in the ”Right” contact.

From the signal measured in the Sensor we draw two major conclusions. First,
measuring a signal away from the background current along the line connecting
1 and 4 shows that there are non-equilibrium electrons generated in the
”Right” contact region while electrons tunnel through the Emitter QD. As the
direct electron transport from the Source to the ”Right” side is barred, we
observe an energy transfer from the Source contact to the ”Right” contact.
Second, the fact that the maximal energy at which electrons are observed to
tunnel through the Sensor depends on the energetic position of the Emitter
level
($\mu^{\mathrm{max}}_{\mathrm{Sens}}-\mu_{\mathrm{S}}=\mu_{\mathrm{S}}-\mu_{\mathrm{EM}}$;
indicated by the dashed line connecting 2 and 4 in Fig. 4a) excludes a
thermopower effect to be the reason for this observation, as heating would be
independent of the Emitter chemical potential. However, Auger-like
recombination can account for this observation.

The signal close to 3 and 5, does not comply with the Auger-like recombination
in the Source Fermi sea, but can be explained by an Auger-like recombination
in the Reservoir Fermi sea. We have seen that an emitted electron undergoes
scattering events where another electron is excited. This could account for
the signal measured at positions 3 and 5.

To underpin the aforementioned conjectures derived from the measurement data
displayed in Fig. 4a in the extended experiment, the theoretical model is
amended by a ”Left” and a ”Right” channel as well as by a Sensor resonant
level. The Sensor current obtained from the amended model is shown in Fig. 4b.
Interactions between Source and ”Right” electrons here indeed generate current
in triangles 1\- 2\- 4 and 1\- 4\- 6, while interactions between Reservoir and
”Right” electrons generate current in triangles 1\- 3\- 4 and 1\- 4\- 5. The
smaller magnitude of the current in the latter triangles results from the
larger separation of the channels involved in the respective transport
processes.

##  V Conclusion

In conclusion, we have investigated the non-equilibrium distribution of
electrons generated by electron emission from a QD into a quantum Hall edge
channel. We observe both the direct shake-up of the edge channel into which
electrons are emitted, and the shake-up of distant edge channels which are
only capacitively coupled to the emitted electrons. While global energy
conservation is fulfilled, our measurements indicate that highly biased
quantum devices can excite degrees of freedom in other nearby systems which
are not directly but only capacitively coupled. To attain a more complete
picture of energy relaxation, future experimental and theoretical analyses
accounting for multiple edge channels, allowing to control such multi-channel
Auger processes, should be carried out. Furthermore, investigating such energy
redistribution in the fractional quantum Hall effect might shed light on the
nature and interactions of quasiparticles in fractional quantum Hall ground
states.

###### Acknowledgements.

This work was supported by the Swiss National Science Foundation through the
National Center for Competence in Research (NCCR) Quantum Science and
Technology (QSIT). S.G.F. acknowledges financial support from the Minerva
foundation. Y.G. was supported by DFG RO 2247/11-1 and CRC 183 (project C01),
and the Italia-Israel project QUANTRA. Y.M. acknowledges support from ISF
grant 292/15.

## References

  * (1) Bocquillon, E. _et al._ Electron quantum optics in ballistic chiral conductors.  _Annalen der Physik_ 526, 1–30 (2014).
  * (2) Henny, M. _et al._ The Fermionic Hanbury Brown and Twiss Experiment.  _Science_ 284, 296–298 (1999).
  * (3) Ji, Y. _et al._ An electronic Mach–Zehnder interferometer.  _Nature_ 422, 415–418 (2003).
  * (4) Neder, I. _et al._ Interference between two indistinguishable electrons from independent sources.  _Nature_ 448, 333–337 (2007).
  * (5) Bocquillon, E. _et al._ Electron Quantum Optics: Partitioning Electrons One by One.  _Physical Review Letters_ 108, 196803 (2012).
  * (6) Bocquillon, E. _et al._ Coherence and Indistinguishability of Single Electrons Emitted by Independent Sources.  _Science_ 339, 1054–1057 (2013).
  * (7) Altimiras, C. _et al._ Non-equilibrium edge-channel spectroscopy in the integer quantum Hall regime.  _Nature Physics_ 6, 34–39 (2010).
  * (8) le Sueur, H. _et al._ Energy Relaxation in the Integer Quantum Hall Regime.  _Physical Review Letters_ 105, 056803 (2010).
  * (9) Bid, A. _et al._ Observation of neutral modes in the fractional quantum Hall regime.  _Nature_ 466, 585–590 (2010).
  * (10) Deviatov, E. V., Lorke, A., Biasiol, G. & Sorba, L.  Energy Transport by Neutral Collective Excitations at the Quantum Hall Edge.  _Physical Review Letters_ 106, 256802 (2011).
  * (11) Altimiras, C. _et al._ Chargeless Heat Transport in the Fractional Quantum Hall Regime.  _Physical Review Letters_ 109, 026803 (2012).
  * (12) Venkatachalam, V., Hart, S., Pfeiffer, L., West, K. & Yacoby, A.  Local thermometry of neutral modes on the quantum Hall edge.  _Nature Physics_ 8, 676–681 (2012).
  * (13) Degiovanni, P. _et al._ Plasmon scattering approach to energy exchange and high-frequency noise in $\nu=2$ quantum Hall edge channels.  _Physical Review B_ 81, 121302 (2010).
  * (14) Lunde, A. M., Nigg, S. E. & Büttiker, M.  Interaction-induced edge channel equilibration.  _Physical Review B_ 81, 041311 (2010).
  * (15) Kovrizhin, D. L. & Chalker, J. T.  Equilibration of integer quantum Hall edge states.  _Physical Review B_ 84, 085105 (2011).
  * (16) Bocquillon, E. _et al._ Separation of neutral and charge modes in one-dimensional chiral edge channels.  _Nature Communications_ 4, 1839 (2013).
  * (17) Takei, S., Milletarì, M. & Rosenow, B.  Nonequilibrium electron spectroscopy of Luttinger liquids.  _Physical Review B_ 82, 041306 (2010).
  * (18) Hohls, F., Pepper, M., Griffiths, J. P., Jones, G. a. C. & Ritchie, D. A.  Ballistic electron spectroscopy.  _Applied Physics Letters_ 89, 212103 (2006).
  * (19) Rössler, C. _et al._ Spectroscopy of equilibrium and nonequilibrium charge transfer in semiconductor quantum structures.  _Physical Review B_ 90, 081302 (2014).
  * (20) Katine, J. A. _et al._ Point Contact Conductance of an Open Resonator.  _Physical Review Letters_ 79, 4806–4809 (1997).
  * (21) Rössler, C. _et al._ Transport Spectroscopy of a Spin-Coherent Dot-Cavity System.  _Physical Review Letters_ 115, 166603 (2015).
  * (22) Steinacher, R. _et al._ Scanning gate experiments: From strongly to weakly invasive probes.  _Physical Review B_ 98, 075426 (2018).