# Exact bounds on the amplitude and phase of the interval discrete Fourier
transform in polynomial time

Marco de Angelis

(December 17, 2021)

###### Abstract

We elucidate why an interval algorithm that computes the exact bounds on the
amplitude and phase of the discrete Fourier transform can run in polynomial
time. We address this question from a formal perspective to provide the
mathematical foundations underpinning such an algorithm. We show that the
procedure set out by the algorithm fully addresses the dependency problem of
interval arithmetic, making it usable in a variety of applications involving
the discrete Fourier transform.

For example when analysing signals with poor precision, signals with missing
data, and for automatic error propagation and verified computations.

Keywords: Interval mathematics, Dependency tracking, Discrete Fourier
transform.

##  1 Introduction

In a recent work, an algorithm that computes the exact bounds on the amplitude
of the discrete Fourier transform (DFT) in polynomial time was presented [1].
In this paper, the focus is shifted towards the mathematical foundations
underpinning the interval algorithm presented in the above work.

The paper is structured as follows: first, we introduce the mathematical
expression of the Fourier transform under study, see §1.1. In §2 propaedeutic
theoretical foundations of interval analysis are given, in §3 the interval
Fourier transform is introduced, in §4 the main results are presented,
followed by a discussion section in §5 .

### Notation

The standardized notation of interval analysis is adopted throughout the
manuscript [3].

###  1.1 The discrete Fourier transform

Let $x=(x_{0},\ldots,x_{N-1})\in\mathbb{R}^{N}$ be a vector, denote $x_{n}$
the $(n+1)$-th coordinate of the vector $x$. We study the discrete Fourier
transform of $x$ which is given by the algebraic expression:

$\mathsf{f}_{h}(x):=\sum_{n=0}^{N-1}x_{n}\ w_{hn}$ (1)

where
$w_{hn}:=e^{-{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}\frac{2\pi}{N}hn}$
is the so-called Fourier coefficient with
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}=\sqrt{-1}$,
$w_{hn}\in\mathbb{C}$, and $h=0,...,N-1$ a positive integer often called a
harmonic or frequency number. Since $n,h=0,\ldots,N-1$, the Fourier
coefficients form a matrix of size $N\times N$ called $W$, with elements
$w_{hn}:=W[h,n]$.

$w_{h}$$W=$$0$ $1$ $\cdots$ $n$ $\cdots$ $N-1$$0$ $w_{00}$ $w_{01}$ $\cdots$
$w_{0n}$ $\cdots$ $w_{0(N-1)}$ $1$ $w_{10}$ $w_{11}$ $\cdots$ $w_{1n}$
$\cdots$ $w_{1(N-1)}$ $\vdots$ $\vdots$ $h$ $w_{h0}$ $w_{h1}$ $\cdots$
$w_{hn}$ $\cdots$ $w_{h(N-1)}$ $\vdots$ $\vdots$ $N-1$ $w_{(N-1)0}$
$w_{(N-1)1}$ $\cdots$ $w_{(N-1)n}$ $\cdots$ $w_{(N-1)(N-1)}$

Therefore (1) can be seen as the complex inner product:

$\mathsf{f}_{h}(x):=\sum_{n=0}^{N-1}x_{n}\
w_{hn}=\left<w_{h},x\right>=\overline{w}_{h}x^{T}$ (2)

where, $\overline{w}_{h}\in\mathbb{C}^{N}$, is the complex conjugate vector of
Fourier coefficients at harmonic $h$, or $(h+1)$-th row of $W$. Since the
matrix of Fourier coefficients is symmetric and orthogonal, the DFT need not
be evaluated for all $h=0,...,N-1$. In particular, when $N$ is a power of two,
it will be sufficient to compute $\mathsf{F}_{h}$ for all $0\leq h\leq N/2$.
Also, observe that expressions (1) and (2) are equivalent from an interval
analysis perspective because of repetitions invariance.

######  Remark 1.1.

In what follows, the Fourier coefficients $w_{hn}$ will be considered as non-
interval floating-point numbers. While this leads to results that are not
verified, this assumption need not affect the generality of the presented
method, which is primarily developed to deal with input uncertainties that are
typically orders of magnitude larger in width than round-off errors. Under
this working assumption, the presented interval algorithm can be considered
rigorous but not verified.

##  2 Theory of interval computations

In this section we will provide an overview of the fundamental definitions and
theorems of interval computations that will be utilised to obtain the main
result.

The theory of interval computations is based on two fundamental pillars: (i)
the notion of an _interval-valued function_ , (ii) and the property of
_inclusion monotonicity_. An _interval-valued function_ is a function (or
computer program), whose inputs are intervals. An interval-valued function is
_inclusion monotonic_ if, when evaluated on two nested intervals, its
resulting ranges are also nested with preserving order. Notion (i) implies
that intervals represent a particular instance of a number; while property
(ii) ensures that interval computations are inclusive thus rigorous. An
interval-valued function that satisfies the property of inclusion monotonicity
is called _inclusive_. There are examples in the literature of interval-valued
function that are not inclusion monotonic. Calculations that are not inclusion
monotonic cannot be regarded as rigorous.

###  2.1 Intervals and united extension

######  Definition 2.1.

(interval)
Let $a,b\in\mathbb{R}$. An interval, denoted by $\boldsymbol{x}$, is the
compact set:

$\boldsymbol{x}:=\\{x:a\leq x\leq b\\}.$

An interval is said to be an element of an interval vector space
$\mathbb{IR}$, such that $\boldsymbol{x}\in\mathbb{IR}$.

######  Definition 2.2.

(n-interval or n-box)
Let $a,b\in\mathbb{R}^{n}$. An n-interval or interval vector, denoted by
$\boldsymbol{x}$, is the n-box:

$\boldsymbol{x}:=\\{x:a_{i}\leq x_{i}\leq b_{i},\ \text{for}\ i=1,...,n\\}.$

An n-interval is said to be an element of an interval vector space
$\mathbb{IR}^{n}$, such that $\boldsymbol{x}\in\mathbb{IR}^{n}$.

Note that our notation intentionally does not distinguish an n-interval from
an interval.

Note that the definition of an n-interval implies non-interactivity, see
Definition 4.1.

######  Definition 2.3.

(Interval-valued function)
An _interval-valued function_ $F:\mathbb{IR}^{n}\rightarrow\mathbb{IR}^{m}$ is
a function that maps an n-interval to an m-interval.

Also note that $F$ is not inclusion monotonic in general.

######  Definition 2.4.

(Inclusion monotonicity)
Let $\boldsymbol{x},\boldsymbol{x}^{\prime}\in\mathbb{IR}^{n}$, let
$F:\mathbb{IR}^{n}\rightarrow\mathbb{IR}^{m}$ be an interval-valued function
that outputs the two m-intervals: $\boldsymbol{y}=F(\boldsymbol{x})$, and
$\boldsymbol{y}^{\prime}=F(\boldsymbol{x}^{\prime})$. Then $F$ is said to be
_inclusion monotonic_ for $\boldsymbol{x}^{\prime}\subset\boldsymbol{x}$, if
and only if:

$F(\boldsymbol{x}^{\prime})\subset F(\boldsymbol{x}).$

######  Definition 2.5.

(Rigorous computations)
Interval computations are said to be _rigorous_ if they satisfy the property
(ii) of inclusion monotonicity.

Note that Definition 2.5 is a weak definition of rigorous computing as it
suitable only for (engineering) problems wherein input uncertainty is
predominant. Stronger definitions of rigorous computing may include
either/both round-off errors or/and truncation errors.

######  Definition 2.6.

(Verified computations)
Interval computations are said to be _verified_ if they are rigorous and
implemented using outward directed rounding.

######  Definition 2.7.

(United extension)
Let $\boldsymbol{x}\in\mathbb{IR}^{n}$ be an n-interval,
$A\subset\mathbb{R}^{n}$ an arbitrary set, $f:A\rightarrow B$ an arbitrary
function that maps $A$ to $B\subset\mathbb{R}^{m}$, and let $S(A)$ be the
collection of all n-intervals that are subsets of $A$. Then, the _united
extension_ of $f$ is:

$\mathcal{F}(A)=\bigcup_{\boldsymbol{x}\in
S(A)}\left\\{f(x):x\in\boldsymbol{x}\right\\}.$ (3)

######  Definition 2.8.

(United set)
The image of the united extension of Definition 2.7 is also called a _united
set_ , and is denoted by $B:=\mathcal{F}(A)$.

######  Definition 2.9.

When $A=\boldsymbol{x}$ is an n-box rather than an arbitrary set the
Definition 2.7 specialises to:

$\mathcal{F}(\boldsymbol{x})=\bigcup_{\boldsymbol{x}^{\prime}\in
S(\boldsymbol{x})}\left\\{f(x):x\in\boldsymbol{x}^{\prime}\right\\}.$

Note that the united set of $\mathcal{F}$ denoted by
$Y:=\mathcal{F}(\boldsymbol{x})$ is not an m-box. The range of $Y$ is often
called a _united box_ and is denoted by:

$\hat{\boldsymbol{y}}:=\text{range}(Y).$

######  Observation 2.10.

A united extension is inclusion monotonic.

###### Proof.

Let $\mathcal{F}$ be a united extension of the function $f$, and let
$A,A^{\prime}\subset\mathbb{R}^{n}$ be two arbitrary sets such that
$A^{\prime}\subset A$. Then, from Definition 2.7 it clearly follows that:

$\mathcal{F}(A^{\prime})\subset\mathcal{F}(A).$

Hence $\mathcal{F}$ is inclusion monotonic. ∎

A united extension is abstracted of the notion of interval and interval
computations, as it belongs to the more general class of set-valued function.
Moreover, a united extension and its united set are unique, thus there is only
one single united extension of a function $f$, and one single united set of
$f$ given an input $A$ or $\boldsymbol{x}$.

Note that there is no polynomial-time algorithm that can compute a united
extension in the general case.

The following result provides the fundamental condition for an interval-valued
function to be considered inclusion monotonic. A proof can be found in [4].

######  Proposition 2.11.

Let $F:\mathbb{IR}^{n}\rightarrow\mathbb{IR}^{m}$ be interval-valued function,
$\boldsymbol{x}\in\mathbb{IR}^{n}$ be a n-interval. Then, $F$ is said to be
inclusion monotonic if:

$\lim_{\boldsymbol{x}\rightarrow\hat{x}}F(\boldsymbol{x})=F(\hat{x})\ \
\text{for\ all}\ \ \hat{x}\in\boldsymbol{x}.$

###  2.2 Interval arithmetic

With the rules of interval arithmetic we can practically turn an algebraic
expression or computer program in to an interval-value function.

######  Definition 2.12.

(United extension of a binary operation)
Let $\boldsymbol{x},\boldsymbol{y}\in\mathbb{IR}$,
$S(\boldsymbol{x},\boldsymbol{y})$ the family of subset of the 2-box
$(\boldsymbol{x},\boldsymbol{y})$, and let $\diamond$ be one of the four
arithmetic operators $+,-,*,\ \text{or}\ /$. Then, the united extension of
$f(x,y)=x\diamond y$ is defined as:

$\mathcal{F}(\boldsymbol{x},\boldsymbol{y})=\bigcup_{(\boldsymbol{x}^{\prime},\boldsymbol{y}^{\prime})\in
S(\boldsymbol{x},\boldsymbol{y})}\\{x\diamond y:x\in\boldsymbol{x}^{\prime},\
y\in\boldsymbol{y}^{\prime}\\},$

provided that $0\notin\boldsymbol{y}$ for $\diamond=/$.

######  Observation 2.13.

(United set of a binary operation)
Let $Z=\mathcal{F}(\boldsymbol{x},\boldsymbol{y})$ be the united set for
$f(x,y)=x\diamond y$, and let
$\boldsymbol{xy}=(\boldsymbol{x},\boldsymbol{y})$ be a 2-box. Then, it holds
that:

$\text{range}(Z)=\\{z:\inf_{x,y\in\boldsymbol{xy}}x\diamond y\leq
z\leq\sup_{x,y\in\boldsymbol{xy}}x\diamond
y\\}=[\inf_{x,y\in\boldsymbol{xy}}x\diamond y,\
\sup_{x,y\in\boldsymbol{xy}}x\diamond y].$ (4)

###### Proof.

The proof follows immediately noticing that $Z\subseteq\mathbb{R}$. ∎

The range of the united set for all four binary arithmetic operations can be
obtained in closed form by means of (4). Let
$\boldsymbol{x}=\\{x:\underline{x}\leq
x\leq\overline{x}\\}=[\underline{x},\overline{x}]$,
$\boldsymbol{y}=\\{y:\underline{y}\leq
x\leq\overline{y}\\}=[\underline{y},\overline{y}]$, then equation (4)
specialises to:

$\displaystyle\boldsymbol{x}+\boldsymbol{y}=\ $
$\displaystyle[\underline{x}+\underline{y},\ \overline{x}+\overline{y}]$
$\displaystyle\boldsymbol{x}-\boldsymbol{y}=\ $
$\displaystyle[\underline{x}-\overline{y},\ \overline{x}-\underline{y}]$
$\displaystyle\boldsymbol{x}*\boldsymbol{y}=\ $
$\displaystyle[\min\\{\underline{x}\underline{y},\overline{x}\underline{y},\underline{x}\overline{y},\overline{x}\overline{y}\\},\
\max\\{\underline{x}\underline{y},\overline{x}\underline{y},\underline{x}\overline{y},\overline{x}\overline{y}\\}]$
$\displaystyle\boldsymbol{x}\ /\ \boldsymbol{y}=\ $
$\displaystyle\boldsymbol{x}*[1/\overline{y},\ 1/\underline{y}],\ \text{for}\
0\notin\boldsymbol{y}$

A more efficient form to evaluate the multiplication rule can be found in [5].

###  2.3 Interval extensions

With the notion of interval-valued function, and the rules of interval
arithmetic we can give a more precise definition of interval computations via
the definition of an interval extension.

######  Definition 2.14.

(Interval extension)
Let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$,
$\boldsymbol{x}\in\mathbb{IR}^{n}$, $x\in\boldsymbol{x}$, and $\mathsf{f}$ be
an algebraic expression of $f$. Then, an _interval extension_ $\mathsf{F}$ of
$f$ via the expression $\mathsf{f}$, is an interval-valued function obtained
evaluating the expression $\mathsf{f}$ on $\boldsymbol{x}$ using the rules of
interval arithmetic.

Recall that the algebra of intervals is not distributive, rather it is _sub-
distributive_ , thus two equivalent algebraic expressions of $f$ may produce
different results when evaluated with interval arithmetic rules [5].

######  Observation 2.15.

An interval extension is inclusion monotonic.

###### Proof.

Let $\mathsf{F}$ be the interval extension of $f$ via the expression
$\mathsf{f}$, whose evaluation consists in applying the rules of interval
arithmetic. Note that because $\mathsf{F}$ is a particular instance of an
interval-valued function, then to prove that $\mathsf{F}$ is inclusion
monotonic, it will be sufficient to show that:

$\lim_{\boldsymbol{x}\rightarrow\hat{x}}\mathsf{F}(\boldsymbol{x})=\mathsf{F}(\hat{x})\
\ \text{for\ all}\ \ \hat{x}\in\boldsymbol{x}.$

Since $\mathsf{F}$ and $\mathsf{f}$ are identical algebraic expressions, when
evaluated on singletons it holds that
$\mathsf{F}(\hat{x})\equiv\mathsf{f}(\hat{x})$, thus the above limit holds for
all $\hat{x}\in\boldsymbol{x}$. ∎

Note that there are as many interval extensions as there are equivalent
algebraic expressions of the function.

The following result can be deemed the fundamental theorem of interval
computations. The theorem states the renowned conservatism of interval
computations. A complete proof of this theorem can be found in the seminal
work of Moore [4].

######  Theorem 2.16.

(Conservatism of interval computations)
Let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ be a function, $\mathcal{F}$
be its united extension, $\mathsf{F}$ be any of its interval extensions, and
$\boldsymbol{x}\in\mathbb{IR}^{n}$. Then, it holds that:

$\mathcal{F}(\boldsymbol{x})\subset\mathsf{F}(\boldsymbol{x}).$

###### Proof.

Let $Y:=\mathcal{F}(\boldsymbol{x})$ be the united set of $\mathcal{F}$, and
$\boldsymbol{y}:=\mathsf{F}(\boldsymbol{x})$ be the m-interval of
$\mathsf{F}$. Since $\mathsf{F}$ is inclusion monotonic the following must
hold:

$\text{range}(Y)\subset\boldsymbol{y}.$

If this were not true, there would be at least a component of $\boldsymbol{y}$
that does not contain the united set, which would imply that there are images
in $Y$ that, while complying with the interval constraints defined by
$\boldsymbol{x}$, are not contained in $\boldsymbol{y}$, which in turns would
violate the inclusion property for $\mathsf{F}$. ∎

Theorem 2.16 in practice states that an interval extension is a so-called
outer approximation of its united extension.

######  Definition 2.17.

(Optimal extension)
Let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ be a function, $\mathcal{F}$
be its united extension, $\boldsymbol{x}\in\mathbb{IR}^{n}$, and
$Y:=\mathcal{F}(\boldsymbol{x})$ be the united set of $\mathcal{F}$ applied to
$\boldsymbol{x}$. Then, a united extension $\mathsf{F}$ is said to be an
_optimal extension_ if and only if:

$\text{range}(Y)=\mathsf{F}(\boldsymbol{x}).$

Note that an optimal extension yields the exact bounds on its corresponding
function.

######  Observation 2.18.

(Dependency problem)
Let $\boldsymbol{x},\boldsymbol{y}\in\mathbb{IR}$,
$\boldsymbol{z}=\boldsymbol{x}\circ\boldsymbol{y}$ and
$\boldsymbol{w}=\boldsymbol{z}\diamond\boldsymbol{x}$ be two intervals
obtained with the rules of interval arithmetic, and ‘$\circ$’ and ‘$\diamond$’
be any two of the four arithmetic operations. Now, let
$f(x,y)=\mathsf{f}(x,y)=(x\circ y)\diamond x$,
$\boldsymbol{w}=\mathsf{F}(\boldsymbol{x},\boldsymbol{y})$, and
$W=\mathcal{F}(x,y)$. Then, it holds that:

$\text{range}(W)\subseteq\boldsymbol{w}.$

###### Proof.

Since there is functional dependence between $\boldsymbol{z}$ and
$\boldsymbol{x}$, the joint set $(\boldsymbol{z},\boldsymbol{x})$ is a subset
of their 2-box. Because the rules of interval arithmetic encode no dependence
assumption, the second expression
$\boldsymbol{w}=\boldsymbol{z}\diamond\boldsymbol{x}$ is evaluated under the
assumption that the joint set $(\boldsymbol{z},\boldsymbol{x})$ is a 2-box,
whereas the joint set $(\boldsymbol{z},\boldsymbol{x})$ is clearly a subset of
their 2-box. Thus any further operation between $\boldsymbol{z}$ and
$\boldsymbol{x}$ results in an interval that is wider than it ought to be. ∎

Because of the dependency problem (Observation 2.18) of interval extensions,
some algebraic expressions evaluate in intervals that are too wide.
Observation 2.18 goes also by the name of _wrapping effect_.

######  Observation 2.19.

(Repeated variables)
Let $f$ be a function, and $\mathsf{f}$ be its algebraic expression with no
repeated variables $\boldsymbol{x}$. Then its interval extension $\mathsf{F}$
is an optimal extension.

###### Proof.

Without repeated variables in an expression, the dependency problem of
Observation 2.18 cannot occur, because the joint dependency structure of all
variables is an n-box. Thus, the rules of interval arithmetic encode the
correct dependency structure between all variables. ∎

An example of interval extensions that are not optimal, i.e. carrying repeated
variables, are polynomials. In a typical polynomial expression the number of
repeated variables coincides with its degree minus one. So for instance, a
second-degree polynomial has one repeated variable. It is generally hard to
rearrange polynomial expressions so that no repeated variables occur.

###  2.4 Complex intervals

######  Definition 2.20.

(Rectangular complex interval)
Let $\boldsymbol{u},\boldsymbol{v}\in\mathbb{IR}$ be two real intervals. A
_rectangular complex interval_ is a 2-box in the complex plane, and is defined
as:

$\boldsymbol{z}=\boldsymbol{u}+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}\boldsymbol{v}=\\{u+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}v\
|\ u\in\boldsymbol{u},\ v\in\boldsymbol{v}\\}.$

####  2.4.1 Amplitude

Let
$z=u+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}v\in\mathbb{C}$
be a complex number, with $u,v\in\mathbb{R}$; then its _amplitude_ (or
absolute value or modulus) is defined as: $|z|=\sqrt{u^{2}+v^{2}}$. Thus the
amplitude of $z$ can be interpreted as the 2-norm of a point in the complex
plane whose coordinates are $(u,v)$. Now let us introduce the amplitude of a
rectangular complex number.

######  Definition 2.21.

(Amplitude of a complex interval)
Let
$\boldsymbol{z}=\boldsymbol{u}+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}\boldsymbol{v}\in\mathbb{IC}$
be a rectangular complex interval, with
$\boldsymbol{u},\boldsymbol{v}\in\mathbb{IR}$. The interval amplitude is
defined as:

$|\boldsymbol{z}|=\\{\sqrt{u^{2}+v^{2}}:u\in\boldsymbol{u},\
v\in\boldsymbol{v}\\}.$

######  Observation 2.22.

(Computing the interval amplitude)
Let $|\boldsymbol{z}|$ be the amplitude of $\boldsymbol{z}\in\mathbb{IC}$, and
let $\text{vert}(\boldsymbol{z})$ be the set of four vertices of
$\boldsymbol{z}$, such that:
$\text{vert}(\boldsymbol{z}):=\\{\underline{u}+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}\underline{v},\
\overline{u}+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}\underline{v},\
\underline{u}+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}\overline{v},\
\overline{u}+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}\overline{v}\\}$.
Now, let $A$ be the set of amplitudes at each vertex such that:

$A:=\\{|\underline{u}+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}\underline{v}|,\
|\overline{u}+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}\underline{v}|,\
|\underline{u}+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}\overline{v}|,\
|\overline{u}+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}\overline{v}|\\}.$

Then, the amplitude of the complex interval $\boldsymbol{z}$ is:

$|\boldsymbol{z}|=\left\\{\begin{matrix}[\min A,\max A],\ &\text{if}\
0\notin\boldsymbol{z},\\\ [0,\ \max A],\ &\text{if}\ 0\in\boldsymbol{z},\\\
[\min A_{1},\ \max A],\ &\text{if}\ 0\in\text{Re}(\boldsymbol{z}),\\\ [\min
A_{2},\ \max A],\ &\text{if}\ 0\in\text{Im}(\boldsymbol{z}).\\\
\end{matrix}\right.$

Where,
$A_{1}:=\\{|0+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}\underline{v}|,\
|0+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}\overline{v}|\\}$,
and
$A_{2}:=\\{|\underline{u}+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}0|,\
|\overline{u}+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}0|\\}$.

###### Proof.

In [1] (Appendix B) a proof for the maximum is provided for any convex set.
For the minimum, when $0\notin\boldsymbol{z}$, the proof is equivalent, whilst
when $0\in\boldsymbol{z}$, clearly the shortest distance is zero. ∎

####  2.4.2 Argument or phase

Let
$z=u+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}v\in\mathbb{C}$
be a complex number, with $u,v\in\mathbb{R}$; then its _argument_ (or phase),
is the angle with the positive real axis, defined as:

$\arg
z=\arg(u+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}v)=\left\\{\begin{matrix}2\arctan\left(\frac{v}{\sqrt{u^{2}+v^{2}}+u}\right)&\text{if}\
u>0,\ v\neq 0,\\\ \pi&\text{if}\ u<0,\ v=0,\\\ \text{undefined}&\text{if}\
u=0,\ v=0.\\\ \end{matrix}\right.$

.

######  Definition 2.23.

(Argument of a complex interval)
Let
$\boldsymbol{z}=\boldsymbol{u}+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}\boldsymbol{v}\in\mathbb{IC}$
be a rectangular complex interval, with
$\boldsymbol{u},\boldsymbol{v}\in\mathbb{IR}$. The interval argument is
defined as:

$\arg\boldsymbol{z}=\\{\arg(u+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}v):u\in\boldsymbol{u},\
v\in\boldsymbol{v}\\}.$

######  Observation 2.24.

(Computing the interval argument)
Let $\arg\boldsymbol{z}$ be the argument of $\boldsymbol{z}\in\mathbb{IC}$,
and let $\text{vert}(\boldsymbol{z})$ be the set of four vertices of
$\boldsymbol{z}$, such that:
$\text{vert}(\boldsymbol{z}):=\\{\underline{u}+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}\underline{v},\
\overline{u}+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}\underline{v},\
\underline{u}+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}\overline{v},\
\overline{u}+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}\overline{v}\\}$.
Now, let $\Phi$ be the set of arguments of each such vertex such that:

$\Phi:=\\{\arg(\underline{u}+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}\underline{v}),\
\arg(\overline{u}+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}\underline{v}),\
\arg(\underline{u}+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}\overline{v}),\
\arg(\overline{u}+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}\overline{v})\\}.$

Then the argument of the complex interval $\boldsymbol{z}$ is:

$|\boldsymbol{z}|=\left\\{\begin{matrix}[\min\Phi,\ \max\Phi],\ &\text{if}\
0\notin\boldsymbol{z},\\\ \text{undefined},\ &\text{if}\
0\in\boldsymbol{z}.\\\ \end{matrix}\right.$

####  2.4.3 Arithmetic between complex intervals

In order to do interval computations between complex intervals the rules of
arithmetic must be defined. For the purpose of this work we are only going to
need the sum and subtraction between complex intervals, as well as the
multiplication of an interval times a complex number.

######  Definition 2.25.

(Sum and subtraction)
Let $\boldsymbol{z},\boldsymbol{w}\in\mathbb{IC}$ be two complex intervals,
$\text{vert}(\boldsymbol{z})$ and $\text{vert}(\boldsymbol{w})$ be their set
of four vertices, and $\diamond=\\{+,-\\}$ be the sum and subtraction
operators. Now let
$\text{vert}(\boldsymbol{z}\boldsymbol{w})=\text{vert}(\boldsymbol{z})\times\text{vert}(\boldsymbol{w})$
be the Cartesian product of all pairs of vertices. Then the arithmetic
operation specialises to:

$\boldsymbol{z}\diamond\boldsymbol{w}=\\{z\diamond
w:(z,w)\in\text{vert}(\boldsymbol{z}\boldsymbol{w})\\}.$

Note that the cardinality of the product set is
$\\#\\{\text{vert}(\boldsymbol{z}\boldsymbol{w})\\}=16$, so exactly $16$
sums/subtractions need to be computed. More efficient implementations of such
operations can be derived noticing that the sum and subtractions only takes
place between diagonally opposite pairs of vertices.

######  Definition 2.26.

(Multiplication between an interval and a complex number)
Let $\boldsymbol{x}\in\mathbb{IR}$ be an interval,
$z:=u+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}v$
be a complex number, and $\\{u\underline{x},u\overline{x}\\}$ be the set of
possible real multiplications. Then, the multiplication between an interval
and a complex number is given by:

$\boldsymbol{x}*z=z*\boldsymbol{x}=[\min\\{u\underline{x},u\overline{x}\\}+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}v,\
\max\\{u\underline{x},u\overline{x}\\}+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}v].$

##  3 Extensions of the discrete Fourier transform

###  3.1 Interval extension

Recall that an interval extension is any algebraic expression, whose entries
have been replaces with intervals, and that an interval extension is always
inclusion monotonic. In this section we define the interval extension
considered throughout this manuscript.

######  Definition 3.1.

(DFT interval extension)
Let $\boldsymbol{x}\in\mathbb{IR}^{N}$ be a sequence of real intervals, and
let $\mathsf{f}_{h}:\mathbb{R}^{N}\rightarrow\mathbb{C}$ be the expression
(1). Then, the _interval extension_ of the discrete Fourier transform at
harmonic $h=0,...,N-1$, $\mathsf{F}_{h}:\mathbb{IR}^{N}\rightarrow\mathbb{IC}$
is simply given by:

$\mathsf{F}_{h}(\boldsymbol{x}):=\sum_{n=0}^{N-1}\boldsymbol{x}_{n}\
e^{-{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}\frac{2\pi}{N}hn}$
(5)

where, $N$ is the size of the N-interval (usually a power of two). The
evaluation of such an expression results in a rectangular complex interval
denoted by: $\boldsymbol{z}_{h}:=\mathsf{F}_{h}(\boldsymbol{x})$.

Note that (5) is an optimal interval extension, under no dependency statement
between the components of $\boldsymbol{x}$. In other words, the interval
extension (5) is optimal because it has no repeated variables in its
expression.

###  3.2 United extension and united set

######  Definition 3.2.

(United extension and united set)
The _united extension_ of the discrete Fourier transform on the N-interval
$\boldsymbol{x}\in\mathbb{IR}^{N}$, is:

$\mathcal{F}_{h}(\boldsymbol{x}):=\bigcup_{\boldsymbol{x}^{\prime}\in
S(\boldsymbol{x})}\left\\{\sum_{n=0}^{N-1}x_{n}\
e^{-{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}\frac{2\pi}{N}hn}:x\in\boldsymbol{x}^{\prime}\right\\}.$
(6)

The image of (6) is named _united set_ , and will be denoted by
$Z_{h}:=\mathcal{F}_{h}(\boldsymbol{x})$, with $Z_{h}\subset\mathbb{C}$.

Note that the united set $Z_{h}$ is not a box in $\mathbb{C}$; this is why it
is not trivial to obtain the exact bounds on the amplitude and phase of the
discrete Fourier transform. Observe that because of the property of inclusion
monotonicity of interval extensions, and because the extension defined in 3.1
is an optimal extension it holds that:

$Z_{h}\subseteq\boldsymbol{z}_{h}\ \ \ \Rightarrow\ \ \
\text{range}(Z_{h})=\boldsymbol{z}_{h},$ (7)

thus the box $\boldsymbol{z}_{h}$ always circumscribes the united set $Z_{h}$.
In other words, taking the range of the united set $Z_{h}$ is equivalent to
evaluating the interval extension $\mathsf{F}_{h}$.

##  4 Reaching the united set

######  Definition 4.1.

(Non-interactive intervals or boxes)
Let $\boldsymbol{x},\boldsymbol{y}\in\mathbb{IR}$. Then, $\boldsymbol{x}$ and
$\boldsymbol{y}$ are said to be _non-interactive_ if their joint set is a
2-box, i.e. if it holds that:
$(\boldsymbol{x},\boldsymbol{y}):=\\{(x,y):x\in\boldsymbol{x},\
y\in\boldsymbol{y}\\}$.

The marginal projections $\boldsymbol{x}$ and $\boldsymbol{y}$, retain all the
information about the joint structure. Also, when no statement about the
dependence between $\boldsymbol{x}$ and $\boldsymbol{y}$, the joint structure
of Definition 4.1 is implied. In other terms, when nothing is stated about the
dependence between two intervals, these will be considered non-interactive.

######  Remark 4.2.

(Non-interactive independence)
Two non-interactive intervals are often referred to as independent in the
literature. Whilst non-interactivity is a form of interval independence, we
tend to avoid the term independence because of the probabilistic
interpretation of intervals, which can be seen as sets of bounded probability
distributions. Under the probabilistic interpretation saying that two
intervals are independent may imply statistical independence, which is a much
stronger statement than non-interactivity. If no dependency statement is made,
the components of an n-interval are mutually non-interactive.

######  Definition 4.3.

(Linearly dependent intervals)
Let $\boldsymbol{x},\boldsymbol{y}\in\mathbb{IR}$. Then $\boldsymbol{x}$ and
$\boldsymbol{y}$ are said to be _linearly dependent_ if their joint set is
defined as:

$(\boldsymbol{x},\boldsymbol{y})_{\bigtimes}:=\\{(x,y):x=\text{mid}\boldsymbol{x}\pm\tau\
\text{rad}\boldsymbol{x},\ y=\text{mid}\boldsymbol{y}\pm\tau\
\text{rad}\boldsymbol{y},\ \tau\in[-1,1]\\},$

where we recall that
$\text{mid}\boldsymbol{x}=(\overline{x}+\underline{x})/2$, and
$\text{rad}\boldsymbol{x}=(\overline{x}-\underline{x})/2$. Note that choosing
a pair of signs $\pm=\\{+,-\\}$, determines the orientation of the joint set.

######  Definition 4.4.

(Interval diagonal)
The joint set of two linearly dependent intervals, denoted by
$(\boldsymbol{x},\boldsymbol{y})_{\bigtimes}$, is called an _interval
diagonal_. An interval diagonal can be regarded as the simplest convex
polytope in $\mathbb{R}^{2}$, with only two vertices. The vertices of such
polytope can be obtained by setting $\tau=\\{-1,1\\}$:

$\text{vert}(\boldsymbol{x},\boldsymbol{y})=\\{(\boldsymbol{x},\boldsymbol{y})_{\bigtimes}:\tau=\\{-1,1\\}\\}.$

######  Definition 4.5.

(Oriented linearly dependent intervals) Let
$\boldsymbol{x},\boldsymbol{y}\in\mathbb{IR}$ be two linearly dependent
intervals, and $t\in[0,1]$. An orientation can be established within their
joint set $(\boldsymbol{x},\boldsymbol{y})_{\bigtimes}$ simply by ordering
each pair $(x,y)$ by increasing $t$. Four orientations can be established for
linearly dependent intervals:

Perfect ($+$) |  $(\boldsymbol{x},\boldsymbol{y})_{\nearrow}=\\{(x,y):x=\underline{x}+t(\overline{x}-\underline{x}),\ y=\underline{y}+t(\overline{y}-\underline{y}),\ t\in[0,1]\\}$,
---|---
Perfect ($-$) |  $(\boldsymbol{x},\boldsymbol{y})_{\swarrow}=\\{(x,y):x=\overline{x}-t(\overline{x}-\underline{x}),\ y=\overline{y}-t(\overline{y}-\underline{y}),\ t\in[0,1]\\}$,
Opposite ($+$) |  $(\boldsymbol{x},\boldsymbol{y})_{\nwarrow}=\\{(x,y):x=\overline{x}-t(\overline{x}-\underline{x}),\ y=\underline{y}+t(\overline{y}-\underline{y}),\ t\in[0,1]\\}$,
Opposite ($-$) |  $(\boldsymbol{x},\boldsymbol{y})_{\searrow}=\\{(x,y):x=\underline{x}+t(\overline{x}-\underline{x}),\ y=\overline{y}-t(\overline{y}-\underline{y}),\ t\in[0,1]\\}$.

######  Definition 4.6.

(Oriented interval diagonal)
The joint set of two oriented linearly dependent intervals can be given the
interpretation of an _oriented interval diagonal_ , i.e. a convex set with two
ordered vertices. Given Definition 4.5 first and second vertex of an oriented
diagonal can be obtained setting $t=0$ and $t=1$ respectively.

######  Definition 4.7.

(Linear interval dependence)
The joint set $(\boldsymbol{x},\boldsymbol{y})_{\bigtimes}$ of Definition 4.3
expresses linear dependence between intervals, a.k.a. _linear interval
dependence_.

######  Definition 4.8.

(Strong linear interval dependence)
Let $\boldsymbol{x}_{1},\boldsymbol{x}_{2}\in\mathbb{IR}$, and let
$u,v\in\mathbb{R}$. The two intervals $\boldsymbol{x}_{1}$ and
$\boldsymbol{x}_{2}$ are said to have _strong linear interval dependence_ , if
there exists a generator $\boldsymbol{x}\in\mathbb{IR}$, such that:

$(\boldsymbol{x}_{1},\boldsymbol{x}_{2})=(u\boldsymbol{x},v\boldsymbol{x})=\\{(x_{1},x_{2}):x_{1}=ux,\
x_{2}=vx,\ x\in\boldsymbol{x},\ u,v\in\mathbb{R}\\}.$

Because the joint set $(u\boldsymbol{x},v\boldsymbol{x})$ is determined by its
generator $\boldsymbol{x}$, such joint set can be denoted by: $\
{}_{uv}\boldsymbol{x}:=(u\boldsymbol{x},v\boldsymbol{x})$. The vertices of the
diagonal joint set are given by:
$\text{vert}(_{uv}\boldsymbol{x})=\\{(u\underline{x},v\underline{x}),(u\overline{x},v\overline{x})\\}$.

######  Remark 4.9.

Note that because strong linear dependence is a more stringent condition than
linear dependence, any two linearly dependent interval may not satisfy
Definition 4.8.

######  Remark 4.10.

Observe that the orientation of the interval diagonal induced by strong linear
dependence is fully determined by the sign of $u$ and $v$. This holds under
the classical interpretation that the interval $\boldsymbol{x}\in\mathbb{IR}$
is oriented like the real line $\mathbb{R}$. Improper interval analysis and
Kraucher arithmetic have challenged this interpretation [2].

######  Example 4.11.

(Addend of the Fourier series)
The addend of the Fourier series is an example of an oriented interval
diagonal in the complex plane. The Fourier coefficients are
$w_{hn}=u_{hn}+iv_{hn}=u_{n}+iv_{n}$. Let $h=1$, $N=8$, then
$w_{1,0}=e^{0}=1+i0$ with $u_{0}=1,\ v_{0}=0$;
$w_{1,1}=e^{-i\frac{2\pi}{8}}=\cos\frac{\pi}{4}-i\sin\frac{\pi}{4}$, with
$u_{1}=\cos\frac{\pi}{4},\ v_{1}=\sin\frac{\pi}{4}$;
$w_{1,2}=e^{-i\frac{2\pi}{8}2}=\cos\frac{\pi}{2}-i\sin\frac{\pi}{2}$, with
$u_{2}=0,\ v_{2}=1$.

$\boldsymbol{x}_{0}=[-2,0]$$\boldsymbol{x}_{0}\cdot
u_{0}$$+$$\boldsymbol{x}_{1}=[1,3]$$\boldsymbol{x}_{1}\cdot
u_{1}$$+$$\boldsymbol{x}_{2}=[-4,-2]$$\boldsymbol{x}_{2}\cdot u_{2}$$+\ \
...$${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}$$\boldsymbol{x}_{0}\cdot
v_{0}$${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}$$\boldsymbol{x}_{1}\cdot
v_{1}$${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}$$\boldsymbol{x}_{2}\cdot
v_{2}$$-4$$-3$$-2$$-1$$1$$2$$-2$$-1$$1$$2$$3$$4$ReIm+$-4$$-3$$-2$$-1$$1$$2$$-2$$-1$$1$$2$$3$$4$ReIm+$-4$$-3$$-2$$-1$$1$$2$$-2$$-1$$1$$2$$3$$4$ReIm+
…

######  Definition 4.12.

(Minkowski addition)
Let $A,B\in\mathcal{C}$ be any two convex subsets of a real vector space,
where $\mathcal{C}\subseteq\mathbb{R}^{m}$ is such a space of convex subsets.
Then the _Minkowski addition_ is given by:

$A\oplus B=\bigcup_{A,B\in\mathcal{C}}\\{a+b:a\in A,b\in B\\}.$

The following is a well-known result in computational geometry, which leads to
a practical implementation of the Minkowski sum.

######  Proposition 4.13.

The sum of two convex polytopes in the plane:
$A,B\in\mathcal{C}\subseteq\mathbb{R}^{2}$ with $m,n$ vertices, is a convex
polytope with at most $m+n$ vertices.

######  Remark 4.14.

Note that because of Proposition 4.13 the coordinates of the vertices
resulting from the Minkowski addition can be computed in linear time $O(m+n)$.
The intuitive procedure is provided in the form of text in the Wikipedia
article [6].

Here is the extract of the Wikipedia article on December 2021:
For two convex polygons $P$ and $Q$ in the plane with $m$ and $n$ vertices,
their Minkowski sum is a convex polygon with at most $m+n$ vertices and may be
computed in time $O(m+n)$ by a very simple procedure, which may be informally
described as follows. Assume that the edges of a polygon are given and the
direction, say, counterclockwise, along the polygon boundary. Then it is
easily seen that these edges of the convex polygon are ordered by polar angle.
Let us merge the ordered sequences of the directed edges from $P$ and $Q$ into
a single ordered sequence $S$. Imagine that these edges are solid arrows which
can be moved freely while keeping them parallel to their original direction.
Assemble these arrows in the order of the sequence $S$ by attaching the tail
of the next arrow to the head of the previous arrow. It turns out that the
resulting polygonal chain will in fact be a convex polygon which is the
Minkowski sum of $P$ and $Q$.

######  Remark 4.15.

Note that as a consequence of Proposition 4.13, the Minkowski addition is
convexity preserving.

######  Proposition 4.16.

(Minkowski addition and united extensions)
Let $\mathsf{f}:\mathbb{R}^{2}\rightarrow\mathbb{R}$ be the sum function, such
that $\mathsf{f}(x,y)=x+y$, and $\boldsymbol{x},\boldsymbol{y}\in\mathbb{IR}$
be two dependent intervals, whose joint set is convex, such that
$(\boldsymbol{x},\boldsymbol{y})\in\mathcal{C}$. Then, the united extension of
$\mathsf{f}$, $\mathcal{F}_{+}(\boldsymbol{x},\boldsymbol{y})$ is equivalent
to the Minkowski sum, such that:

$\mathcal{F}_{+}(\boldsymbol{x},\boldsymbol{y})\equiv\boldsymbol{x}\oplus\boldsymbol{y},$

thus the united set of $\mathcal{F}_{+}$ can be reached by means of the
Minkowski sum.

###### Proof.

Invoking the Definition 2.7, the united extension of the sum function applied
to an arbitrary set $(\boldsymbol{x},\boldsymbol{y})$ is given by:

$\mathcal{F}_{+}(\boldsymbol{x},\boldsymbol{y})=\bigcup_{\boldsymbol{x}^{\prime},\boldsymbol{y}^{\prime}\in
S(\boldsymbol{x},\boldsymbol{y})}\\{x+y:x\in\boldsymbol{x}^{\prime},\
y\in\boldsymbol{y}^{\prime}\\},$

which is equivalent to Definition 4.12, when $(\boldsymbol{x},\boldsymbol{y})$
is a convex subset of $\mathbb{R}^{2}$. Therefore the Minkowski sum coincides
to evaluating the united extension of the sum function. ∎

######  Corollary 4.17.

The Minkowski sum of two linearly dependent intervals
$\boldsymbol{x},\boldsymbol{y}\in\mathbb{IR}$, whose joint set is:
$(\boldsymbol{x},\boldsymbol{y})=(\boldsymbol{x},\boldsymbol{y})_{\bigtimes}$,
yields the united set under the sum function.

###### Proof.

The proof is identical to the proof of Proposition 4.16, and it holds because
the joint set of two linearly dependent intervals is convex:
$(\boldsymbol{x},\boldsymbol{y})_{\bigtimes}\in\mathcal{C}$. ∎

######  Example 4.18.

(Minkowski addition between two diagonals)
$-5$$-4$$-3$$-2$$-1$$1$$-1$$1$$2$$3$ReIm+$-5$$-4$$-3$$-2$$-1$$1$$-1$$1$$2$$3$ReIm=$-5$$-4$$-3$$-2$$-1$$1$$-1$$1$$2$$3$ReIm

######  Example 4.19.

(Minkowski addition between a convex set and a diagonal)
$-5$$-4$$-3$$-2$$-1$$1$$1$$2$$3$$4$$5$$6$ReIm+$-5$$-4$$-3$$-2$$-1$$1$$1$$2$$3$$4$$5$$6$ReIm=$-5$$-4$$-3$$-2$$-1$$1$$1$$2$$3$$4$$5$$6$ReIm

We are ready to state the main result of this work.

######  Theorem 4.20.

(Main result)
Let $\boldsymbol{x}\in\mathbb{IR}^{N}$ be an n-interval, whose components are
non-interactive (N-box). Let $\mathsf{F}_{h}$ be the discrete Fourier
transform at a given harmonic $h=0,1,...,N-1$, and let $Z_{h}$ be the united
set, obtained applying the united extension $\mathcal{F}_{h}$ on to
$\boldsymbol{x}$. Then, the united set $Z_{h}$ is a convex polytope in
$\mathbb{C}$. Thus, its vertices are computable by a chain of Minkowski
additions.

###### Proof.

Let us expand the Fourier transform and consider its algebraically equivalent
trigonometric expression:

$\mathsf{f}_{h}(x)=\sum_{n=0}^{N-1}x_{n}\
\left(\cos{\frac{2\pi}{N}hn}-{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}\sin{\frac{2\pi}{N}hn}\right).$

With the change of variables:

$u_{hn}=\cos{\frac{2\pi}{N}hn},\ \ \ \ v_{hn}=-\sin{\frac{2\pi}{N}hn},$

the transform becomes:

$\mathsf{f}_{h}(x)=\sum_{n=0}^{N-1}x_{n}u_{hn}+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}\
x_{n}v_{hn}.$ (8)

Let us now consider the interval extension of (8):
$\mathsf{F}_{h}(\boldsymbol{x})=\sum_{n=0}^{N-1}\boldsymbol{x}_{n}u_{hn}+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}\
\boldsymbol{x}_{n}v_{hn}$. Each addend of such extension is the interval
diagonal ${}_{uv}\boldsymbol{x}_{hn}\in\mathbb{C}$, given by:

${}_{uv}\boldsymbol{x}_{hn}:=\boldsymbol{x}_{n}u_{hn}+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i}\
\boldsymbol{x}_{n}v_{hn}.$

Each interval diagonal ${}_{uv}\boldsymbol{x}_{hn},\ n=0,1,...,N-1$ is a
convex polytope in $\mathbb{C}$ with two vertices. Substituting the interval
diagonals ${}_{uv}\boldsymbol{x}_{hn}$ back into expression (8), the interval
extension of the discrete Fourier transform becomes:

$\displaystyle\mathsf{F}_{h}(\boldsymbol{x})$ $\displaystyle=\sum_{n=0}^{N-1}\
{}_{uv}\boldsymbol{x}_{hn}$ $\displaystyle=(\cdots((_{uv}\boldsymbol{x}_{h0}\
+\ _{uv}\boldsymbol{x}_{h1})\ +\ _{uv}\boldsymbol{x}_{h2})\ +...+\
_{uv}\boldsymbol{x}_{h(N-1)}).$

Now, because each interval diagonal is a convex subset of $\mathbb{C}$, we can
replace each addition by its Minkowski equivalent:

$Z_{h}=\mathcal{F}_{h}(\boldsymbol{x})=(\cdots((_{uv}\boldsymbol{x}_{h0}\
\oplus\ _{uv}\boldsymbol{x}_{h1})\ \oplus\ _{uv}\boldsymbol{x}_{h2})\
\oplus...\oplus\ _{uv}\boldsymbol{x}_{h(N-1)}).$ (9)

Because the sum between two diagonals is a convex set, and the sum of a convex
set and a diagonal is again a convex set, by invoking Proposition 4.13, it
holds that the series of nested Minkowski sums of (9) yields the united set
$Z_{h}$, which concludes the proof. ∎

######  Remark 4.21.

Note that the proof of Theorem 4.20 implies that the dependence encoded in the
diagonal is fully preserved, and so the dependency problem of interval
computations is fully addressed. The resulting united set $Z_{h}$ is therefore
a convex polytope in $\mathbb{C}$, whose vertices can be computed by
repeatedly applying the Minkowski sum in (9).

######  Corollary 4.22.

(Number of vertices)
Let $Z_{h}$ be he united set of (9), then $Z_{h}$ is convex and has at most
$2N$ vertices.

###### Proof.

The proof follows from Proposition 4.13, noticing that each sum in (9) is a
Minkowski addition between convex sets. ∎

##  5 Discussion

This paper has set out the mathematical foundations upon which a polynomial-
time algorithm can be built, in order to compute exact bounds on the amplitude
and phase of the discrete Fourier transform, when presented with input
uncertainty in the form of intervals.

The main result states that the united set $Z_{h}\subset\mathbb{C}$ of the
transform can be reached by chaining Minkowski additions. This provides a
means to address the dependency problem of interval computations, whilst
characterising the geometry of the united set. This result also establishes
the convexity of such sets, which in turns makes it possible to obtain exact
bounds on the amplitude and phase.

Note from Definition 2.24 that when the united set at a particular harmonic
contains the origin of the complex plane, the phase for such a harmonic is
undefined.

With a full characterization of the united set it is possible to pinpoint the
configuration of endpoints in the original N-interval that leads to the bounds
for each harmonic. There will be one configuration for the upper bound and one
for the lower bound for each harmonic. This study can help the analysts
identify some ‘critical’ signals within the N-interval that lead to the upper
bound of the amplitude, which can be useful when concerned with the energy
content of the process.

It is important to note that an algorithm for the exact bounds on amplitude
and phase can suffer additional dependency problems if used to perform further
calculations involving the interval amplitude and/or the interval phase.
Therefore, such an algorithm must be used with caution, while understanding
the limitations of interval computations.

Proposition 4.13 induces an algorithm that can compute the vertices of a
Minkowski addition in linear time. This is a very interesting prospect as it
can lead to faster algorithms than the one presented in [1]. In fact, with a
linear-time algorithm for the Minkowski addition, there is no longer need to
compute a convex hull at each addition, bringing significantly down the cost
of the algorithm.

Finally, a short remark about verified computations. In order for the
computations presented in this paper to be verified and exact at the same
time, additional theoretical work is needed. Verified computations will need
to deal with interval Fourier coefficients, whose width is typically orders of
magnitude smaller compared to the width of the input uncertainty. Because of
the difference in magnitude, the exactness of the bounds could be relaxed to
make room for rigour, however, to achieve verified computations a slightly
modified implementation of the algorithm is needed.

## Acknowledgements

Thanks to Tania Gricel Benitez, Ander Gray, Scott Ferson, Marco Behrendt and
Liam Comerford.

This research was funded by the Engineering & Physical Sciences Research
Council (EPSRC) with grant no. EP/R006768/1.

## References

  * [1] Marco De Angelis, Marco Behrendt, Liam Comerford, Yuanjin Zhang, and Michael Beer.  Forward interval propagation through the discrete Fourier transform.  In The 9th international workshop on Reliable Engineering Computing, pages 39–52. 2020.
  * [2] Edgar Kaucher.  Interval analysis in the extended interval space IR.  In Fundamentals of Numerical Computation (Computer-Oriented Numerical Analysis), pages 33–49. Springer, 1980.
  * [3] Ralph Baker Kearfott, Mitsuhiro T Nakao, Arnold Neumaier, Siegfried M Rump, Sergey P Shary, and Pascal Van Hentenryck.  Standardized notation in interval analysis.  In Proc. XIII Baikal International School-seminar “Optimization methods and their applications, volume 4, pages 106–113. Citeseer, 2005.
  * [4] Ramon E Moore.  Interval analysis, volume 4.  Prentice-Hall Englewood Cliffs, 1966.
  * [5] Arnold Neumaier and Arnold Neumaier.  Interval methods for systems of equations.  Number 37. Cambridge university press, 1990.
  * [6] Wikipedia contributors.  Minkowski addition — Wikipedia, the free encyclopedia, 2021.  [Online; accessed 18-December-2021].