# Empirical Studies on Symbolic Aggregation Approximation Under Statistical
Perspectives for Knowledge Discovery in Time Series

Wei Song  School of Information Engineering
Zhengzhou University
<EMAIL_ADDRESS>Zhiguang Wang  Dept.of CS and EE
University of Maryland
Baltimore County
<EMAIL_ADDRESS>Yangdong Ye, Ming Fan  School of Information
Engineering
Zhengzhou University
<EMAIL_ADDRESS>
###### Abstract

Symbolic Aggregation approXimation (SAX) has been the de facto standard
representation methods for knowledge discovery in time series on a number of
tasks and applications. So far, very little work has been done in empirically
investigating the intrinsic properties and statistical mechanics in SAX words.
In this paper, we applied several statistical measurements and proposed a new
statistical measurement, i.e. information embedding cost (IEC) to analyze the
statistical behaviors of the symbolic dynamics. Our experiments on the
benchmark datasets and the clinical signals demonstrate that SAX can always
reduce the complexity while preserving the core information embedded in the
original time series with significant embedding efficiency. Our proposed IEC
score provide a priori to determine if SAX is adequate for specific dataset,
which can be generalized to evaluate other symbolic representations. Our work
provides an analytical framework with several statistical tools to analyze,
evaluate and further improve the symbolic dynamics for knowledge discovery in
time series.

Key Words— SAX; Knowledge Discovery in Time Series; Infomation Embedding Cost;
Permutation Entropy; Symbolic Complexity

††footnotetext: This work is supported by the National Natural Science
Foundation of China (Grant No.61170223), The Education Department of Henan
Province (Grant No.13A520453), Department of Science & Technology of Henan
Province (Grant No.142300410229).

##  I Introduction

Time series is a sequence of data obtained from sequential measurements over
time. Nowadays, time series data is ubiquitous among finance, health care,
multimedia, agriculture and manufacturing, etc. Arising needs on various time
series data mining tasks inspire a number of representation methods to reduce
the volume, smooth the noise or extract the implicit structure for further
data mining tasks. Some numerical approaches inspired by signal processing
techniques are firstly applied. The Discrete Fourier Transformation (DFT)
framework is applied in the seminal work of Agrawal [1] by projecting the time
series into the sine and cosine bases. Discrete Wavelet Transformation (DWT),
which uses the scaled variety of mother wavelet function to give
multiresonlutional decomposition basis to measure both high frequency and low
frequency over large intervals, are intensively applied in the literature over
last decades [2, 3, 4]. Singular Value Decomposition (SVD) and its extensions
have been proposed to find multiscale patterns in the streaming data [5, 6].
Esling and Agon had a good review paper about other numerical representation
methods [7].

Instead of generating a sequence of numerical output, symbolic representations
provide another perspective. Aligned Cluster Analysis (ACA) is introduced as
an unsupervised method to cluster the temporal patterns of human motion data
[8]. It is an extension of kernel k-means clustering but requires quite
computational capacity. Persist is an unsupervised discretization methods to
maximize the persistence measurement of each symbol [9]. Piecewise Aggregation
Approximation (PAA) methods is proposed by Keogh [10] to reduce the
dimensionality of time series, which is then upgraded to Symbolic Aggregation
Approximation (SAX) [11]. In SAX, each aggregation value after PAA process is
mapped into the equiprobable intervals based on standard normal distribution
to produce a sequence of symbolic representations. Sant’Anna et al. compared
the comprehensive performance of above three symbolic approaches [12].

Among the above representation approaches, SAX method has become one of the de
facto standard to discretize time series and is at the core of many effective
classification algorithms. Koegh et al. introduce the new problem of finding
time series discords and apply SAX derivations to find the subsequences of a
longer time series that are maximally different to all the rest of the time
series subsequences [13]. A new SAX-based algorithm is proposed to discover
time series motifs with invariance to uniform scaling. The authors show that
their approach produces objectively superior results in several important
domains [14]. Vector Space Model is combined together with SAX as a novel
method to discover characteristic patterns in a time series [15]. SAX with
bag-of-words are proved to be powerful in several time series classification
tasks [16, 17, 18].

As the golden standard of supervised parametric approach in recent ten more
years, what are the intrinsic statistical behavior of SAX? How can we evaluate
and justify its performance through empirical studies? What can we learn from
SAX to further improve the time series representations? The following
properties/questions primarily motivate our work:

  * •

Data complexity: Time series data are inherently noisy and chaotic.
Symbolization can improve the analysis through the assumption that it
compresses the complexity and generates more concise representations.

  * •

Information loss: The PAA process of SAX reduces the volume but always incurs
the information loss. The ideal results are achieved when the information loss
is superfluous, e.g. noise is abandoned in the analysis of the raw time
series.

  * •

Efficiency of information embedding: While SAX is supposed to smooth the
noise, the following question is natural to ask about, how much useful
information in original signals will be integrated into the symbolic output of
SAX?

  * •

Seasonality and correlation: correlation and seasonality is important property
in time series analysis, e.g. to determine the order of ARIMA model. For
pattern discovery task, explicitly extract the implicit seasonality in time
series helps us to reveal the intrinsic correlations. However, redundant
correlation will affect the representation efficiency.

We empirically studied above four aspects under a statistical perspectives.
Briefly, permutation entropy [19] helps us to reveal the implicit complexity
under the seemingly randomness or chaos. KL divergence [20] measures the
distribution distance between symbolic output and the raw data. The
information reduction/loss is quantified by standard reconstruction
information loss and a new measurement, Information Embedding Cost (IEC) which
is built upon the standard reconstruction information loss and KL divergence
are applied to analyze the information embedding efficiency. We consider
Autocorrelation function (ACF) and partial autocorrelation function (PACF)
[21] as well to deeply understand the seasonality and internal correlation
embedded in the raw data and symbolic outputs. We analyzed above properties
between SAX, PAA and raw data on seven benchmark datasets [22] and the real
world clinical signals. Our proposed analysis framework shows concretely
reasonable conclusions.

##  II background

In this section, we briefly introduce the SAX approach. SAX can be manually
divided into two phases to facilitate our discussion in this paper. First, we
reduce the dimensionality of the input time series by Piecewise Aggregation
Approximation (PAA). Each value is the mean of its corresponding sliding
windows. Then PAA values are mapped to the equiprobable intervals according to
standard normal distribution as alphabet characters. Overall time series trend
will be extracted as a symbolic sequence as SAX words.

The algorithm has three parameters: window length $n$, word number $w$ and
alphabet size $a$. Different parameters lead to different representations of
the time series. Given a normalized time series of length $n$, in the first
step we need to reduce the dimensionality by dividing it into $[n/w]$ non-
overlapping subwindows. Mean values of each sub-window are computed to reduce
volume and smooth (PAA procedure). Then, PAA values are mapped to a
probability density function $\mathcal{N}(0,1)$ to divide the PAA value into
equiprobable segments with the same probabilities. Words starting from $A$ to
$Z$ are assigned to each PAA values corresponding to the segments they fall
in. Fig. 1 shows the PAA and SAX word of ECG signals from the UCR dataset. A
time series of length 96 is partitioned into 5 segments. The means of each
segment are allocated to the equiprobable interval. After discretization by
PAA and symbolization by SAX, we convert the time series into symbolic
sequence $CACBB$.

Figure 1: The piecewise aggregate approximation for the ”ECG” data and the
corresponding SAX words.

##  III methods

###  III-A Permutation Entropy (PE)

Permutation entropy (PE) is a measurement in symbolic dynamics to quantify the
complexity of time series. Given a sequence of time series
$\\{x_{t}\\}_{t=1...T}$, PE considers all the permutation sets $\pi$ of order
length $n$. All the possible orders of $n$ different numbers are denoted as
$S_{n}$. For each $\pi$ in $S_{n}$, we determine the relative frequency of
possible permutation patterns as:

$p(\pi)=\frac{\\#\\{0\leq t\leq
T-n,\\{x_{t+1},x_{t+2},...,x_{t+n}\\}\in\pi\\}}{T-n+1}$ (1)

When the order $n\geq 2$, PE value is defined as

$H(n)=-\sum P(\pi)\log P(\pi)$ (2)

PE value is actually the sum runs over all possible $n!$ permutations in
permutation pool $S_{n}$. It is clear that $0\leq H(n)\leq\log n!$. We use the
normalized PE $\frac{H(n)}{\log n!}$ to scale the PE value into $[0,1]$ to
facilitate our comparison.

PE has two parameters. Permutation order $n$ determines the length of the
sequence, i.e. the size of the permutation pools. Time delay $t$ controls the
time embedding properties between successive points in the symbol sequences.
The optimal $n$ and $t$ are highly dependable on the system when using PE to
determine the optimal embedding parameters [23]. We discuss the comparable
complexity of raw data, PAA values and SAX words instead of finding a group of
optimal parameters to precisely quantify the complexity. To simplify, we set
$t=1-100$ to observe the tendency of PE values by changing the time delay. For
the parameter $n$, we follow the suggestions to constrain $N>5n!$ [24], thus
$n\leq 7$. Values with the same rank number in the regarded sequence generate
a new permutation pattern, e.g., 3, 4, 4, 3, 1 leads to the permutation
pattern 1, 2, 2, 1, 0 [25].

###  III-B Information Embedding Cost (IEC)

####  III-B1 information loss

Discretization always incur information loss. Piecewise averaging by PAA and
SAX will reduce the dimensionality, but also ignore specific low frequency
details in the raw time series. Information loss is estimated by Mean Square
Error (MSE) between original signal and reconstructed symbolic sequences,
which is slightly different from [12]:

$\text{information loss
}(\tilde{T},T)=\frac{\sum(\tilde{t_{i}}-t_{j})^{2}}{n-1},\tilde{t_{i}}\in\tilde{T},t_{j}\in
T$ (3)

$T$ is the original signal and $\tilde{T}$ is the reconstructed signal.
Reconstructed signal was generated by substituting the original samples with
its corresponding PAA values. For SAX, piecewise averaging from normalized
signals are mapped to its corresponding equiprobable intervals for
symbolization. Then the original samples were substituted by its corresponding
SAX words. To facilitate the comparison and analysis, raw time series, PAA
values and SAX words (A-Z correspond to digits 0-25) are scaled to $[0,1]$
(Fig. 2).

Figure 2: Reconstructed signals of SAX word and PAA representation (left) and
MSE over all samples on UCR Coffee dataset.

####  III-B2 KL divergence

A measurement to compare the distance between two different probability
distributions. For distributions $P$ and $Q$ of $k$ points, the non-symmetric
KL divergence is defined as:

$KL(P||Q)=\sum_{i=1}^{k}p_{i}\log\frac{p_{i}}{q_{i}},p_{i}\in P,q_{i}\in Q$
(4)

In information theory, the KL divergence measures the expected number of extra
bits required to code the samples from $P$ when using a code based on $Q$
rather than using the original code based on $P$ itself. In the our
experiments, $P$ is the distribution of quantile bins in the original signals,
the number of bins actually equals to the alphabet size $a$ in SAX/PAA
settings.

Information loss measures the amount of information discarded when coding the
original signal to the symbolic output. KL divergence indicates the distance
between the distribution from encoding outputs to the original signals. We
define IEC score as the ADD-1 ratio of standardized KL divergence and
standardized information loss. IEC measures how much useful information is
discarded when approximating the original signals:

$IEC_{T}(P,Q)=\frac{KL_{T}(P||Q)_{std}}{1+InfoLoss(\tilde{T},T)_{std}}$ (5)

Given time series $T$ in distribution $Q$ and the proposed encoding approach
$\phi$ with distribution $P$, its IEC score demonstrates the number of extra
bits required when encoding output $\tilde{T}$ when one unit information loss
incurs. Note that we do not equally emphasis on KL divergence and information
loss in the IEC framework. The IEC score linearly decreases as KL divergence
falling. However, when information loss increases, IEC score not only
corresponds to the inverse square term
$\frac{-1}{(1+InfoLoss_{(\tilde{T},T)})^{2}}$, but also depends on the value
of KL divergence. This means that IEC score emphasis more on the KL
divergence, or the information embedding accuracy rather than the compression
rate of symbolic representations. Intuitively, this is reasonable because we
need precise representations rather than the symbols that are too concise to
preserve enough information from the original signals.

$IEC=0$ when the encoding approach $\phi$ generates the representations with
the same probability distribution as the original signals. $IEC=1$ if and only
if the deviation measured by KL divergence reaches to the maximum, i.e. no bit
of original signal is compressed by the proposed symbolic representation.
$IEC=0.5$ when KL divergence and information loss are both 1. It is the
baseline when applying IEC score to evaluate the information embedding
efficiency of specific symbolic representation. $IEC=0.5$ means the symbolic
representation will lose one unit information while reduce one unit
complexity. Relatively large information loss and small KL divergence
demonstrate that the encoding method preserves much information while reducing
the information complexity. Thus, the information loss caused by encoding
method with small IEC score is more likely to produce more concise and
accurate representation.

###  III-C (Partial) Autocorrealtion Coefficient Function

For a stationary process $Z={Z_{1},Z_{2},…,Z_{t}}$, the covariance between
$Z_{t}$ and $Z_{t+k}$ is defined as

$\gamma_{k}=cov(Z_{t},Z_{t+k})=E(Z_{t}-\mu)(Z_{t+k}-\mu)$ (6)

The correlation between $Z_{t}$ and $Z_{t+k}$ as:

$\rho_{k}=\frac{\gamma_{k}}{\sqrt{var(Z_{t})}\sqrt{var(Z_{t+k})}}$ (7)

As a function of $k$, $\rho_{k}$ is the Autocorrelation Coefficient Function
(ACF). ACF represents the covariance and correlation between $Z_{t}$ and
$Z_{t+k}$ with the time lag $k$.

If we remove the mutual linear dependency on the intervening variables
$Z_{t+1},Z_{t+2},...,Z_{t+k-1}$, the conditional correlation is described by:

$Corr(Z_{t},Z_{t+k}|Z_{t+1},Z_{t+2},...,Z_{t+k-1})$ (8)

Above equation is Partial Autocorrelation Coefficient Function (PACF).

ACF and PACF are widely applied in time series analysis to identify the order
of the ARIMA model. We focus on the essential property of ACF and PACF, i.e.
the seasonality of time series. Symbolic representation reduces the complexity
of the original signal while running the risk of information loss and
information distortion. Regular patterns such as seasonality extracted from
noisy and chaotic data is important in discovering more reasonable patterns
embedded in the original data, but over-complicated correlation leads to large
information redundancy. The ideal representation removes much of the
superfluous correlation while retaining the main invariant dependencies.

##  IV experiments and analysis

We select 7 benchmark datasets from the UCR Time Series Classification and
Clustering Repository [22]. We also consider the real clinical signals to
validate our results. Our clinical data were collected in University of XXX
School of Medicine. All patient data are anonymous in order to protect
privacy. 556 patients’ ECG and PPG data were collected in 68 to 128 minutes
long with 240 Hz sampling rate. SAX requires three parameters, window length
$n$, word number $w$ and alphabet size $a$. To empirically explore the
intrinsic property of the appropriate SAX representations, we firstly use SAX-
BoP representations with a 1NN classifier to classify the benchmark datasets,
as described in [17]. We extracted the average value of the alphabet size in
the top 10 representations for each dataset. For simplicity, Window length $n$
is the sequence length, word number $w$ and alphabetical size $a$ are the
rounding values of the expectation among the top 10 representations. All the
parameters are shown in Table I.

TABLE I: Optimal SAX parameters on seven benchmark datasets. Dataset | Length n | Rounding w | Rounding a
---|---|---|---
ECG | 96 | 12 | 7
Lighting2 | 637 | 18 | 7
Coffee | 286 | 48 | 7
Adiac | 176 | 25 | 9
Lighting 7 | 319 | 11 | 9
Beef | 470 | 11 | 5
Oliveoil | 570 | 26 | 7

###  IV-A Complexity

Figure 3: Permutation entropy on (a) raw UCR time series, permutation order
$n=[2,7]$, $t$ is up to $\frac{1}{3}$ of the length (up left),(b) SAX words
from UCR time series, permutation order $n=[2,7]$, $t=[1,10]$ (up right), (c)
clinical signals (bottom left), (d) SAX words on clinical signals (bottom
right).

To study the representational complexity of SAX, we consider the normalized
permutation entropy on the benchmark datasets. For the clarification and the
sake of space, we show the graph upon one datasets. However, our analysis are
more general on all the datasets. In Table 3 (1), it is clear that a linear
rise of the PE value incurs for the increasing $t$. It demonstrates the
complexity of the unfolding trajectory is also increased. The correlation
between the values in the embedding vector $t\times(n-1)$ is getting lost.
This observation is named ’redundancy effect’ by DeMicco et. al [26]. High
correlation leads to less need of visiting the phase of the data during the
reconstruction of the trajectory. The increasing PE value shows the data is
correlated within the embedding vector of $t\times(n-1)$. The embedding vector
is too small for the original data to summarize the full information among the
potentially successive values in the time series that fall into the embedding
vectors. The correlation, or the embedded information between the original
time series is loose with much more noise and redundant irrelevance. This
assumption is clearly supported by the observation, that along within the
embedding vector $t\times(n-1)$, the PE value is increasing linearly without
convergence in Figure 3 (a). Relatively high internal correlation leads to
information redundancy in high dimensionality of time series and enhances the
curse of dimensionality [27].

After symbolization by SAX, the redundancy effect is significantly alleviated
(Figure 3 (b)). However, this may be caused by two possible reasons. Note that
the symbolic sequence is shorter in length, one reason is that the number of
permutation patterns is limited as $t$ increases. Another potential reason is
that SAX word not only decreases the dimensionality, it also makes the
correlation more ’compact’. Instead of the data with very loose correlations,
the SAX words does not experience in heavy redundancy effect when it reaches
to its convergence or starts to diffuse.

Moreover, the magnitude of the PE values demonstrates the absolute complexity.
Compare (a) and (b) in Figure 3 (and on all datasets), the magnitude of the PE
values overlap between raw and SAX However, in the benchmark dataset, the time
series is not very noisy and the information is compact. We compared the PE
values between the raw clinical data and its corresponding SAX words (Figure 3
(c) and (d)), SAX words clearly has lower PE magnitude than the raw data .
Thus, SAX practically reduces the redundancy effect and the absolute
complexity.

###  IV-B Information Embedding Efficiency

Figure 4: Information loss and KL divergence on (a) ’Coffee’ dataset (up), (b)
’ECG’ dataset (bottom). X-axis denotes the sample index, Y-axis is the
corresponding measurement.

As the size of SAX representation sometimes exerts subtle influence on the
analysis based on PE, explore other ways to study the information embedding
efficiency is necessary.

SAX steps further than PAA by mapping the PAA values to the corresponding
words according to the standard Gaussian distribution. If SAX can encode more
information in the SAX words while incurs less information loss, we suppose to
study if this advantage benefits from PAA process or Gaussian mapping process.
However, neither KL divergence nor information loss are capable to analyze the
non-linear dependencies among different dataset, but run into a case-by-case
manner. On some datasets, it is easy to discriminate the benefit from the SAX
words over the PAA output (Figure 4a). However, the relative relationship
might be ambiguous neither (Figure 4b). If a representation has small KL
divergence with superior information loss, it will maintain more substantial
information while discarding much of the noise. Thus, to compare the
information embedding efficiency among different symbolic approaches, we
propose the newly IEC score to measure how much information is discarded when
compress the original signals. We take the average of IEC scores among all
samples in each dataset and compare the classification performance of SAX [17]
and original time series [22] using a 1NN classifier (Table II). We expect
that the representations with lower IEC score achieve lower classification
error rates.

TABLE II: The IEC scores on the SAX/PAA representations and the classification error rates on SAX words and the original data. Dataset | SAX IEC | PAA IEC | Error Rate | Error Rate
---|---|---|---|---
|  |  | on SAX | on Raw Data
lighting2 | 0.444 | 0.179 | 0.229 | 0.197
ECG | 0.259 | 0.305 | 0.22 | 0.11
coffee | 0.126 | 0.242 | 0.107 | 0.25
adiac | 0.096 | 0.089 | 0.383 | 0.407
lighting7 | 0.496 | 0.065 | 0.397 | 0.37
beef | 0.416 | 0.407 | 0.466 | 0.4
oliveoil | 0.119 | 0.883 | 0.166 | 0.233
clinical ECG | 0.192 | 0.611 | 0.173 | 0.545

Table II demonstrates that SAX words always has lower IEC scores than the PAA
values. The Gaussian mapping procedure actually improves the representational
capability by getting rid of much noise while maintaining the output symbols
“nearer” to the original signals. Another observation is that, when SAX words
has higher IEC score on some datasets (e.g. ’lighting2’ and ’lighting7’), the
classification performance on SAX words are always worse than classifying the
raw data. Actually, we suppose that the classification performance on PAA
values will overtake SAX on the ’lighting2’ and ’lighting7’ datasets, because
PAA values obviously has lower IEC scores than SAX words on these two
datasets. On the clinical ECG dataset, the KL divergence, reconstruction
information loss and IEC score of SAX words and PAA outputs clearly justify
our assumptions. We rank above three measurements in ascending order (Figure
5). Although its hard to judge the performance through the graph of KL
divergence and information loss, obviously the SAX words has lower average IEC
score over all samples (0.1919) than PAA output(0.6105). The low IEC score on
SAX words also explains its superior performance on classification comparing
with the raw data (Table II).

Figure 5: The KL divergence, reconstruction information loss and IEC scores of
the SAX words and PAA output on the clinical ECG data.

To deeply understand the non-linear correlation encoded between the IEC scores
and the representational capability for time series data mining (i.e.
classification performance), we applied the high-order regression model. Our
assumption is that, the IEC score helps us to find out if one symbolic
representation outperform raw data on specific dataset. We suppose that, the
improvement on classification error rate of the SAX words over the original
signal, defined as $\frac{ERR_{SAX}}{ERR_{raw}}$, are correlated to their
corresponding IEC scores. By the quadratic regression, we found the error
ratio and the IEC scores are highly correlated with the a R-square 0.9265
(Table. 3). Thus, we suggest that when the IEC score on the symbolic
representation is lower than 0.2 with some specific tolerance, it is more
likely to overtake the original signals in the data mining tasks such as
classification or retrieval.

TABLE III: Regression statistics of the classification error ratio and the IEC scores on seven benchmark datasets and one real-world clinical dataset. Independent variable $x$ is the IEC score, dependent variable $y$ is the error ratio. Regression Statistics |
---|---
Multiple $R$ | 0.962576
$R$ Square | 0.926553
Intercept | 0
$x$ | 9.454057
$x^{2}$ | -14.9802

###  IV-C Internal Correlation/Seasonality

Figure 6:  (a) The ACF/PACF plots of raw data, SAX words and PAA output on the
benchmark ’ECG’ dataset. SAX words and PAA output both preserve the
correlation while compressing the original signals. The absolute mean of ACF
value over all samples is 0.35 on the raw signals, 0.23 on the SAX words and
0.21 on PAA values (left), (b) The ACF/PACF plots on the clinical dataset
(right).

The internal correlation indicates if the representation can preserve the
significant seasonal patterns with strong correlation in the data while
removing much of the redundant correlations. A good representation should
smooth the noise, reduce the volume and simultaneously extract the main
patterns. We apply ACF and PACF to evaluate the ability to capture intrinsic
correlation embedded in time series on SAX words and PAA output. In our
experiments, both PAA and SAX can extract the correlation tendency in the
original signals, because the ACF/PACF plots have the same shape on both PAA
output and SAX words (Figure 6). The maximum peak value in ACF measures the
periodicity in a sequence of signals [12]. Thus, we look into the absolute
mean among the ACF values and take the average over all samples in each
dataset (Table IV). SAX words actually always have the higher absolute mean
ACF than PAA output, thus preserve more internal correlations than PAA output.

We also explored the morphology of the internal correlation embedded in time
series by the SAX words and PAA output on the real-world clinical dataset
(Figure 6b). Both SAX words and PAA output have the similar scheme of ACF to
preserve the internal correlation. The PACF behaves quite interestingly. The
average ACF value of the original signals, SAX words and PAA output are 0.587,
0.556 and 0.360. SAX and PAA both decrease the correlation redundancy to
generate more compact representations. The smoothness of the redundancy effect
by SAX words also interpret the benefit that SAX compresses the internal
correlation.

While the ACF indicates both SAX and PAA will extract the internal
correlation, the PACF demonstrates these two methods do not follow the same
routines, but have different recurrent relations. In time series analysis, we
decide the order of auto-regressive (AR) process from the significance beyond
the time lags, because those insignificant coefficients do not exhibit any
patterns. Although it is clear that test time series are not a stationary
process and most of them have the seasonal trend, the PACF shows complex
behavior on SAX words and PAA values. Interestingly, the peak value of PACF on
SAX words and PAA output sometimes has the different sign, which means the
correlation orientations are opposite after the Gaussian mapping procedure.

TABLE IV: The absolute mean value of the ACF on raw data, SAX words and PAA output. Dataset | RAW | SAX | PAA
---|---|---|---
lighting2 | 0.3502 | 0.2336 | 0.2112
ECG200 | 0.1981 | 0.2907 | 0.2787
Coffee | 0.4723 | 0.3237 | 0.3227
Adiac | 0.4656 | 0.3237 | 0.3227
lighting7 | 0.2455 | 0.2868 | 0.2704
Beef | 0.4040 | 0.2722 | 0.2599
Oliveoil | 0.3226 | 0.1763 | 0.1680
Clinical ECG | 0.6331 | 0.5563 | 0.3605

##  V Conclusion

To the best of our knowledge, this paper is the first attempt to explore the
intrinsic statistical properties of Symbolic Aggregation Approximation. We
empirically investigates the intrinsic properties of Symbolic Aggregation
approXimation method in the statistical perspective. We explain the
statistical behavior of SAX words via three aspects, the complexity, the
information embedding efficiency and the internal correlation. We also
proposed a new measurement, Information Embedding Cost (IEC) to evaluate the
information embedding efficiency of the symbolic dynamics. We proved that high
correlation lies between the IEC score and the classification performance.

The logic map is clear. Lower absolute permutation entropy implies that SAX
words significantly reduce the complexity of the original time series. This
observation motivates us to investigate how much information will the symbolic
representations retain and discard after processing by the SAX. We develop a
novel measurement, IEC score based on KL divergence and reconstruction
information loss to evaluate the information embedding efficiency. Our
experiments indicate that SAX shows significant improvement than PAA with
lower IEC score. We recommend the criterion of IEC score to be 0.2 when
considering if the SAX representations work better or not. If test
representation has lower IEC score than 0.2, it is much likely that SAX will
improve the classification performance compared with original signals. Such
analysis on IEC score can also be generalized to other symbolic
representations such as ACA, Persist or some newly proposed representation
methods.

Redundancy effect incurs in the analysis on permutation entropy. This
observation motivate us to investigate how SAX behaves on the internal
correlation embedded in the original time series. Our experiments demonstrate
that the internal correlation which is measured by ACF is preserved by both
SAX and PAA precisely and concisely. However, moving average (MA) model will
not fit the output signal well, because the ACF indicates seasonal properties
before differencing. The same trends preserved by the ACF and lower average
ACF values imply that PAA-based discretization reduce the redundant internal
correlation and maintain major correlations. SAX words always have slightly
higher average ACF value than PAA, thus maintain the better internal
correlations. The PACF behavior are quite different within SAX and PAA, which
implies that Gaussian mapping procedure greatly changes the conditional
correlation among original data. This observation is interesting. We will try
to reveal the symbolic mechanics of this observation in the future work.

Our work can support the SAX method and its further applications, provide the
analytical framework and statistical tools to evaluate symbolic
representations methods, and inspire the researcher to design new symbolic
dynamics for time series data mining tasks.

## References

  * [1] R. Agrawal, C. Faloutsos, and A. Swami, _Efficient similarity search in sequence databases_. Springer, 1993.
  * [2] A. Grinsted, J. C. Moore, and S. Jevrejeva, “Application of the cross wavelet transform and wavelet coherence to geophysical time series,” _Nonlinear processes in geophysics_ , vol. 11, no. 5/6, pp. 561–566, 2004.
  * [3] K. Lau and H. Weng, “Climate signal detection using wavelet transform: How to make a time series sing,” _Bulletin of the American Meteorological Society_ , vol. 76, no. 12, pp. 2391–2402, 1995.
  * [4] P. C. Ivanov, M. G. Rosenblum, C. Peng, J. Mietus, S. Havlin, H. Stanley, and A. L. Goldberger, “Scaling behaviour of heartbeat intervals obtained by wavelet-based time-series analysis,” _Nature_ , vol. 383, no. 6598, pp. 323–327, 1996.
  * [5] F. Korn, H. V. Jagadish, and C. Faloutsos, “Efficiently supporting ad hoc queries in large datasets of time sequences,” _ACM SIGMOD Record_ , vol. 26, no. 2, pp. 289–300, 1997.
  * [6] K. Ravi Kanth, D. Agrawal, and A. Singh, “Dimensionality reduction for similarity searching in dynamic databases,” in _ACM SIGMOD Record_ , vol. 27, no. 2. ACM, 1998, pp. 166–176.
  * [7] P. Esling and C. Agon, “Time-series data mining,” _ACM Computing Surveys (CSUR)_ , vol. 45, no. 1, p. 12, 2012.
  * [8] F. Zhou, F. Torre, and J. K. Hodgins, “Aligned cluster analysis for temporal segmentation of human motion,” in _Automatic Face & Gesture Recognition, 2008. 8th IEEE International Conference on_. IEEE, 2008, pp. 1–7.
  * [9] F. Mörchen and A. Ultsch, “Finding persisting states for knowledge discovery in time series,” in _From Data and Information Analysis to Knowledge Engineering_. Springer, 2006, pp. 278–285.
  * [10] E. Keogh, K. Chakrabarti, M. Pazzani, and S. Mehrotra, “Dimensionality reduction for fast similarity search in large time series databases,” _Knowledge and information Systems_ , vol. 3, no. 3, pp. 263–286, 2001.
  * [11] J. Lin, E. Keogh, S. Lonardi, and B. Chiu, “A symbolic representation of time series, with implications for streaming algorithms,” in _Proceedings of the 8th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery_. ACM, 2003, pp. 2–11.
  * [12] A. Sant’Anna and N. Wickstrom, “Symbolization of time-series: An evaluation of sax, persist, and aca,” in _Image and Signal Processing (CISP), 2011 4th International Congress on_ , vol. 4. IEEE, 2011, pp. 2223–2228.
  * [13] E. Keogh, J. Lin, and A. Fu, “Hot sax: Efficiently finding the most unusual time series subsequence,” in _Data mining, fifth IEEE international conference on_. IEEE, 2005, pp. 8–pp.
  * [14] D. Yankov, E. Keogh, J. Medina, B. Chiu, and V. Zordan, “Detecting time series motifs under uniform scaling,” in _Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining_. ACM, 2007, pp. 844–853.
  * [15] P. Senin and S. Malinchik, “Sax-vsm: Interpretable time series classification using sax and vector space model,” in _Data Mining (ICDM), 2013 IEEE 13th International Conference on_. IEEE, 2013, pp. 1175–1180.
  * [16] T. Oates, C. F. Mackenzie, L. G. Stansbury, B. Aarabi, D. M. Stein, and P. F. Hu, “Predicting patient outcomes from a few hours of high resolution vital signs data,” in _Machine Learning and Applications (ICMLA), 2012 11th International Conference on_ , vol. 2. IEEE, 2012, pp. 192–197.
  * [17] T. Oates, C. F. Mackenzie, D. M. Stein, L. G. Stansbury, J. Dubose, B. Aarabi, and P. F. Hu, “Exploiting representational diversity for time series classification,” in _Machine Learning and Applications (ICMLA), 2012 11th International Conference on_ , vol. 2. IEEE, 2012, pp. 538–544.
  * [18] Z. Wang and T. Oates, “Time warping symbolic aggregation approximation with bag-of-patterns representation for time series classification,” in _Machine Learning and Applications (ICMLA), 2014 13th International Conference on_. IEEE, 2014, pp. 270–275.
  * [19] C. Bandt and B. Pompe, “Permutation entropy: a natural complexity measure for time series,” _Physical review letters_ , vol. 88, no. 17, p. 174102, 2002\.
  * [20] S. Kullback and R. A. Leibler, “On information and sufficiency,” _The annals of mathematical statistics_ , pp. 79–86, 1951.
  * [21] W. W.-S. Wei, _Time series analysis_. Addison-Wesley publ, 1994.
  * [22] E. Keogh, X. Xi, L. Wei, and C. A. Ratanamahatana, “The ucr time series classification/clustering homepage,” _URL= http://www. cs. ucr. edu/~ eamonn/time_series_data_ , 2006.
  * [23] M. Riedl, A. Müller, and N. Wessel, “Practical considerations of permutation entropy,” _The European Physical Journal Special Topics_ , vol. 222, no. 2, pp. 249–262, 2013.
  * [24] J. Amigó, S. Zambrano, and M. A. Sanjuán, “Combinatorial detection of determinism in noisy time series,” _EPL (Europhysics Letters)_ , vol. 83, no. 6, p. 60005, 2008.
  * [25] C. Bian, C. Qin, Q. D. Ma, and Q. Shen, “Modified permutation-entropy analysis of heartbeat dynamics,” _Physical Review E_ , vol. 85, no. 2, p. 021906, 2012\.
  * [26] L. De Micco, J. G. Fernández, H. A. Larrondo, A. Plastino, and O. A. Rosso, “Sampling period, statistical complexity, and chaotic attractors,” _Physica A: Statistical Mechanics and its Applications_ , vol. 391, no. 8, pp. 2564–2575, 2012.
  * [27] R. Bellman, R. E. Bellman, R. E. Bellman, and R. E. Bellman, _Adaptive control processes: a guided tour_. Princeton university press Princeton, 1961, vol. 4.


# Applications and Issues in Abstract Convexity

R. Díaz Millán1, Nadezda Sukhorukova2,∗, Julien Ugon1

(Date: January 2022)

1Faculty of Science, Engineering and Built Environment , Deakin University,
Australia
2Department of Mathematics, Swinburne University of Technology, Australia

Abstract. The theory of abstract convexity, also known as convexity without
linearity, is an extension of the classical convex analysis. There are a
number of remarkable results, mostly concerning duality, and some numerical
methods, however, this area has not found many practical applications yet. In
this paper we study the application of abstract convexity to function
approximation. Another important research direction addressed in this paper is
the connection with the so-called axiomatic convexity.

Keywords. Abstract convexity, axiomatic convexity, Chebyshev approximation,
Carathéodory number, quasiaffine functions.

2010 Mathematics Subject Classification. 90C26,90C90, 90C47, 65D15.

††footnotetext:  ∗Corresponding author. E-mail addresses:
<EMAIL_ADDRESS>(R. Díaz Millán<EMAIL_ADDRESS>(N.
Sukhorukova<EMAIL_ADDRESS>(Julien Ugon). Received ; Accepted .

##  1\. Introduction

Abstract convexity appears as a natural extension of the classical convex
analysis when linear and affine functions (elementary functions) are
“replaced” by other types of functions. This is why abstract convexity is also
known as “convexity without linearity”.

It was demonstrated that many results from the classical convex analysis:
conjugation, duality, subdifferential related issues can be extended to “non-
linear” settings [25, 31]. In [25] the authors provide a very detailed
historical review of the theory and it turned out that the origins of this
environment comes back to early 70s, while some specific issues were already
in place in the 50s of the twentieth century.

Despite a very productive work done in the development of abstract convexity,
there are still several direction for improvements. From the onset of abstract
convex theory, much effort has been devoted to study duality, leading to very
elegant generalisations of classical convexity results. On the other hand, the
geometric aspects of convexity have not received as much attention.
Additionally, the theory remains “abstract” and needs practical applications.
One of the goals of this paper is to provide some applications and develop a
framework on the properties that the elementary functions have to satisfy to
be efficient in applications.

There are a number of difficulties to develop efficient computational methods.
The first step is to choose the set of elementary functions. This set should
be simple enough to construct fast and efficient methods. On another hand,
this set has to generate accurate approximations to the functions from the
applications. In some cases, the choice of elementary functions is reasonably
straightforward (see section 3), but this is rather exceptional and in most
applications the choice of a suitable class of elementary functions is a
difficult task.

A deep and detailed study on abstract convexity and related issues can be
found in [31] and also in [29]. A detailed survey of methods of abstract
convex programming can be found in [2]. Many more contributions and
developments and results on duality and methods are not mentioned in this
paper, but the most recent state of the developments in abstract convexity and
a comprehensive literature review can be found in [6].

The paper is organised as follows. In section 2 we provide the essential
background of abstract convexity and axiomatic convexity. In the same section,
we underline connections and possible cross-feeding between these two types of
convexity. Then, in section 3 we illustrate how abstract convexity and
axiomatic convexity can be applied to function approximation. Section 4
illustrates the results of numerical experiments. Finally, section 5 provides
conclusions and future research directions.

##  2\. Abstract Convexity

###  2.1. Definitions and preliminaries

Consider the set of all real-valued functions acting on the domain $X$,
denoted by $\mathscr{F}$ and defined by $\mathscr{F}:=\\{f:X\to\mathds{R}\\}$.
We called the set of _abstract linear functions_ to any subset of functions
$L\subseteq\mathscr{F}$. Following, we introduce some known definitions to
state the abstract convexity concept. Suppose that we defined the set of
abstract linear functions $L\subseteq\mathscr{F}$.

######  Definition 2.1.

The vertical closure of $L$, $H:=\\{l+c:l\in L,c\in\mathds{R}\\}$ is the set
of _abstract affine functions_.

######  Definition 2.2 (Abstract Convexity [29]).

A function $f$ is said to be _$L$ -convex_ if there exists a set $U\subset H$
such that for any $x\in X$, $f(x)=\sup_{u\in U}u(x)$. Such functions are also
called _abstract convex with respect to $L$_.

In this paper we denote the set of all $L$-convex functions by
$\mathscr{F}_{L}$.

######  Definition 2.3 (Support Set [29]).

The _$L$ -support set_ of a function $f\in F$ is defined as:
$\mathop{\mathrm{missing}}{supp}_{L}f:=\\{l\in L:l\leq f\\},$ where $l\leq f$
means that $l(x)\leq f(x),\forall x\in X$. The support sets of $L$-convex
functions are called _$L$ -convex sets_.

Therefore, informally, convexity without linearity simply means that the
“role” of linear functions of the classical convex analysis is held by
functions from a certain class. The first (and for some applications this is
the most important) question is how to choose the set of elementary function.

The next definition, which will be detailed and used in the next subsection,
“helps” the chosen of a “better” set of abstract linear functions.

######  Definition 2.4 (Supremal generator [14, 29]).

Let $\mathscr{F}$ be a set of functions defined on a set $X$. A set
$L\subset\mathscr{F}$ is called a _supremal generator_ of $\mathscr{F}$ if
each $f\in\mathscr{F}$ is abstract convex with respect to $L$.

###  2.2. Quasiconvexity

The notion of quasiconvexity plays an essential role in abstract convexity. We
are now going to explain why.

The notion of quasiconvexity was originally introduced in [11], where the
author studied the behaviour of functions with convex sublevel sets, but the
term quasiconvexity was introduced much later.

######  Definition 2.5.

Let $D$ be a convex subset of $\mathds{R}^{n}$. A function $f:D\to\mathds{R}$
is _quasiconvex_ if and only if its sublevel set

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

is convex for any $\alpha\in\mathbb{R}$.

There are several equivalent definitions of quasiconvex functions, but the one
we use is convenient for our study.

######  Definition 2.6.

A function $f:D\to\mathds{R}$, where $D$ is a convex subset of
$\mathds{R}^{n}$, is called quasiconcave if $-f$ is quasiconvex.

######  Definition 2.7.

Functions that are both quasiconvex and quasiconcave are called quasiaffine
(quasilinear).

Note the following important observations.

  * •

Quasiconvex functions do not need to be continuous.

  * •

In the case of univariate functions, quasiaffine functions are monotone
functions.

If a function is quasiaffine on $\mathds{R}^{n}$ (unconstrained problems)
then, from the definition, that its level sets must be half-spaces, and it is
clear that the hyperplanes defining these half-spaces need to be parallel. In
the presence of constraints, this observation is not valid and we provide an
example in section 4.

There are many studies dedicated to quasiconvex functions and quasiconvex
optimisation [5, 9, 10, 14, 29, 30]. In these studies, the notion of
quasiconvexity appears as one of the possible generalisations of convexity.

###  2.3. Quasiconvex functions and supremal generators

Theorem 7.13 from [14] states the following.

######  Theorem 2.8.

The set of all lower semicontinuous quasiaffine functions forms a supremal
generator of the set of all lower semicontinuous quasiconvex functions.

Essentially, this theorem states that in the case of quasiconvex minimisation
problems, quasiaffine functions “replace” the role of linear functions in
classical convex settings. Therefore, the choice of elementary functions is
clear (all quasiaffine functions).

One main advantage is that the sublevel sets of “new” elementary functions are
half-spaces (similar to classical convex analysis). In most practical
problems, there are some specific characteristics for the quasiaffine
approximations (for example, the class of rational or generalised rational
approximations, approximations that are compositions of certain monotone or
non-decreasing function with certain affine or quasiaffine functions, etc.).
This additional information helps dealing with some specific applications.

In the rest of this section, we clarify the “roles” of quasiaffine functions
in the new abstract convex settings. Then section 4 contains the results of
computational experiments and illustrations.

###  2.4. Relation to Axiomatic Convexity

_Axiomatic Convexity_ aims at generalising the notion of convexity using only
set-theoretic definitions. Good reviews can be found in [32, 33]. Given a set
$X$, a family $\mathcal{C}$ of subsets of $X$ is called a _convexity_ if it
follows the following axioms:

  1. (1)

$\emptyset$ and $V$ belong to $\mathcal{C}$;

  2. (2)

Any arbitrary intersection of sets from $\mathcal{C}$ is in $\mathcal{C}$: if
$D\subset\mathcal{C}$,

$\bigcap_{A\in D}A\in\mathcal{C}$

  3. (3)

The nested union of sets from $\mathcal{C}$ is in $\mathcal{C}$: given an a
family of sets $D\subset\mathcal{C}$ that is totally ordered by inclusion then

$\bigcup_{A\in D}A\in\mathcal{C}.$

The pair $(X,\mathcal{C})$ is called a _convex structure_ (or _(abstract)
convex space_).

These axioms (in particular axioms 1 and 2) ensure the existence of the convex
hull of any set $S\subset X$, namely the smallest convex set containing $S$:

$\mathrm{co}_{\mathcal{C}}S=\bigcap\\{A\in\mathcal{C}:S\subset A\\}.$

If $F$ is finite, then $\mathrm{co}_{\mathcal{C}}F$ is called a _polyhedron_.

Axiomatic Convexity, also called _abstract convexity_ by van de Vel [33], has
found applications in combinatorial geometry [13, 18], among others. A family
$\mathcal{C}$ that satisfies the first two axioms above is called a _closure
space_ , or $\cap$-stable [15].

There are clear connections between abstract convexity as defined by
Definition 2.3 and axiomatic convexity. Indeed, the notion of abstract convex
function (Definition 2.2) first appeared in [15] in the context of closure
spaces. The families of sets considered in [15] were the closure of the set of
sublevel sets of a given family of functions.

Abstract convex functions (Definition 2.2) and Abstract convex sets
(Definition 2.3) were then formally introduced by Kutateladze and Rubinov
[17], who showed the equivalence between these sets and the ones considered by
Fan [15]. Below we formalise some results on the correspondence between
abstract convex sets and closure spaces. Let us start with noting that the
support set of any (not necessarily $L$-convex) function is $L$-convex.
Indeed, the support set of $f$ is also the support set of its $L$-convex
envelope, which is convex.

######  Proposition 2.9.

Consider a family of functions $L$. Then, the set of $L$-convex sets form a
closure space. Furthermore, every closure space is isomorphic to such a set.

###### Proof.

Consider a family of functions $L$ and let $\mathcal{C}$ be the set of
$L$-convex sets. We first show that $L$ is closed with respect to inclusion.
Indeed, let $D\subset\mathcal{C}$ be an arbitrary set of $L$-convex sets. For
each $A\in D$, let $f_{A}(x)=\sup_{l\in A}l(x)$ and consider the function
$f(x)=\inf_{A\in D}f_{A}(x)$. We will show that $\cap_{A\in
D}A=\mathop{\mathrm{missing}}{supp}f$, which implies that $\cap_{A\in D}A$ is
$L$-convex (note that $\mathop{\mathrm{missing}}{supp}f$ is the support set of
the lower convex envelope of $f$).

$\displaystyle\mathop{\mathrm{missing}}{supp}f$ $\displaystyle=\\{l\in
L:l(x)\leq\inf_{A\in D}f_{A}(x)\forall x\in X\\}$ $\displaystyle=\\{l\in
L:l(x)\leq f_{A}(x)\forall A\in D,x\in X\\}$ $\displaystyle=\cap_{A\in
D}\\{l\in L:l(x)\leq f_{A}(x),\forall x\in X\\}=\cap_{A\in D}A.$

The first axiom is clearly verified by $\mathcal{C}$ from the fact that
$\emptyset$ is the support set of $\sup_{l\in\emptyset}l$ and $L$ is the
support set of $\sup_{l\in L}l$.

The second part of the statement is obtained by considering the set $L$ of
indicator functions of the sets in the closure space. More precisely, let
$\mathcal{C}$ be a closure space, and consider the set
$L=\\{i_{A}:A\in\mathcal{C}\\}$ where

$i_{A}(x)=\begin{cases}0&\text{if }x\in A\\\
+\infty&\text{otherwise}\end{cases}$

Then, $L$ is also the set of $L$-convex functions. Indeed, let
$D\subset\mathcal{C}$. Define $U=\\{i_{A}:A\in D\\}\subset L$ and
$f=\sup_{l\in U}l=\sup_{A\in D}i_{A}$. Then $f(x)=0$ if and only if $x\in A$
for all $A\in D$. That is, $f=i_{\cap_{A\in D}A}$. The isomorphism between the
set of support sets of functions from $L$ and $\mathcal{C}$ is evident. ∎

Note that in practice it is not necessary to consider the entire set of
indicator functions, but only the set of indicator functions of a _basis_ of
$\mathcal{C}$ (i.e., a set of functions whose closure is $\mathcal{C}$), which
corresponds to a suppremal generator of the corresponding abstract functions.
It can also easily be seen that the set of domains of the $L$-abstract
functions defined as in the above proof, as well as the set of 0-sublevel
sets, is precisely $\mathcal{C}$.

On the other hand, not all families of abstract convex sets are a convexity
structure.

######  Example 2.10.

Let $L$ be the set of linear functions on $\mathds{R}$, and consider the
functions $f_{\alpha}$ defined by $f_{\alpha}(x)=\alpha\lvert x\rvert$, for
$\alpha>0$. These functions are $L$-convex, and induce a nested sequence of
$L$-convex sets
$S_{\alpha}=\mathop{\mathrm{missing}}{supp}_{L}f_{\alpha}=\\{x\to\beta
x:\beta\in[-\alpha,\alpha]\\}$.

However,

$U=\bigcup_{\alpha<1}S_{\alpha}=\\{x\to\beta x:\beta\in(-1,1)\\}$

is not a $L$-convex set. Indeed, $f_{1}=\sup_{l\in U}l$ is the smallest
$L$-convex function whose support set contains $U$, but the function $x\to
x\in\mathop{\mathrm{missing}}{supp}f_{1}\setminus U$, which shows that $U$
cannot be the support set of $f_{1}$ and therefore of any $L$-convex function.
This shows that the set of $L$-convex sets is not a convex structure.

Let us introduce the notion of strict support set, which will enable us to
address this issue.

The $L$-strict support set of a function $f$ is defined as:

$\mathop{\mathrm{\underline{supp}}}f=\\{l\in L:l(x)<f(x),\forall
x\in\mathop{\mathrm{missing}}{dom}(f)\\}.$

We define the family of sets $\mathcal{C}_{L}$ as follows:

######  Definition 2.11 (convexity extension).

$\displaystyle\mathcal{C}_{L}^{f}$ $\displaystyle:=\\{A\in
L:\mathop{\mathrm{\underline{supp}}}f\subseteq
A\subseteq\mathop{\mathrm{missing}}{supp}f\\}$ $\displaystyle\mathcal{C}_{L}$
$\displaystyle:=\bigcup_{f\in L}\mathcal{C}_{L}^{f}.$

We call the set $\mathcal{C}_{L}$ the _convexity extension_ of the set of
support sets of $L$-convex functions.

######  Proposition 2.12.

For any family of functions $L$, the convexity extension of $L$,
$\mathcal{C}_{L}$, forms a convexity structure.

###### Proof.

Since $\mathcal{C}_{L}$ contains all $L$-convex sets, it contains a closure
space and therefore by Proposition 2.9, it contains the sets $\emptyset$ and
$X$.

To see why the second axiom is satisfied consider an arbitrary family of sets
$D\subset\mathcal{C}_{L}$. For each $A\in D$, there exists a $L$-function
$f_{A}$ such that $\mathop{\mathrm{\underline{supp}}}f_{A}\subseteq
A\subseteq\mathop{\mathrm{missing}}{supp}f_{A}$. Define
$f=\mathrm{co}_{L}\inf_{A\in D}f_{A}$. Since
$A\subseteq\mathop{\mathrm{missing}}{supp}f_{A}$ for any $A$, we have that

$\bigcap_{A\in D}A\subset\bigcap_{A\in
D}\mathop{\mathrm{missing}}{supp}f_{A}=\mathop{\mathrm{missing}}{supp}f,$

where the last equality was shown in the proof of Proposition 2.9.
Additionally, we have:

$\displaystyle\mathop{\mathrm{\underline{supp}}}f$ $\displaystyle=\\{l\in
L:l(x)<\inf_{A\in D}f_{A}(x)\forall x\in X\\}$ $\displaystyle\subset\\{l\in
L:l(x)<f_{A}(x)\forall A\in D,x\in X\\}$ $\displaystyle=\cap_{A\in D}\\{l\in
L:l(x)<f_{A}(x)\forall x\in X\\}\subset\cap_{A\in D}A.$

Therefore $\mathop{\mathrm{\underline{supp}}}f\subseteq\cap_{A\in
D}A\subseteq\mathop{\mathrm{missing}}{supp}f$, we conclude that $\cap_{A\in
D}A$ is in $\mathcal{C}_{L}$.

Finally, to see that the third axiom is also satisfied, let $D$ be an ordered
family of sets from $\mathcal{C}$. For each $A\in D$, we define $f_{A}$ as
above. The nested nature of the sets in $D$ implies that for $A,A^{\prime}$ in
$D$, if $A\leq_{D}A^{\prime}$, then

$f_{A}\leq f_{A^{\prime}}.$ (2.1)

Let $S=\cup_{A\in D}A$ and $f=\sup_{A\in D}f_{A}$.

It is clear that $S\subset\mathop{\mathrm{missing}}{supp}f$, since for any
$u\in S$ there exists $A\in D$ such that
$u\in\mathop{\mathrm{missing}}{supp}f_{A}$. Then $u\leq f_{A}\leq f$. Now,
consider $u\notin S$. Then $u\notin\cup_{A\in
D}\mathop{\mathrm{\underline{supp}}}f_{A}$, and so there exists $x\in X$ such
that $u(x)\geq f_{A}(x)$ for any $A\in D$, and therefore that
$u(x)\geq\sup_{A\in D}f_{A}(x)=f(x)$. Therefore
$u\notin\mathop{\mathrm{\underline{supp}}}f$. This implies that
$\mathop{\mathrm{\underline{supp}}}f\subseteq
S\subseteq\mathop{\mathrm{missing}}{supp}f$, and therefore $S$ is in
$\mathcal{C}_{L}$ and $\mathcal{C}_{L}$ is a convexity structure. ∎

######  Remark 2.13.

Propositions 2.9 and 2.12 imply an equivalence relation between sets of
abstract linear functions according to the convexity structure (axioms 1-3) or
closure space (axioms 1,2) the induced abstract convex sets are isomorphic to.

Axiomatic convexity has been applied to obtain generalisations of well known
geometric results in convexity theory. Of particular interest to this paper
are generalisations of Carathéodory’s theorems. Much research has been devoted
to investigating this topic. We refer to [33] for a review of classical
results in the area.

######  Definition 2.14 ([33, Definition 1.5]).

In a given Convexity structure $\mathcal{C}$, a set $F$ is _Carathéodory
dependent_ if

$\mathrm{co}_{\mathcal{C}}F\subseteq\bigcup_{a\in
F}\mathrm{co}_{\mathcal{C}}(F\setminus\\{a\\}),$

and _Carathéodory independent_ otherwise.

Then we can define the _Carathéodory number_ of a convex structure
$\mathcal{C}$ as the largest cardinality of a Carathéodory independent set
(i.e., any set $F$ with cardinality greater than $c(x)$ is Carathéodory
dependent). The Carathéodory numbers of several important classes of convexity
structures are known and discussed in the literature [33].

Generalisations of Helly’s and Radon’s theorems were obtained similarly. The
Carathéodory number enables the following generalisation of Carathéodory’s
classical result:

######  Proposition 2.15 ([33, Theorem 1.7]).

Consider a convexity structure $(\mathcal{C},X)$ with Carathéodory number
$c(x)$, and let $A\subset\mathcal{C}$ be a convex set from $\mathcal{C}$.
Then, for any $x\in A$ there exists a set $F\subset A$ such that $\lvert
F\rvert\leq c(x)$ and $x\in\mathrm{co}F$. This is best possible.

##  3\. Application to approximation

###  3.1. Problem formulation

We are working with uniform (Chebyshev) approximation:

$\min_{A}\sup_{\mathbf{x}\in X}|f(\mathbf{x})-g(A,\mathbf{x})|,$ (3.1)

where $A$ are the decision variables and $X$ is a compact set. In many
computer based applications, this set is a finite grid defined on a convex
compact set. If we define $L=\\{A\to g(A,\mathbf{x}):x\in X\\}$, then it is
clear from Formulation (3.1) that the objective function of this problem is
$H_{L}$-convex.

In the case when the approximation function $g(A,t)$ is a polynomial (and its
coefficients are subject to optimisation), the optimality conditions are based
on maximal deviation points (Chebyshev theorem, see [7]). In the case of
univariate function approximation, the conditions are based on the notion of
alternating sequence.

######  Theorem 3.1 (Chebyshev).

A polynomial of degree at most $n$ is optimal in uniform (Chebyshev) norm if
and only there are $n+2$ alternating points.

Essentially, the approximations here are presented as linear combinations of
basis functions. In the case of polynomials the basis functions are monomials,
but other classes of basis functions can be used. The corresponding
optimisation problems are convex as supremum of linear forms. Theorem 3.1 can
be proved using convex analysis and the number of alternative point ($n+2$)
obtained through Carathéodory’s theorem. In other words, the following
conjecture is true, in the case when $L$ is a set of linear functions:

######  Conjecture 3.2.

For a function from $L$ to be an optimal approximation in uniform norm, it is
enough that it is optimal at $c(\mathcal{C}_{H_{L}})+1$ extreme points.

We also conjecture that this is best possible, in the sense that the statement
is generally not true if we replace $c(\mathcal{C}_{H_{L}})+1$ with
$c(\mathcal{C}_{H_{L}})$.

If true, this conjecture could form the basis for algorithms for best
approximation, such a generalisation of Vallée-Poussin’s procedure [12]. Later
in this section, we discuss an example of families $L$ in the context of this
conjecture.

One possible generalisation to polynomial approximation is rational
approximation, that is, approximation by the ratio of two polynomials, whose
coefficients are subject to optimisation. Note that in some cases, the degree
of the denominator and numerator can be reduced without compromising the
accuracy:

$\frac{\sum_{j=0}^{n}a_{j}t_{i}^{j}}{\sum_{k=0}^{m}b_{k}t_{i}^{k}}=\frac{\sum_{j=0}^{n-\nu}a_{j}t_{i}^{j}}{\sum_{k=0}^{m-\mu}b_{k}t_{i}^{k}},$

where $d=\min\\{\nu,\mu\\}$ is called the defect. Then the necessary and
sufficient optimality conditions are as follows [1].

######  Theorem 3.3.

A rational function in $\mathcal{R}_{n,m}$ with defect $d$ is the best
polynomial approximation of a function $f\in C^{0}(I)$ (the space of
continuous functions over $I$) if and only if there exists a sequence of at
least $n+m+2-d$ points of maximal deviation where the sign of the deviation at
these points alternates.

Therefore, similar to polynomial approximation, these conditions are bases the
number of alternating points.

In connection to Conjecture 3.2, $c(\mathcal{C}_{H_{L}})$ is $n+m+2$. If $n$
and $m$ are the degrees of the corresponding polynomials, then the total
number of the parameters is $n+1+m+1=n+m+2$. However, one of the parameters
can be fixed (otherwise one can divide the numerator and denominator by the
same number). Therefore, there are $n+m+1$ “free” parameters and we add one
more for $c(\mathcal{C}_{H_{L}})$ (similar to Carathéodory’s theorem from
classical convex analysis). We will provide a formal proof in a future paper.

Rational approximation was a very popular research area in the 1950s-70s [1,
4, 20, 27, 28] (just to name a few).

If the basis functions are not restricted to monomials, the approximations are
called generalised rational approximations. The term is due to Cheney and Loeb
[8].

One way to approach rational approximation is through constructing “near
optimal” solutions [24]. This approach is very efficient and therefore very
popular. The extension of this approach to non-monomial basis functions and
multivariate approximation remains open (an extension to complex domains can
be found in [23]).

An alternative way is based on modern optimisation techniques. This approach
is preferable when the basis function are not restricted to univariate
monomials and when deeper theoretical study is required. The corresponding
optimisation problems are quasiconvex and can be solved using a general
quasiconvex optimisation methods.

Rational and generalised rational functions are quasiaffine as ratios of
linear forms [5, 19, 26]. It can be solved efficiently by applying a simple,
but robust approach, called the bisection method for quasiconvex functions
[5].

In [26] the authors use a well-known bisection method for quasiconvex
functions (see [5]) to solve these problems. In [22], the authors use a
projection-type algorithm for solving these problems.

###  3.2. Bisection method

Bisection method for quasiconvex functions [5] can be used efficiently for
rational and generalised rational approximation, including multivariate
settings [21, 26]. Can we use abstract convexity to extend this method to a
wider class of approximations?

The problem can be formulated as follows:

$\text{minimise}~{}\tilde{z}$ (3.2)

subject to

$f(\mathbf{x})-\frac{\mathbf{A}^{T}\mathbf{G}(\mathbf{x})}{\mathbf{B}^{T}\mathbf{H}(\mathbf{x})}\leq\tilde{z},~{}\mathbf{x}\in
X,$ (3.3)
$\frac{\mathbf{A}^{T}\mathbf{G}(\mathbf{x})}{\mathbf{B}^{T}\mathbf{H}(\mathbf{x})}-f(\mathbf{x})\leq\tilde{z},~{}\mathbf{x}\in
X,$ (3.4) $\mathbf{B}^{T}\mathbf{H}(\mathbf{x})\geq\delta,~{}\mathbf{x}\in X,$
(3.5)

where $\tilde{z}$ is the maximal deviation and $\delta$ is a small positive
number. Problem (3.2)-(3.5) is not linear.

The idea of this method is based on the fact that all the sublevel sets of
quasiconvex functions are convex and therefore the sublevel sets of
quasiaffine functions are half-spaces. Essentially, this means that the
constraint set (3.3)-(3.5) for a fixed $\tilde{z}$ is an intersection of a
finite number of half-spaces ($X$ is a finite grid) and therefore it is a
polytope.

The algorithm starts with an upper and lower bound ($u$ and $l$) for the
maximal deviation, then the sublevel set for the maximal deviation at the
level $z=\frac{u+l}{2}$ is a convex set and the algorithm checks if this set
is empty. If it is empty, then the upper bound is updated to $z$, otherwise,
the lower bound is updated to $z$. The algorithm terminates when the upper and
lower bounds are within the specified precision.

In general, checking if the convex set (sublevel set of the maximal deviation)
is empty or not may be a difficult task (convex feasibility problems). There
are a number of efficient methods ([3, 34, 35, 36, 37] just to name a few),
but there are still several open problems here. The discussion of these
problems is out of scope of the current paper.

In the case of multivariate generalised rational approximation, however, this
problem (convex feasibility) can be reduced to solving a linear programming
problem [21]. The denominator of the approximation does not change the sign.
Assume, for simplicity, that it is positive, then the problem of checking the
feasibility is equivalent to solving the following problem:

$\text{minimise}~{}\tilde{u}$ (3.6)

subject to

$f(\mathbf{x}){\mathbf{B}^{T}\mathbf{H}(\mathbf{x})}-{\mathbf{A}^{T}\mathbf{G}(\mathbf{x})}\leq
z{\mathbf{B}^{T}\mathbf{H}(\mathbf{x})}+\tilde{u},~{}\mathbf{x}\in X,$ (3.7)
${\mathbf{A}^{T}\mathbf{G}(\mathbf{x})}-f(\mathbf{x}){\mathbf{B}^{T}\mathbf{H}(\mathbf{x})}\leq
z{\mathbf{B}^{T}\mathbf{H}(\mathbf{x})}+\tilde{u},~{}\mathbf{x}\in X,$ (3.8)
$\mathbf{B}^{T}\mathbf{H}(\mathbf{x})\geq\delta,~{}\mathbf{x}\in X,$ (3.9)

where $z=\frac{1}{2}(u+l)$ is the current bisection point (bisecting the
possible values of maximal deviation).

If an optimal solution $\tilde{u}\leq 0$, the corresponding sublevel set of
the maximal deviation function is not empty (update the upper bound),
otherwise the set is empty (update the lower bound). If $X$ is a finite grid,
then (3.6)-(3.9) is a linear programming problem and can be solved efficiently
at each step of the bisection method.

To summarise, an efficient implementation of the bisection method for
quasiconvex functions, can be extended to approximation by any type of
quasiaffine functions, since at each step one needs to check if a polytope
(intersection of a finite number of half-spaces) is non-empty. The main
problem is how to find this polytope. In the case of rational and generalised
rational approximation, this problem is simple, but not for some other types
of quasiaffine approximations. In section 4 we give more examples where the
construction of this polytope is straightforward (composition of monotone and
affine or ratios of affine functions).

One possibility for constructing sublevel sets for smooth quasiaffine
approximation is to use their gradients (if it is not vanishing). In the rest
section, we give an example demonstrating that this approach may be
complicated if there are constraints (even simple linear constraints). In
particulra, this approach will not work even in the case of rational
approximation due to the requirement for the denominator to be strictly
positive.

###  3.3. Approximation by a quasiaffine function

Suppose that instead of a generalised rational approximation one needs to
approximate by a function from a different class, but the approximations are
quasiaffine functions with respect to the decision variables. Then the problem
is as follows:

$\text{minimise}~{}\tilde{z}$ (3.10)

subject to

$f(\mathbf{x})-g(A,\mathbf{x})\leq\tilde{z},~{}\mathbf{x}\in X,$ (3.11)
$g(A,\mathbf{x})-f(\mathbf{x})\leq\tilde{z},~{}\mathbf{x}\in X,$ (3.12)

where $g(A,\mathbf{x})$ is a quasiaffine function. Since the sublevel sets of
quasiaffine functions are half-spaces, the constraint set (3.11)-(3.12) is a
polytope, since $X$ is a finite grid.

######  Remark 3.4.

A finite number of linear constraints may be added to (3.10)-(3.12), while the
constraint set remains a polytope.

Therefore, the constraint set (for any fixed $\tilde{z}$), with or without
additional linear constraints, is a poytope and we only need to check if this
polytope is non-empty. However, we still need an efficient approach for
finding this polytope. In the case of smooth functions, one can use the
gradient as a possible normal vector to the hyperplanes, providing that it is
not a zero vector. In section 4 we study the examples where the quasiaffine
approximations can be decomposed as a composition of strictly monotone and
affine (quasiaffine) functions. Other situations may be harder.

Note that if a function is quasiaffine on the whole space, then the sublevel
sets are half-spaces, whose boundary hyperplanes are parallel. Otherwise, two
hyperplanes will intersect. If there are additional (even linear) constraints,
this observation may not be valid anymore. The following example illustrates
that this may happen even in a very simple case of two variables.

######  Example 3.5.

Consider $f(x,y)=\frac{x}{y}$, where $y>0$. The sublevel sets are

$S_{\alpha}=\\{(x,y):\frac{x}{y}\leq\alpha,y>0\\},$

where $\alpha$ is a given real number. Then $S_{\alpha}$ can be described as

$\\{x-\alpha y\leq 0,\quad y>0\\}.$

Each sublevel set is still a half-space, but the corresponding hyperplanes (in
this example they correspond to level sets) are not parallel. These
hyperplanes intersect at $(0,0)$, but this point is excluded from the domain
due to the requirement for the denominator $y$ to be strictly positive.

This example demonstrates that the computation of sublevel sets for
quasiaffine functions may be challenging. In the next section we give some
examples of the classes of approximations that can be handled efficiently. We
also provide the results of the numerical experiments.

##  4\. Numerical experiments

###  4.1. Strictly monotone function in composition with an affine function.

In this example we approximate function

$f(x,y)=(-x+y^{3}+x^{4})^{4}$ (4.1)

by a quasiaffine function in the form

$g(A,x,y)=(a_{1}+a_{2}x+a_{3}y+a_{4}x^{2}+a_{5}y^{2}+a_{6}xy)^{3},$ (4.2)

where $A=(a_{1},a_{2},a_{3},a_{4},a_{5},a_{6})$ are the decision variables,
$x$ and $y$ form a grid on $[-1,1]$ with the step-size 0.1. The optimal
coefficients are (rounded to two decimal places):

$A=(-1.88,-0.75,0.31,3.29,0.98,-0.74),$

the maximal absolute deviation is 8.01 (to two decimal places).

Figure 1 represents the function $f(x,y)$, figure 2 depicts the best found
approximation and figure 3 contains the deviation function $f(x,y)-g(A,x,y)$,
which is the error of approximation.

Function $f(x,y)$ is almost flat with an abrupt increase around point
$(-1,1)$. Visually, the approximation resembles the shape of the original
function and the magnitude of the deviation confirms that the approximation is
reasonably good.

Figure 1. Function $f(x,y)=(-x+y^{3}+x^{4})^{4}$. Figure 2. Approximation
$g(A,x,y)=(a_{1}+a_{2}x+a_{3}y+a_{4}x^{2}+a_{5}y^{2}+a_{6}xy)^{3}$. Figure 3.
Deviation (error) function
$f(x,y)-g(A,x,y)=(-x+y^{3}+x^{4})^{4}-(a_{1}+a_{2}x+a_{3}y+a_{4}x^{2}+a_{5}y^{2}+a_{6}xy)^{3}.$

###  4.2. Strictly monotone function in composition with a rational function.

In this example we approximate the same function

$f(x,y)=(-x+y^{3}+x^{4})^{4}$ (4.3)

by a quasiaffine function in the form

$g_{1}(A,x,y)=\left(\frac{a_{1}+a_{2}x+a_{3}y+a_{4}x^{2}+a_{5}y^{2}}{1+a_{6}xy}\right)^{3},$
(4.4)

where, similar to the previous example,
$A=(a_{1},a_{2},a_{3},a_{4},a_{5},a_{6})$ are the decision variables (the
number of decision variables is the same as in the previous example), $x$ and
$y$ are on a grid $[-1,1]$ with the step-size 0.1. The purpose of
approximation is to use lower degree polynomials in the composition. The
optimal coefficients are (rounded to two decimal places):

$A=(-1.66,-0.93,1.05,2.87,0.98,1),$

the maximal absolute deviation is 11.48 (to two decimal places).

Figure 4 contains the best found approximation and figure 5 depicts the
deviation function $f(x,y)-g_{1}(A,x,y)$, which is the error of approximation.

The new approximation still resembles the shape of the original function, but
the maximal deviation is higher.

Figure 4. Approximation
$g_{1}(A,x,y)=(\frac{a_{1}+a_{2}x+a_{3}y+a_{4}x^{2}+a_{5}y^{2}}{1+a_{6}xy})^{3}$.
Figure 5. Deviation (error) function
$f(x,y)-g(A,x,y)=(-x+y^{3}+x^{4})^{4}-\left(\frac{a_{1}+a_{2}x+a_{3}y+a_{4}x^{2}+a_{5}y^{2}}{1+a_{6}xy}\right)^{3}.$

####  4.2.1. Deep learning applications.

At first glance, the class of a composition of a monotone univariate function
with an affine or rational function is restrictive. However, it has many
practical applications, including deep learning, where compositions of
univariate activation functions and affine transformations are the main
components or the models [16]. Most common choices for activation functions
are sigmoid functions, ReLU and Leaky ReLU (the last two functions are simply
non-decreasing piecewise linear functions with two linear pieces).

##  5\. Conclusions

The goal of this study is to demonstrate that abstract convexity (in the sense
“convexity without linearlity”) has several applications in different branches
of mathematics, including approximation theory. This application appears
naturally in the new settings.

The results of the numerical experiments demonstrate that our approach is
computationally efficient. The applications lead to practical applications as
well. One potential application is data science and deep learning.

We also touched the connections between “abstract convexity” and “axiomatic
convexity”. These areas have many overlappings that can be seen as a new way
of looking at the problems, in particular, function approximation.

Acknowledgements

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

## References

  * Achieser [1956] Achieser.  _Theory of Approximation_.  Frederick Ungar, New York, 1956.
  * Andramonov [2002] Mikhail Andramonov.  A survey of methods of abstract convex programming.  _Journal of Statistics and Management Systems_ , 5(1-3):21–37, 2002.  doi: 10.1080/09720510.2002.10701049.  URL https://doi.org/10.1080/09720510.2002.10701049.
  * Bauschke and Lewis [2000] Heinz H Bauschke and Adrian S Lewis.  Dykstras algorithm with bregman projections: A convergence proof.  _Optimization_ , 48(4):409–427, 2000.
  * Boehm [1964] Boehm.  Functions whose best rational chebyshev approximation are polynomials.  _Numer. Math._ , pages 235––242, 1964.
  * Boyd and Vandenberghe [2009] S. Boyd and L. Vandenberghe.  _Convex Optimization_.  Cambridge University Press, New York, USA, seventh edition, 2009.
  * Bui et al. [2021] Hoa T. Bui, Regina S. Burachik, Alexander Y. Kruger, and David T. Yost.  Zero duality gap conditions via abstract convexity.  _Optimization_ , 0(0):1–37, 2021.  doi: 10.1080/02331934.2021.1910694.  URL https://doi.org/10.1080/02331934.2021.1910694.
  * Chebyshev [1955] P.L Chebyshev.  The theory of mechanisms known as parallelograms.  In _Selected Works_ , pages 611–648. Publishing Hours of the USSR Academy of Sciences, Moscow, 1955.  (In Russian).
  * Cheney and Loeb [1964] E.W. Cheney and H.L. Loeb.  Generalized rational approximation.  _Journal of the Society for Industrial and Applied Mathematics, Series B: Numerical Analysis_ , 1(1):11–25, 1964.
  * Crouzeix [1980] J. P. Crouzeix.  Conditions for convexity of quasiconvex functions.  _Mathematics of Operations Research_ , 5(1):120–125, 1980.
  * Daniilidis et al. [2002] A. Daniilidis, N. Hadjisavvas, and J.-E. Martinez-Legaz.  An appropriate subdifferential for quasiconvex functions.  _SIAM Journal on Optimization_ , 12(2):407–420, 2002.
  * de Finetti [1949] B. de Finetti.  Sulle stratificazioni convesse.  _Ann. Mat. Pura Appl._ , pages 173–183, 1949.
  * [12] C J de la Vallée Poussin.  Sur la méthode de l’approximation minimum.  _Ann. Soc. Sci. Bruxelles_ , 35:1–16.
  * Duchet [1987] Pierre Duchet.  Convexity in combinatorial structures.  In _Proceedings of the 14th Winter School on Abstract Analysis_ , pages [261]–293. Circolo Matematico di Palermo, 1987.  URL http://eudml.org/doc/220736.
  * Dutta and Rubinov [2005] J. Dutta and A. M. Rubinov.  Abstract convexity.  _Handbook of generalized convexity and generalized monotonicity_ , 76:293–333, 2005.
  * Fan [1963] Ky Fan.  On the Krein-Milman theorem.  In _Convexity: Proceedings of the Seventh Symposium in Pure Mathematics of the American Mathematical Society_ , pages 211–219. American Mathematical Society, 1963.  doi: 10.1090/pspum/007/0154097.  URL https://doi.org/10.1090%2Fpspum%2F007%2F0154097.
  * Goodfellow et al. [2016] Ian Goodfellow, Yoshua Bengio, and Aaron Courville.  _Deep Learning_.  MIT Press, 2016.  http://www.deeplearningbook.org.
  * Kutateladze and Rubinov [1972] S S Kutateladze and A M Rubinov.  Minkowski duality and its applications.  _Russ. Math. Surv._ , 27(3):137–191, jun 1972\.  doi: 10.1070/rm1972v027n03abeh001380.  URL https://doi.org/10.1070%2Frm1972v027n03abeh001380.
  * Levi [1951] F. W. Levi.  On helly’s theorem and the axioms of convexity.  _Journal of the Indian Mathematical Society_ , 15:65–76, 1951.
  * Loeb [1960] Henry L Loeb.  Algorithms for chebyshev approximations using the ratio of linear forms.  _Journal of the Society for Industrial and Applied Mathematics_ , 8(3):458–465, 1960.
  * Meinardus [1967] G. Meinardus.  _Approximation of Functions: Theory and Numerical Methods_.  Springer-Verlag, Berlin, 1967.
  * Millán et al. [a] R. Díaz Millán, V. Peiris, N. Sukhorukova, and J. Ugon.  Multivariate approximation by polynomial and generalised rational functions.  _Accepted in Optimization_ , a.  URL https://arxiv.org/abs/2101.11786v1.
  * Millán et al. [b] R. Díaz Millán, N. Sukhorukova, and J. Ugon.  An algorithm for best generalised rational approximation of continuous functions.  _In PRESS, accepted in Set-Valued and Variational Analysis_ , b.  URL https://arxiv.org/abs/2011.02721.
  * Nakatsukasa and Trefethen [2020] Yuji Nakatsukasa and Lloyd N. Trefethen.  An algorithm for real and complex rational minimax approximation.  _SIAM Journal on Scientific Computing_ , 42(5):A3157–A3179, 2020.  doi: 10.1137/19M1281897.
  * Nakatsukasa et al. [2018] Yuji Nakatsukasa, Olivier Sete, and Lloyd N. Trefethen.  The aaa algorithm for rational approximation.  _SIAM Journal on Scientific Computing_ , 40(3):A1494–A1522, 2018.
  * Pallaschke and Rolewicz [1997] Diethard Pallaschke and Stefan Rolewicz.  _Foundations of Mathematical Optimization: Convex Analysis without Linearity_ , volume 388.  Springer Science & Business Media, 1997.
  * Peiris et al. [2021] V. Peiris, N. Sharon, N. Sukhorukova, and J. Ugon.  Generalised rational approximation and its application to improve deep learning classifiers.  _Applied Mathematics and Computation_ , 389:125560, jan 2021\.  doi: 10.1016/j.amc.2020.125560.  URL https://doi.org/10.1016%2Fj.amc.2020.125560.
  * Ralston [1965] Anthony Ralston.  Rational chebyshev approximation by remes’ algorithms.  _Numer. Math._ , 7(4):322–330, August 1965.  ISSN 0029-599X.
  * Rivlin [1962] TJ Rivlin.  Polynomials of best uniform approximation to certain rational functions.  _Numerische Mathematik_ , 4(1):345–349, 1962\.
  * Rubinov [2013] A. M. Rubinov.  _Abstract convexity and global optimization_ , volume 44.  Springer Science & Business Media, 2013.
  * Rubinov and Simsek [1995] A. M. Rubinov and B. Simsek.  Conjugate quasiconvex nonnegative functions.  _Optimization_ , 35(1):1–22, 1995.  doi: 10.1080/02331939508844124.
  * Singer [1997] Ivan. Singer.  _Abstract convex analysis / Ivan Singer._ Canadian Mathematical Society series of monographs and advanced texts. Wiley, New York, 1997.  ISBN 0471160156.
  * Soltan [1984] V.V. Soltan.  _Introduction to the Axiomatic Theory of Convexity_.  Sthiinka, Kishinev, 1984.  In Russian.
  * van de Vel [1993] M.L.J. van de Vel.  _Theory of convex structures_.  North-Holland, Amsterdam New York, 1993.  ISBN 9780080933108.
  * ya Matsushita and Xu [2016] Shin ya Matsushita and Li Xu.  On the finite termination of the douglas-rachford method for the convex feasibility problem.  _Optimization_ , 65(11):2037–2047, 2016.
  * Yang and Yang [2013] Yuning Yang and Qingzhi Yang.  Some modified relaxed alternating projection methods for solving the two-sets convex feasibility problem.  _Optimization_ , 62(4):509–525, 2013.
  * Zaslavski [2013] A. J. Zaslavski.  Subgradient projection algorithms and approximate solutions of convex feasibility problems.  _Journal of Optimization Theory and Applications_ , 157:803–819, 2013.
  * Zhao and Köbis [2018] 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(9):1409–1427, 2018.