# Sparse Coresets for SVD on Infinite Streams

Vladimir Braverman Department of Computer Science, Johns Hopkins University.
Dan Feldman Department of Computer Science, University of Haifa. Harry Lang
MIT CSAIL. Daniela Rus MIT CSAIL. Adiel Statman University of Haifa.

###### Abstract

In streaming Singular Value Decomposition (SVD), $d$-dimensional rows of a
possibly infinite matrix arrive sequentially as points in $\mathbb{R}^{d}$. An
$\epsilon$-coreset is a (much smaller) matrix whose sum of square distances of
the rows to any hyperplane approximates that of the original matrix to a
$1\pm\epsilon$ factor. Our main result is that we can maintain a
$\epsilon$-coreset while storing only $O(d\log^{2}d/\epsilon^{2})$ rows. Known
lower bounds of $\Omega(d/\epsilon^{2})$ rows show that this is nearly
optimal. Moreover, each row of our coreset is a weighted subset of the input
rows. This is highly desirable since it: (1) preserves sparsity; (2) is easily
interpretable; (3) avoids precision errors; (4) applies to problems with
constraints on the input. Previous streaming results for SVD that return a
subset of the input required storing $\Omega(d\log^{3}n/\epsilon^{2})$ rows
where $n$ is the number of rows seen so far. Our algorithm, with storage
independent of $n$, is the first result that uses finite memory on infinite
streams. We support our findings with experiments on the Wikipedia dataset
benchmarked against state-of-the-art algorithms.

##  1 Introduction

Coresets are a small representation of a large dataset that preserve some key
property of interest. For example, given a large clustering problem over $n$
points, one could build an $\epsilon$-coreset of $O(\log n)$ points and then
run an off-the-shelf algorithm on the coreset to obtain a
$(1+\epsilon)$-approximate solution. Coresets have been widely studied in
recent years for a variety of problems [7, 1, 12, 9].

Much of the large scale high-dimensional data sets available today (e.g. image
streams, text streams, etc.) are sparse. For a concrete example, we can
associate a matrix with Wikipedia where ($1.4\times 10^{6}$) words define the
columns and ($4.4\times 10^{6}$) documents define the rows. Entry $(i,j)$ is
the number of occurrences of word $j$ in document $i$. Since most documents
only contain $\sim 10^{3}$ words, this matrix is very sparse. Recently, the
first algorithm that could compute the eigenvectors of this matrix on
commodity hardware was provided by [10]. We benchmark our algorithm against
this result for the Wikipedia matrix and show dramatic improvements in both
runtime and accuracy.

We consider Singular Value Decomposition (SVD) in the streaming model, which
is applicable to processing large datasets or real-time data [10, 12]. In the
streaming model, the rows of a (possibly infinite) matrix
$A\in\mathbb{R}^{?\times d}$ arrive sequentially as
$(a_{1},a_{2},a_{3},\ldots)$. Our main contribution is an algorithm to
maintain an $\epsilon$-coreset for SVD while storing only $O(d\log d)$ rows.
Our construction has the desirable property that it is a weighted subset of
the input. The property that each row of the coreset is a multiple of a single
row of the input is important because: (1) sparsity is preserved, (2) the
coreset is easy to interpret, and (3) there are less floating point precision
issues.

######  Theorem 1 (Main Theorem).

It is possible to maintain an $\epsilon$-coreset for SVD in the streaming
model on an $n\times d$ matrix using $O(d\log d/\epsilon^{2})$ space and
$O(d^{2})$ worst-case update time111The space and update time are measured in
terms of a single $d$-dimensional row (i.e. multiply by $d$ obtain the
space/time in bits).

Previous coreset results required dependence on $n$, the number of rows seen
so far. This is the first streaming result for an SVD coreset that uses finite
memory on an infinite stream. Moreover, the coreset is a weighted subset of
the input, implying that properties of the input (such as sparsity) are
preserved.

Our solution is a mixture of a known RAM model coreset with a novel streaming
approach. The existing construction defines a distribution over all rows of
the input, and draws an i.i.d. sample which becomes the coreset (after
reweighting). Thus, the coreset is naturally a subset of the input. We use the
coreset inductively to compute the sampling probabilities after each update
(i.e. after each row is received), and maintain a set of samplers in parallel.
Each sampler runs a simple procedure we call singleton sampling. If a sampler
contains exactly one element, then the probability distribution regarding
which element it contains is identical to the desired sampling distribution
for the coreset. If it does not contain exactly one element, then we ignore
that sampler as having failed (at that particular time; later it may contain
exactly one element and be used). Our coreset is then the union over all
samplers containing one element, therefore keeping the known RAM construction
in the streaming setting without incurring any of the overhead associated with
previous techniques.

##  2 Prior Work

Work | Subset of Input | Space In Rows
---|---|---
[10] | Yes | $O(d^{2}\epsilon^{-2}\log^{3}n)$
[3] | No | $O(d^{2}\epsilon^{-2}\log^{3}n)$
[9] | ? | $O(d\epsilon^{-2})$
[7] | Yes | $O(d^{2}\epsilon^{-2}\log^{3}n)$
[5] | Yes | $O(d\log d\epsilon^{-2}\log^{3}n)$
** | Yes | $O(d\log d/\epsilon^{2})$

The result most similar to the present work is [5], where rows are sampled
according to their Lewis weight. As explained in that paper, the Lewis weight
is equivalent to the statistical leverage score defined in other literature
such as [6]. While sampling $O(d\log d\epsilon^{-2})$ rows, they construct a
coreset in the RAM model. Like all RAM model construction with inverse-
quadratic dependence on $\epsilon$, the merge-and-reduce technique can be
applied to construct a coreset in the streaming model while incurring
$O(\log^{3}n)$ space overhead.

Also in the RAM model, a coreset of size $O(d^{2}/\epsilon^{2})$ is given in
[10]. When plugged into the merge-and-reduce tree, the final space is
$O(d^{2}\epsilon^{-2}\log^{3}n)$ space. In the current work, we provide a
coreset using only $O(d\log d\epsilon^{-2})$ space, so independent of the
input size $n$, therefore valid for infinite streams.

A dimensionality reduction technique for low-rank approximation [3] can be
used to construct a coreset for SVD of size $O(d^{2}/\epsilon^{2})$ in the RAM
model, leading to a streaming space of $O(d^{2}\epsilon^{-2}\log^{3}n)$.
However, the resulting coreset is not a subset of the input. This property is
attained (with the same space bound) in [7].

##  3 Our Techniques

To construct a coreset, we must sample from a distribution over the input.
This is the approach taken by a wide-class of constructions such all those
inspired by [7]. In the RAM model this is trivial since we can access the
entire input without restriction. Suppose we wish to sample one point from a
stream ($a_{1}$, $a_{2}$, …, $a_{n}$) where the probability of sampling
$a_{i}$ is $\pi(a_{i})/\sum_{j=1}^{n}\pi(a_{j})$ for some non-negative
function $\pi$. If the distribution is known beforehand, then reservoir
sampling will obtain the desired sample. The difficulty in the streaming
problem is that the distribution is discovered as the stream arrives.

Reservoir sampling does not work when the probabilities change. We generalize
reservoir sampling in exchange for small probability of failure. See Figure 1
for an example of our technique on a simple distribution over two points
$(a,b)$. Here $\pi(a)=1/3$ and $\pi(b)=2/3$. Suppose that after receiving
point $a$, we take a random draw $u_{a}$ from the interval $[0,1)$ and keep
$a$ in memory if and only if $u_{a}<\pi(a)$. We do the same for $b$. At the
end of the stream, we declare failure unless there is exactly one point stored
in memory (we will argue the probability of failure is low). Then, as seen in
the top row, the distribution that we actually sample from has been distorted
(see top-right box). However, if we pre-transform the distribution (as shown
in the bottom row), then this cancels the distortion and we recover the
desired distribution (see bottom-right box).

While this example does not show the probabilities $\pi(a)$ or $\pi(b)$
changing, we later apply some additional properties gauranteed by the
functions relevant to SVD that we can easily handle this generalization.

Figure 1: Singleton Sampling. Given a distribution over elements (column 1),
we can independently sample element $n$ with probability $p_{n}$ to obtain a
subset (column 2), which is then filtered to only obtain singletons (column
3). However, the final distribution is distorted (row 1). By pre-transforming
the input distribution (row 2), we can recover the desired distribution
through singleton sampling.

In Section 5 we restate a existing result to construct a coreset in the RAM
model. Section 6 will demonstrate how this construction can be accomplished
while only looking at the $d$ rows of the $A^{\top}A$ (referencing the $n$
rows of $A$ in a very limited way). Finally, in Section 7 we employ singleton
sampling to maintain this coreset construction in the streaming setting.

##  4 Preliminaries

Matrix Notation: For a matrix $M\in\mathbb{R}^{n\times d}$, let $M_{ij}$
denote the entry at row $i$ and column $j$. $M_{\bullet j}\in\mathbb{R}^{n}$
denotes the $j^{\text{th}}$ column and $M_{j\bullet}\in\mathbb{R}^{d}$ denotes
the $i^{\text{th}}$ row. To simplify notation throughout the proofs, we let
$m_{i}=M_{i\bullet}^{\top}$ (and likewise: $a_{i}=A_{i\bullet}^{\top}$ and
$u_{i}=U_{i\bullet}^{\top}$). For a matrix $M\in\mathbb{R}^{n\times d}$ the
term orthonormal means that $MM^{\top}=I_{n}$ or $M^{\top}M=I_{d}$. This
generalizes the notion of an orthonormal square matrix, where both equalities
are equivalent. When $n\neq d$, at most one of the equalities can hold.

######  Definition 1 (Squared-Distance).

For a vector $a^{\prime}\in\mathbb{R}^{d}$ and a compact set
$S\subset\mathbb{R}^{d}$, the squared-distance between $a^{\prime}$ and $S$
is:

$\mu(a^{\prime},S)=\min_{s\in S}\|a^{\prime}-s\|_{2}^{2}$

where $\|\cdot\|_{2}$ is the $\ell_{2}$-norm. This notation is overloaded for
a matrix $A\in\mathbb{R}^{n\times d}$ as:

$\mu(A,S)=\sum_{i=1}^{n}\mu(a_{i},S)$

The above definition is the cost function used to define a coreset for SVD.
The input to the SVD problem is a matrix $A\in\mathbb{R}^{n\times d}$ which
can be considered as a set of $n$ points in $\mathbb{R}^{d}$, namely
$\\{a_{1},\ldots,a_{n}\\}$.

######  Definition 2 (Coreset for SVD).

Let $A\in\mathbb{R}^{n\times d}$ and $\epsilon\in[0,1]$. A $\epsilon$-coreset
for $A$ is matrix $B\in\mathbb{R}^{m\times d}$ such that for every affine
$(d-1)$-subspace $S\subset\mathbb{R}^{d}$ we have:

$|\mu(A,S)-\mu(B,S)|\leq\epsilon\mu(A,S)$

The size of the coreset $B$ is $m$ (the number of rows in $B$). When for each
$j\in[m]$ we can write $b_{j}=wa_{i}$ for some value $w>0$ and $i\in[n]$, we
say that $B$ is a weighted subset of the input.

If a coreset is a weighted subset of the input, then sparsity is preserved and
the coreset admits a sparse representation whenever the input does.

##  5 Coreset Construction

In this section we show how to build a coreset for SVD, leaving computational
concerns for the next section. Let $\mathcal{S}_{d}$ be the set of all $d-1$
dimensional subspaces of $\mathbb{R}^{d}$.

######  Definition 3 (Sensitivity).

Let $A\in\mathbb{R}^{n\times d}$. The sensitivity of a row $a_{i}$ with
respect to $A$ is:

$s_{A}(a_{i})=\max_{S\in\mathcal{S}_{d}}\frac{\mu(a_{i},S)}{\mu(A,S)}$

One can immediately observe that the sensitivity of any row lies in the
interval $[0,1]$. We draw upon the result of [5], who refer to the sensitivity
by the name Lewis weight. The sensitivity has also been used by the term
leverage score in other publications.

######  Theorem 2 ($\ell_{2}$ Matrix Concentration Bound from [5]).

Let $A\in\mathbb{R}^{n\times d}$. Let $t=\sum_{i\in[n]}s_{A}(a_{i})$. Define a
distribution over $A$ such that $a_{i}$ has weight $s_{A}(a_{i})/t$. Sample
$m$ rows i.i.d. where:

$m\geq\frac{3t}{\epsilon^{2}}\left(\log_{2}d+\ln\frac{1}{\delta}\right)$

Construct a matrix $C\in\mathbb{R}^{m\times d}$ such each sampled row
$a_{i}\in A$ corresponds to a row $\frac{t}{ms_{A}(a_{i})}a_{i}\in C$. With
probability $1-\delta$, $C$ is an $\epsilon$-coreset for $A$.

Using Theorem 2, the problem of constructing a coreset in the RAM model is
reduced to computing $s_{A}(a_{i})$ for each row $a_{i}\in A$. The next
section addresses this task. Then in Section 7 we will export this
construction to the streaming model.

##  6 Computing Sensitivity

We will show the construction in the RAM model, using only a restricted part
of the input $A^{\top}A$, and then extend this to the streaming model in the
next section.

######  Theorem 3.

Algorithm 1 takes $A^{\top}A\in\mathbb{R}^{d\times d}$ as input, terminates in
$O(d^{3})$ time, and outputs $Z=\mathcal{B}(A^{\top}A)\in\mathbb{R}^{d\times
r}$ (where $r$ is the rank of $A$) such that $s(a_{i})=\|A_{i\bullet}Z\|$ for
each $i\in[n]$.

Before presenting Algorithm 1, we show how one could compute the sensitivity
by having all of $A$ (and not only $A^{\top}A$) in memory.

######  Definition 4 (Thin SVD).

Let $A\in\mathbb{R}^{n\times d}$ be a matrix of rank $r$. A Thin Singular
Value Decomposition of $A$ is a (not necessarily unique) decomposition
$A=UDV^{\top}$ for matrices $U\in\mathbb{R}^{n\times r}$,
$D\in\mathbb{R}^{r\times r}$, and $V\in\mathbb{R}^{d\times r}$ such that:

  * •

$U^{\top}U=V^{\top}V=I_{r}$

  * •

$D\in\mathbb{R}^{r\times r}$ is a diagonal matrix of positive values in non-
increasing order

It is well-known that the matrix $D$ is unique, so we write $D_{A}$ to specify
the middle matrix in a Thin SVD of $A$. Algorithms such as in [13] exist to
compute the Thin SVD in $O(d^{2})$ time (the time is in terms of number of
operations on $d$-dimensional vectors).

######  Lemma 1 (Corollary of Lemma 3.1 of [12]).

Let $UDV^{\top}$ be a Thin SVD of a matrix $A$. The sensitivity (see
Definition 3) of row $a_{i}$ is $\|u_{i}\|^{2}$.

The matrices $U$ and $V$ are not unique, but Lemma 1 implies that $\|u_{i}\|$
is invariant under any possible choice of $U$. Therefore one can compute the
sensitivity of a point by computing any Thin SVD and then taking the norm of
each row of $U$. We now turn our attention to proving Theorem 3, where
$\mathcal{B}(A^{\top}A)$ is not unique but the value obtained for the
sensitivity is unique.

######  Fact 1.

The rank of $A^{\top}A$ is equal to the rank of $A$.

###### Proof.

Let $UDV^{\top}$ be a Thin SVD of $A$. Then $A^{\top}A$ has a Thin SVD of
$VD_{A}^{2}V^{\top}$. The result follows since all diagonal entries of
$D_{A}^{2}$ are non-zero. ∎

We now walk through Algorithm 1 which computes the matrix
$Z=\mathcal{B}(A^{\top}A)$. Line 1 computes a Thin SVD in in $O(d^{2})$ time.
$A^{\top}A$ is symmetric positive-definite, so it is guaranteed that $U=V$. By
uniqueness of singular values, we have that $\Lambda=D_{A^{\top}A}=D_{A}^{2}$.
On Line 2 we compute $D_{A}$ by taking the positive square-root of the entries
of $D_{A}^{2}$, which are all real since $D_{A}^{2}$ has positive diagonal
entries. Let $r$ denote the rank of $A$. $D_{A}V^{\top}\in\mathbb{R}^{r\times
d}$ has rank $r$ and $r\leq d$, so a right-inverse $Z\in\mathbb{R}^{d\times
r}$ exists such that $D_{A}V^{\top}Z=I_{r}$ (see Line 3).

We can therefore decompose $A=(AZ)D_{A}V^{\top}$. If this is a Thin SVD, we
can calculate the sensitivity of any row of $A$ by using $Z$. First, we must
verify that it is indeed a Thin SVD; it satisfies all properties but it
remains to prove that the columns of $AZ$ are orthonormal.

######  Lemma 2.

For any matrix $Z$ output by Algorithm 1, $AZ$ is orthonormal.

###### Proof.

Algorithm 1 has exactly two sources of ambiguity: the choice of $V$ on Line 1
and the choice of $Z$ on Line 3 (if $r<d$ the right-inverse is not unique).
The ambiguity of $Z$ is irrelevant since the value of $AZ$ is invariant under
any choice. It remains to prove the lemma under any choice of $V$ on Line 1.

Let $(U^{\prime},D_{A},V^{\prime})$ be a Thin SVD of $A$. Then
$A^{\top}A=V^{\prime}D_{A}^{2}V^{\prime\top}$, and therefore the choice
$V=V^{\prime}$ is a possible outcome of Line 1.

For each diagonal entry $\lambda$ in $\Lambda$, the eigenspace $E_{\lambda}$
is unique. Let us temporarily fix $\lambda$. Moreover, if $\lambda$ occured in
slots $j$ through $j^{\prime}$ then $E_{\lambda}=\text{span}(V_{\bullet
j},\ldots,V_{\bullet j^{\prime}})$. Let $s=j^{\prime}-j+1=\dim(E_{\lambda})$.
Let $V_{\lambda}\in\mathbb{R}^{d\times s}$ denote the truncation of the $V$ to
just columns $j$ through $j^{\prime}$. By uniqueness of the space
$E_{\lambda}$, the matrix $V_{\lambda}$ is unique up to right-multiplication
by an orthonormal matrix $X_{\lambda}\in\mathbb{R}^{s\times s}$. In other
words, $V^{\prime}_{\lambda}=V_{\lambda}X_{\lambda}$. Let $X$ be the block-
diagonal $r\times r$ matrix of orthonormal transformations in each eigenspace
from $V$ to $V^{\prime}$, namely $V^{\prime}=VX$. Observe since each
$X_{\lambda}$ multiplies with $\lambda I_{s}$ in $D$, we have the commuting
relationship $XD=DX$. Then we have
$DV^{\prime\top}=DX^{\top}V^{\top}=X^{\top}DV^{\top}$.

Now consider the $U(V)$ and $U(V^{\prime})$, the matrices $U$ we get from
using $V$ or $V^{\prime}$, respectively. Observe the orthonormal relation
$U(V)=U(V^{\prime})X^{\top}$. Since the columns of $U(V^{\prime})$ and
$X^{\top}$ are orthonormal, we conclude that $U(V)$ also has orthonormal
columns. ∎

Lemma 2 ensures that $(AZ,D,V)$ is a Thin SVD of $A$ where the matrices $Z$,
$D$, and $V$ are taken from any realization of Algorithm 1. We therefore
conclude by Lemma 1 that $s(a_{i})=\|A_{i\bullet}Z\|$. This completes the
proof of Theorem 3.

Algorithm 1 Input: matrix $\Psi\in\mathbb{R}^{d\times d}$

1:$(U,\Lambda,V)\leftarrow$ a Thin SVD of $\Psi$

2:$D\leftarrow\sqrt{\Lambda}$ $\triangleright$ $D\in\mathbb{R}^{r\times r}$
where $r=\texttt{rank}(\Psi)\leq d$

3:$Z\leftarrow$ a right-inverse of $DV^{\top}$ $\triangleright$
$Z\in\mathbb{R}^{r\times d}$

4:return $Z$

In conclusion, we denote deterministic Algorithm 1 to take $A^{\top}A$ and
output a matrix $Z$. Although $Z$ may not be unique, it has the required
invariant of $s(a_{i})=\|A_{i\bullet}Z\|^{2}$ for each $i\in[n]$.

##  7 Streaming Algorithm

######  Definition 5 (Streaming $\epsilon$-coreset).

A streaming $\epsilon$-coreset is an algorithm that receives a stream of
elements. After receiving each element, it returns an $\epsilon$-coreset for
the prefix of elements received so far.

Now the rows of $A$ will arrive in a stream. Let $a_{i}$ denote the
$i^{\text{th}}$ row of $A$, and let $A_{n}$ denote the matrix $A$ after the
first $n$ rows have arrived. On Line 14, $s_{n}(a_{i})$ is the sensitivity of
row $a_{i}$ with respect to $A_{n}$ (rows $a_{1},\ldots,a_{n}$).

Algorithm 2 Input: $\epsilon\in(0,1)$, $\delta\in(0,1)$, stream of points in
$\mathbb{R}^{d}$

1:$m\leftarrow\lceil 3d\epsilon^{-2}(\log_{2}^{2}d+\ln(2/\delta))\rceil$

2:$Y\leftarrow\\{1,\ldots,8m\\}$ $\triangleright$ index over the samplers

3:for each $y\in Y$ do

4: $M_{y}\leftarrow\emptyset$ $\triangleright$ each $M_{y}$ stores a sample of
rows

5:$\Psi_{0}\leftarrow 0_{d\times d}$ $\triangleright$
$\Psi_{i}=A_{i}^{\top}A_{i}$ for all $i$

6:for each row $a_{n}\in\mathbb{R}^{d}$ from the stream do

7: $\Psi_{n}\leftarrow\Psi_{n-1}+a_{n}a_{n}^{\top}$

8: for each $y\in Y$ do

9: $u_{y}(a_{n})\leftarrow$ uniform random number in $[0,1)$

10: $M_{y}\leftarrow M_{y}\cup\\{a_{n}\\}$

11: $Z_{n}\leftarrow\mathcal{B}(\Psi_{n})$ $\triangleright$ Algorithm 1

12: $r_{n}\leftarrow$ number of columns of $Z_{n}$

13: for each $a_{i}\in\cup_{y}M_{y}$ do

14: $s_{n}(a_{i})\leftarrow\|Z_{n}^{\top}a_{i}\|^{2}$ $\triangleright$ compute
sensitivity

15: for each $y\in Y$ do

16: for each $a_{i}\in M_{y}$ do

17: if $u_{y}(a_{i})>\frac{s_{n}(a_{i})}{s_{n}(a_{i})+r_{n}}$ then

18: Delete $a_{i}$ from $M_{y}$

19: $\Gamma_{n}\leftarrow\\{y\in Y:|M_{y}|=1\\}$ $\triangleright$ index over
singleton samples

20: $Q_{n}\leftarrow\cup_{y\in\Gamma_{n}}M_{y}$ $\triangleright$ the union of
all samples containing exactly one row

21: for each $a_{i}\in Q_{n}$ do

22: $w_{n}(a_{i})\leftarrow\frac{r_{n}}{|Q_{n}|s_{n}(a_{i})}$

23: return $(Q_{n},w_{n})$ $\triangleright$ the $\epsilon$-coreset for $A_{n}$

Figure 2: The flow for updating the samplers after each update in Algorithm 2.
The new point is first added to each sampler, and then the deletion condition
is checked for every point in every sampler. Figure 3: The input stream is
read into an array of $8m$ samplers $\\{M_{y}\\}_{y\in Y}$. At each step, the
samplers containing exactly one element are combined to obtain a coreset.

######  Theorem 4 (Main Theorem).

Let $\epsilon,\delta\in(0,1)$ and let $A$ be a stream of rows in
$\mathbb{R}^{d}$. After receiving each row of $A$, Algorithm 2 returns an
$\epsilon$-coreset for $A$ with probability $1-\delta$. The space is
$O(\frac{d}{\epsilon^{2}}(\log^{2}d+\log\frac{1}{\delta}))$ rows and the
worst-case update time is $O(d^{2})$.

We denote the rank of $A_{n}$ by $r_{n}$ (computed on Line 12). The next lemma
shows that we know the total sensitivity exactly.

######  Lemma 3.

The total sensitivity of $A_{n}$ is $r_{n}$.

###### Proof.

We must prove $\sum_{i=1}^{n}s_{n}(a_{i})=r_{n}$. For any Thin SVD
$A_{n}=UDV^{T}$, we have that $s_{n}(a_{i})=\|u_{i}\|^{2}$ by Lemma 1, so it
suffices to compute $\sum_{i=1}^{n}\|u_{i}\|^{2}$. Since the columns of $U$
are orthonormal, we argue as follows:

$\displaystyle\sum_{i=1}^{n}\|u_{i}\|^{2}$
$\displaystyle=\sum_{i=1}^{n}\sum_{j=1}^{r_{n}}U_{ij}^{2}$
$\displaystyle=\sum_{j=1}^{r_{n}}\sum_{i=1}^{n}U_{ij}^{2}$
$\displaystyle=\sum_{j=1}^{r_{n}}\|u_{j}\|^{2}$
$\displaystyle=\sum_{j=1}^{r_{n}}1$ $\displaystyle={r_{n}}$

∎

Note that $r_{n}$ (the rank of $A_{n}$) equals the dimension of the row-space
of $A_{n}$ and therefore cannot decrease as the stream progresses. Moreover,
$r_{n}$ is trivially upper-bounded by $d$, as each row is embedded in
$\mathbb{R}^{d}$.

Algorithm 2 keeps a set of samples $\\{M_{y}\\}$, where each $M_{y}$ stores a
sample of rows of $A$. We refer to any sample $M_{y}$ that stores exactly one
row as a singleton. As seen by Lines 19-20, any non-singletons are not used to
build the coreset $(Q_{n},w_{n})$. We first prove that every singleton is
drawn from the distribution required by Theorem 2, namely that $a_{i}$ is
sampled with probability $s_{n}(a_{i})/r_{n}$. In what follows we let
$M_{y}^{(n)}$ denote the state of $M_{y}$ after row $a_{n}$ is processed.

######  Lemma 4.

For any $i\in[n]$,
$Pr(M_{y}^{(n)}=\\{a_{i}\\}:|M_{y}^{(n)}|=1)=s_{n}(a_{i})/r_{n}$

###### Proof.

Let $\gamma_{\ell}=Pr(a_{i}\in
M_{y}^{(n)})=\frac{s_{n}(a_{\ell})}{s_{n}(a_{\ell})+r_{n}}$ and define
$\xi=\prod_{\ell=1}^{n}(1-\gamma_{\ell})$. Observe that
$Pr(M^{(n)}_{y}=\\{a_{i}\\})=\xi\frac{\gamma_{i}}{1-\gamma_{i}}=\xi
s_{n}(a_{i})/r_{n}$. To condition upon the event that $M_{y}^{(n)}$ contains
only a single element, we divide this probability by
$Pr(|M_{y}^{(n)}|=1)=\sum_{\ell=1}^{n}Pr(M^{(n)}_{y}=\\{p_{\ell}\\})$ to
obtain $s_{n}(a_{i})/\sum_{\ell=1}^{n}s_{n}(a_{\ell})$. The result then
follows from Lemma 3. ∎

Each sample $M_{y}$ should have a size concentrated around $1$ with high
probability. If the size is too far away from $1$, there will not be enough
singletons to build a coreset. Also, if the expected size is too large, the
algorithm will require too much space.

######  Lemma 5.

The expected value of $|M_{y}^{(n)}|$ is $1$.

###### Proof.

As in Lemma 6, define
$\gamma_{\ell}=\frac{s_{n}(a_{\ell})}{s_{n}(a_{\ell})+r_{n}}$. Observe that
$s_{n}(a_{\ell})\geq 0$ implies $\gamma_{\ell}\leq s_{n}(a_{\ell})/r_{n}$. It
follows from Line 17 that $Pr(a_{\ell}\in M_{y})=\gamma_{\ell}\leq
s_{n}(a_{\ell})/r_{n}$. The expected value of $|M_{y}|$ is therefore at most
$\sum_{\ell=1}^{n}\frac{1}{r_{n}}s_{n}(a_{\ell})=1$. ∎

We now show that any $M_{y}$ will be a singleton with probability at least
$\frac{1}{4}$. This is essential for showing that, in aggregate, there will be
at least $m$ singletons (Lemma 7) so that we can build a coreset.

######  Lemma 6.

For any $y\in Y$, $P(|M^{(n)}_{y}|=1)\geq\frac{1}{4}$.

###### Proof.

Markov’s inequality to Lemma 5 yields $Pr(|M_{y}|\geq 2)\leq\frac{1}{2}$.

$\displaystyle P(|M_{y}|=1)$
$\displaystyle=\sum_{\ell=1}^{n}P(M_{y}=\\{a_{\ell}\\})$
$\displaystyle=\sum_{\ell=1}^{n}\gamma_{\ell}\prod_{z\neq\ell}(1-\gamma_{z})$
$\displaystyle=\sum_{\ell=1}^{n}\frac{\gamma_{\ell}}{1-\gamma_{\ell}}\prod_{z=1}^{n}(1-\gamma_{z})$
$\displaystyle=\frac{1}{r_{n}}\left(\sum_{\ell=1}^{n}s_{n}(a_{\ell})\right)\left(\prod_{z=1}^{n}(1-\gamma_{z})\right)$
$\displaystyle=Pr(|M_{y}|=0)$

Decomposing $1=Pr(|M_{y}|=0)+Pr(|M_{y}|=1)+Pr(|M_{y}|\geq 2)$, we substitute
to obtain $1\leq 2Pr(|M_{y}|=1)+\frac{1}{2}$. The result follows. ∎

Theorem 2 guarantees that a coreset can be constructed provided that we have
at least $m$ singletons. As seen on Line 19, $|\Gamma_{n}|$ is the number of
singletons after processing row $a_{n}$.

######  Lemma 7.

$|\Gamma_{n}|\geq m$ with probability at least $1-\delta/2$.

###### Proof.

We see from Line 19 that $|\Gamma_{n}|$ is a sum of $|Y|$ independent
Bernoulli trials, each which succeeds with probability at least $\frac{1}{4}$
by Lemma 6. By a Chernoff bound,
$Pr(|\Gamma_{n}|\leq\frac{1}{2}|Y|\frac{1}{4})\leq e^{-|Y|/32}$. We note that
$|Y|/32=m/4\geq\ln(2/\delta)$. Plugging this into the Chernoff bound yields
the result. ∎

In terms of space consumption, Algorithm 2 stores $\Psi_{n}$ ($d$ rows),
$Z_{n}$ ($r_{n}\leq d$ rows), and the $\\{M^{(n)}_{y}\\}_{y\in Y}$. These
samples, of random size, are the dominating factor. The next lemma bounds
their aggregate size with high probability.

######  Lemma 8.

Algorithm 2 stores $O(\frac{d}{\epsilon^{2}}(\log^{2}d+\log\frac{1}{\delta}))$
rows with probability $1-\delta/2$.

###### Proof.

Lemma 5 implies that $\sum_{y\in Y}|M_{y}^{(n)}|=|Y|=8m$. Let the random
variable $X_{n}$ denote the space (in rows) used by all
$\\{M^{(n)}_{y}\\}_{y\in Y}$ after row $a_{n}$ arrives. $X_{n}=\sum_{y\in
Y}|M^{(n)}_{y}|$ is a sum of $|Y|n$ independent Bernoulli trials, each event
being $a_{i}\in M^{(n)}_{y}$ for some $1\leq i\leq n$ and $y\in Y$. We have
the Chernoff bound that $Pr(X_{n}\geq(1+\eta)\mu)\leq
e^{-\eta^{2}\mu/(2+\eta)}$ for any $\eta\geq 1$ where $\mu=E[X_{n}]$. Using
$\eta=1$, this yields that $X_{n}<16m$ with probability at least
$1-e^{-m/3}<\delta/2$. Substitute the value for $m$ from Line 1 to finish the
proof. ∎

###### Proof of Theorem 4.

For correctness, we will apply Theorem 2 to the output $(Q_{n},w_{n})$. The
total sensitivity $t=r_{n}\leq d$ by Lemma 3. The weighting is correct (Line
22). It remains to show that
$|Q_{n}|\geq\frac{cd}{\epsilon^{2}}\left(\log_{2}^{2}d+\ln\frac{1}{\delta}\right)$.
Since $|Q_{n}|=|\Gamma_{n}|$, the result follows with probability $1-\delta/2$
by combining Lemma 7 and Line 1.

As for update time, the dominating factor is computing the Thin SVD on Line 1
which can be done in $O(d^{2})$ time. Then Lemma 8 completes the proof of the
theorem for subspaces. The reduction from affine subspaces to proper subspaces
can be found in Section 4 of [12]. ∎

##  8 Experiments

(a) $k=3,d=4$, error

(b) $k=3,d=4$, time

(c) $k=3,d=4$, time log

(d) $k=7,d=8$, error

(e) $k=7,d=8$, time

(f) $k=7,d=8$, time log

(g) $k=14,d=15$, error

(h) $k=14,d=15$, time

(i) $k=14,d=15$, time log

(j) $k=29,d=30$, error

(k) $k=29,d=30$, time

(l) $k=29,d=30$, time log

Figure 4: Error and time comparison between two methods of streaming on full
JL transform of Wikipedia, for different values of $k$ and $d$.

We then run experimental results that we summarize in this section.

### Wikipedia Dataset

We created a document-term matrix of Wikipedia (parsed enwiki-latest-pages
-articles.xml.bz2-rss.xml from [14]), i.e. sparse matrix with 4624611 rows and
100k columns where each cell $(i,j)$ equals the value of how many appearances
the word number $j$ has in article number $i$. We use a standard dictionary of
the 100k most common words in Wikipedia [2].

In order to compact the data into a small $d$, one applied on it a Johnson-
Lindenstrauss (JL; see [11]) transform: We multiplied this each chunk from the
BOW matrix by a randomized matrix of $100K$ rows and $d$ columns, and got a
dense matrix of $n$ rows and $d$ columns.

### Tree system

We implemented a tree system that separates the $n$ points of the data into
chunks of a desired size of coreset, called $m$. It uses consecutive chunks of
the data, merge each pair of them, and uses a desired algorithm in order to
reduce their dimensionality to a half. The process is described well in [8].
The result is a top coreset of the whole data, in a size of $d$. We built such
a system. Each streaming chunk is in the size of $d$, thus we had
$log(n/d)=22$ floors.

### Algorithms.

We ran JL-Wiki two streaming methods: The one described at ”Tree system”, and
the new method, implementation of Algorithm 2, labeled as ”New Streaming”. We
implemented Algorithm 1 and our streaming algorithm; See Algorithm 2. The
algorithms run on the data blocks of the streaming tree are three:

  1. 1.

A determinstic algorithm, appears in the proof of Theorem 5 of [4], that
guarantees a coreset with an error of $\epsilon$ in a size of
$O(\frac{k}{\epsilon^{2}})$ (Labeled as ”CNW”).

  2. 2.

A non-uniform sampling algorithm, Algorithm 1 of [12], that guarantees a tight
bound of sensitivity for any $k$ and exact sensitivity for $d=k-1$. Sampling
points according to their sensitivities guarantees a coreset with an error of
$\epsilon$ in a size of $O(\frac{d\log_{2}{d}}{\epsilon^{2}}).$ (Labeled as
”Sensitivity Sampling”).

  3. 3.

A uniform sampling method (Labeled as ”Uniform Sampling”).

All algorithms were implemented in Python 3.6 via the Numpy library. The ”New
Streaming” results were averaged over 10 experiments. We ran four experiments
with the following parameterization:

  * •

k=3, d=4

  * •

k=7, d=8

  * •

k=14, d=15

  * •

k=29, d=30

### Hardware.

A desktop, with an Intel i7-6850K CPU @ 3.60GHZ 64GB RAM.

### Results.

We compared the error received for the different algorithms. We show the
results in Figure 4 in $x$-logarithmic scale since the floors’ sizes of the
old streaming method differ multiplicatively. In the old streaming, for every
floor, we concatenated the leaves of the floor and measured the error between
this subset to the original data. The error we determined was calculated by
the formula $\frac{\left\lVert A-AV_{C}^{T}V_{C}\right\rVert^{2}-\left\lVert
A-AV_{A}^{T}V_{A}\right\rVert^{2}}{\left\lVert
A-AV_{A}^{T}V_{A}\right\rVert^{2}}$, where $A$ is the recieved data matrix,
$V_{A}$ received by SVD on A, and $V_{C}$ received by SVD on the top leaf
recieved from steaming $A$; See 4(a),4(d),4(g),4(j). We also measured running
times of each input size. The are showed in linear scale on
4(b),4(e),4(h),4(k), and in logarithmic scale on 4(c),4(f),4(i),4(l)

### Discussion.

One can notice in Figures 4 that the error is relatively similar for the new
streaming as the streaming tree methods and as expected lower than the error
of the Uniform Sampling. In addition, running times of the new method are
shorter in a scale or two than the streaming tree’s blocks methods, and
usually even shorter than those of Uniform Sampling.

## References

  * [1] Vladimir Braverman, Dan Feldman, Harry Lang, and Daniela Rus.  Streaming coreset constructions for m-estimators.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, September 20-22, 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, pages 62:1–62:15, 2019.
  * [2] Dan Church.  https://gist.github.com/h3xx/1976236, March 2012.
  * [3] Michael Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu.  Dimensionality reduction for k-means clustering and low rank approximation.  STOC ’15, page 163–172, 2015.
  * [4] Michael B Cohen, Jelani Nelson, and David P Woodruff.  Optimal approximate matrix product in terms of stable rank.  arXiv preprint arXiv:1507.02268, 2015.
  * [5] Michael B. Cohen and Richard Peng.  Lp row sampling by lewis weights.  In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’15, page 183–192, New York, NY, USA, 2015. Association for Computing Machinery.
  * [6] Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, and David P. Woodruff.  Fast approximation of matrix coherence and statistical leverage.  J. Mach. Learn. Res., 13(1):3475–3506, December 2012.
  * [7] Dan Feldman and Michael Langberg.  A unified framework for approximating and clustering data.  In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC ’11, page 569–578, New York, NY, USA, 2011. Association for Computing Machinery.
  * [8] Dan Feldman, Morteza Monemizadeh, Christian Sohler, and David P Woodruff.  Coresets and sketches for high dimensional subspace approximation problems.  In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 630–649. Society for Industrial and Applied Mathematics, 2010.
  * [9] Dan Feldman, Melanie Schmidt, and Christian Sohler.  Turning big data into tiny data: Constant-size coresets for k-means, pca and projective clustering.  In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’13, page 1434–1453, USA, 2013. Society for Industrial and Applied Mathematics.
  * [10] Dan Feldman, Mikhail Volkov, and Daniela Rus.  Dimensionality reduction of massive sparse datasets using coresets.  In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 2766–2774, 2016.
  * [11] William B Johnson and Joram Lindenstrauss.  Extensions of lipschitz mappings into a hilbert space.  Contemporary mathematics, 26(189-206):1, 1984.
  * [12] Alaa Maalouf, Adiel Statman, and Dan Feldman.  Tight sensitivity bounds for smaller coresets.  arXiv preprint arXiv:1907.01433, 2019.
  * [13] Lloyd Trefethen and David Bau III.  Numerical Linear Algebra.  SIAM, 1997.
  * [14] Wikimedia.  https://dumps.wikimedia.org/enwiki/latest/, June 2019.


# New fixed-circle results related to $F_{c}$-contractive and
$F_{c}$-expanding mappings on metric spaces

Nabil MLAIKI1, NİHAL ÖZGÜR2 and NİHAL TAŞ2 1Department of Mathematics and
General Sciences, Prince Sultan University, Riyadh, Saudi Arabia.
<EMAIL_ADDRESS><EMAIL_ADDRESS>2Balıkesir University, Department of
Mathematics, 10145 Balıkesir, TURKEY<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

The fixed-circle problem is a recent problem about the study of geometric
properties of the fixed point set of a self-mapping on metric (resp.
generalized metric) spaces. The fixed-disc problem occurs as a natural
consequence of this problem. Our aim in this paper, is to investigate new
classes of self-mappings which satisfy new specific type of contraction on a
metric space. We see that the fixed point set of any member of these classes
contains a circle (or a disc) called the fixed circle (resp. fixed disc) of
the corresponding self-mapping. For this purpose, we introduce the notions of
an $F_{c}$-contractive mapping and an $F_{c}$-expanding mapping. Activation
functions with fixed circles (resp. fixed discs) are often seen in the study
of neural networks. This shows the effectiveness of our fixed-circle (resp.
fixed-disc) results. In this context, our theoretical results contribute to
future studies on neural networks.

###### Key words and phrases:

Fixed point, fixed circle, fixed disc.

###### 2010 Mathematics Subject Classification:

Primary 47H10; Secondary 54H25.

##  1\. Introduction

In the last few decades, the Banach contraction principle has been generalized
and studied by different approaches such as to generalize the used contractive
condition (see [1], [4], [5], [6], [7], [8], [11], [18], [19] and [26] for
more details) and to generalize the used metric space (see [2], [3], [9],
[12], [14], [17], [25], [27] and [28] for more details). Recently, some fixed-
circle theorems have been introduced as a geometrical direction of
generalization of the fixed-point theorems (see [20], [21], [22] and [23] for
more details).

Let $(X,d)$ be a metric space and $f$ be a self-mapping on $X$. First, we
recall that the circle $C_{u_{0},\rho}=\left\\{u\in
X:d(u,u_{0})=\rho\right\\}$ is a fixed circle of $f$ if $fu=u$ for all $u\in
C_{u_{0},\rho}$ (see [20]). Similarly, the disc $D_{u_{0},\rho}=\left\\{u\in
X:d(u,u_{0})\leq\rho\right\\}$ is called a fixed disc of $f$ if $fu=u$ for all
$u\in D_{u_{0},\rho}$. There are some examples of self-mappings such that the
fixed point set of the self-mapping contains a circle (or a disc). For
example, let us consider the metric space $\left(\mathbb{C},d\right)$ with the
metric

$d\left(z_{1},z_{2}\right)=\left|x_{1}-x_{2}\right|+\left|y_{1}-y_{2}\right|+\left|x_{1}-x_{2}+y_{1}-y_{2}\right|,$
(1.1)

defined for the complex numbers $z_{1}=x_{1}+iy_{1}$ and $z_{2}=x_{2}+iy_{2}$.
We note that the metric defined in (1.1) is the metric induced by the norm
function

$\left\|z\right\|=\left\|x+iy\right\|=\left|x\right|+\left|y\right|+\left|x+y\right|\text{,}$

(see Example 2.4 in [24]). The circle $C_{0,1}$ is seen in the following
figure which is drawn using Mathematica [31]. Define the self-mapping $f_{1}$
on $\mathbb{C}$ as follows$:$

$f_{1}z=\left\\{\begin{array}[]{ccc}z&;&x\leq 0,y\geq 0\text{ or }x\geq
0,y\leq 0\\\ -y+\frac{1}{2}+i\left(-x+\frac{1}{2}\right)&;&x>0,y>0\\\
-y-\frac{1}{2}+i\left(-x-\frac{1}{2}\right)&;&x<0,y<0\end{array}\right.\text{,}$

for each $z=x+iy\in\mathbb{C}$, then clearly, the fixed point set of $f_{1}$
contains the circle $C_{0,1}$, that is, $C_{0,1}$ is a fixed circle of
$f_{1}$. Therefore, the study of geometric properties of the fixed point set
of a self-mapping seems to be an interesting problem in case where the fixed
point is non unique.

Figure 1. The graph of the circle $C_{0,1}$.

On the other hand, fixed points of self-mappings play an important role in the
study of neural networks. For example, in [16], it was pointed out that fixed
points of a neural network can be determined by fixed points of the employed
activation function. If the global input-output relationship in a neural
network can be considered in the framework of Möbius transformations, then the
existence of one or two fixed points of the neural network is guaranteed (see
[10] for basic algebraic and geometric properties of Möbius transformations).
Some possible applications of theoretical fixed-circle results to neural
networks have been investigated in the recent studies [20] and [23].

Next, we remind the reader of the following theorems on a fixed circle.

######  Theorem 1.1.

[20] Let $(X,d)$ be a metric space and consider the map

$\varphi:X\rightarrow\left[0,\infty\right)\text{,
}\varphi(u)=d(u,u_{0})\text{,}$ (1.2)

for all $u\in X$. If there exists a self-mapping $f:X\rightarrow X$ satisfying

$(C1)$ $d(u,fu)\leq\varphi(u)-\varphi(fu)$

and

$(C2)$ $d(fu,u_{0})\geq\rho$,
for each $u\in C_{u_{0},\rho}$, then the circle $C_{u_{0},\rho}$ is a fixed
circle of $f$.

######  Theorem 1.2.

[20] Let $(X,d)$ be a metric space and consider the map $\varphi$ as defined
in $($1.2$)$. Also, assume that $f:X\rightarrow X$ satisfies the following
conditions:

$(C1)^{\ast}$ $d(u,fu)\leq\varphi(u)+\varphi(fu)-2\rho$

and

$(C2)^{\ast}$ $d(fu,u_{0})\leq\rho$,
for each $u\in C_{u_{0},\rho}$, then the circle $C_{u_{0},\rho}$ is a fixed
circle of $f$.

######  Theorem 1.3.

[20] Let $(X,d)$ be a metric space and consider the map $\varphi$ as defined
in $($1.2$)$. Also, assume that $f:X\rightarrow X$ satisfies the following
conditions:

$(C1)^{\ast\ast}$ $d(u,fu)\leq\varphi(u)-\varphi(fu)$

and

$(C2)^{\ast\ast}$ $hd(u,fu)+d(fu,u_{0})\geq\rho$,
for each $u\in C_{u_{0},\rho}$ and some $h\in\left[0,1\right)$, then the
circle $C_{u_{0},\rho}$ is a fixed circle of $f$.

######  Theorem 1.4.

[23] Let $(X,d)$ be a metric space and assume that the mapping
$\varphi_{\rho}:\mathbb{R}^{+}\cup\left\\{0\right\\}\rightarrow\mathbb{R}$ be
defined by

$\varphi_{\rho}(x)=\left\\{\begin{array}[]{ccc}x-\rho&;&x>0\\\
0&;&x=0\end{array}\right.\text{,}$ (1.3)

for all $x\in\mathbb{R}^{+}\cup\left\\{0\right\\}$. If there exists a self-
mapping $f:X\rightarrow X$ satisfying

  1. (1)

$d(fu,u_{0})=\rho$ for each $u\in C_{u_{0},\rho}$,

  2. (2)

$d(fu,fv)>\rho$ for each $u,v\in C_{u_{0},\rho}$ and $u\neq v$ ,

  3. (3)

$d(fu,fv)\leq d(u,v)-\varphi_{\rho}(d(u,fu))$ for each $u,v\in
C_{u_{0},\rho}$,

then the circle $C_{u_{0},\rho}$ is a fixed circle of $f$.

This manuscript is structured as follows; in Section 2, we give some
generalizations of Theorems 1.1, 1.2 and 1.3. In Section 3, we present the
definitions of an “$F_{c}$-contraction” and an “$F_{c}$-expanding map” where
we prove new theorems on a fixed circle. In section 4, we consider the fixed
point sets of some activation functions frequently used in the study of neural
networks with a geometric viewpoint. This shows the effectiveness of our
fixed-circle results. In section 5, we present some open problems for future
works. Our results show the importance of the geometry of fixed points of a
self-mapping when the fixed point is non unique.

##  2\. New Fixed-Circle Theorems for Some Contractive Mappings

First, we give a fixed-circle theorem using an auxiliary function.

######  Theorem 2.1.

Let $(X,d)$ be a metric space, $f$ be a self-mapping on $X$ and the mapping
$\theta_{\rho}:\mathbb{R}\rightarrow\mathbb{R}$ be defined by

$\theta_{\rho}(x)=\left\\{\begin{array}[]{ccc}\rho&;&x=\rho\\\
x+\rho&;&x\neq\rho\end{array}\right.\text{,}$

for all $x\in\mathbb{R}$ and $\rho\geq 0$. Suppose that

  1. (1)

$d(fu,u_{0})\leq\theta_{\rho}(d(u,u_{0}))+Ld(u,fu)$ for some
$L\in\left(-\infty,0\right]$ and each $u\in X$,

  2. (2)

$\rho\leq d(fu,u_{0})$ for each $u\in C_{u_{0},\rho}$,

  3. (3)

$d(fu,fv)\geq 2\rho$ for each $u,v\in C_{u_{0},\rho}$ and $u\neq v$,

  4. (4)

$d(fu,fv)<\rho+d(v,fu)$ for each $u,v\in C_{u_{0},\rho}$ and $u\neq v$,

then $f$ fixes the circle $C_{u_{0},\rho}$.

###### Proof.

Let $u\in C_{u_{0},\rho}$ be an arbitrary point. By the conditions (1) and
(2), we have

$d(fu,u_{0})\leq\theta_{\rho}(d(u,u_{0}))+Ld(u,fu)=\rho+Ld(u,fu)$

and so

$\rho\leq d(fu,u_{0})\leq\rho+Ld(u,fu)\text{. }$ (2.1)

We have two cases.

Case 1. Let $L=0$. Then we find $d(fu,u_{0})=\rho$ by (2.1), that is, we have
$fu\in C_{u_{0},\rho}$. Then $d(u,fu)=0$ or $d(u,fu)\neq 0$. Assume
$d(u,fu)\neq 0$ for $u\in C_{u_{0},\rho}$. Since $u\neq fu$, from the
condition (3), we obtain

$d(fu,f^{2}u)\geq 2\rho\text{.}$ (2.2)

Also using the condition (4), we get

$d(fu,f^{2}u)<\rho+d(fu,fu)$

and hence

$d(fu,f^{2}u)<\rho\text{.}$

which contradicts the inequality (2.2). Therefore, it should be $d(u,fu)=0$
which implies $fu=u$.

Case 2. Let $L\in\left(-\infty,0\right)$. If $d(u,fu)\neq 0$ we get a
contradiction by (2.1). Hence it should be $d(u,fu)=0$.

Thereby, we obtain $fu=u$ for all $u\in C_{u_{0},\rho}$, that is,
$C_{u_{0},\rho}$ is a fixed circle of $f$. In other words, the fixed point set
of $f$ contains the circle $C_{u_{0},\rho}$. ∎

######  Remark 2.2.

Notice that, if we consider the case $L\in\left(-\infty,0\right)$ in the
condition $(1)$ of Theorem 2.1 for $u\in C_{u_{0},\rho}$, then we get

$-Ld(u,fu)\leq\theta_{\rho}(d(u,u_{0}))-d(fu,u_{0})=d(u,u_{0})-d(fu,u_{0})=\varphi(u)-\varphi(fu)\text{
}$

and hence

$-Ld(u,fu)\leq\varphi(u)-\varphi(fu)\text{.}$

For $L=-1$, we obtain

$d(u,fu)\leq\varphi(u)-\varphi(fu)\text{.}$

This means that the condition $(C1)$ $($resp. the condition $(C1)^{\ast\ast})$
is satisfied for this case.

Clearly, the condition $(2)$ of Theorem 2.1 is the same as condition $(C2)$.
On the other hand, if the condition $(2)$ of Theorem 2.1 is satisfied then the
condition $(C2)^{\ast\ast}$ is satisfied. Consequently, Theorem 2.1 is a
generalization of Theorem 1.1 and Theorem 1.3 for the cases
$L\in\left(-\infty,0\right)\setminus\left\\{-1\right\\}$. For the case $L=-1$,
Theorem 2.1 coincides with Theorem 1.1 and it is a special case of Theorem
1.3.

Next, we present some illustrative examples.

######  Example 2.3.

Let $\left(\mathbb{R},d\right)$ be the metric space with the usual metric
$d(x_{1},x_{2})=\left|x_{1}-x_{2}\right|$ and consider the circle
$C_{0,1}=\left\\{-1,1\right\\}$. If we define the self-mapping
$f_{1}:\mathbb{R}\rightarrow\mathbb{R}$ as

$f_{1}x=\left\\{\begin{array}[]{ccc}3x^{2}+x-3&;&x\in\left\\{-1,1\right\\}\\\
0&;&\text{otherwise}\end{array}\right.\text{,}$

for each $x\in\mathbb{R}$, then it is not difficult to see that $f_{1}$
satisfies the hypothesis of Theorem 2.1 for the circle $C_{0,1}$ and
$L=\frac{-1}{2}$. Clearly, $C_{0,1}$ is the fixed circle of $f_{1}$.

######  Example 2.4.

Consider $\left(\mathbb{R},d\right)$ to be the usual metric space and the
circle $C_{0,2}=\left\\{-2,2\right\\}$. Define
$f_{2}:\mathbb{R}\rightarrow\mathbb{R}$ by

$f_{2}x=\left\\{\begin{array}[]{ccc}2&;&x=-2\\\ -2&;&x=2\\\
0&;&\text{otherwise}\end{array}\right.\text{,}$

for each $x\in\mathbb{R}$, then $f_{2}$ does not satisfy the condition $(1)$
of Theorem 2.1 for each $x\in C_{0,2}$ and for any
$L\in\left(-\infty,0\right)$. Also, $f_{2}$ does not satisfy the condition
$(4)$ for each $x\in C_{0,2}$ and for any $L\in\left(-\infty,0\right]$.
Clearly, $f_{2}$ does not fix $C_{0,2}$ and this example shows that the
condition $(4)$ is crucial in Theorem 2.1.

######  Example 2.5.

Consider $\left(\mathbb{R},d\right)$ to be the usual metric space and the
circles $C_{0,1}=\left\\{-1,1\right\\}$ and $C_{0,2}=\left\\{-2,2\right\\}$.
If we define $f_{3}:\mathbb{R}\rightarrow\mathbb{R}$ as

$f_{3}x=\left\\{\begin{array}[]{ccc}x&;&x\in C_{0,1}\cup C_{0,2}\\\
0&;&\text{otherwise}\end{array}\right.\text{,}$

for each $x\in\mathbb{R}$, then $f_{3}$ satisfies the hypothesis of Theorem
2.1 for each of the circles $C_{0,1}$ and $C_{0,2}$ and for any
$L\in\left[-1,0\right]$. Clearly, $C_{0,1}$ and $C_{0,2}$ are the fixed
circles of $f_{3}$.

We give another fixed-circle result.

######  Theorem 2.6.

Let $(X,d)$ be a metric space, $f$ be a self-mapping on $X$ and the mapping
$\theta_{\rho}:\mathbb{R}\rightarrow\mathbb{R}$ be defined by

$\theta_{\rho}(x)=\left\\{\begin{array}[]{ccc}\rho&;&x=\rho\\\
x+\rho&;&x\neq\rho\end{array}\right.\text{,}$

for all $x\in\mathbb{R}$ and $\rho\geq 0$. Suppose that

  1. (1)

$2d(u,u_{0})-d(fu,u_{0})\leq\theta_{\rho}(d(u,u_{0}))+Ld(u,fu)$ for some
$L\in\left(-\infty,0\right]$ and each $u\in X$,

  2. (2)

$d(fu,u_{0})\leq\rho$ for each $u\in C_{u_{0},\rho}$,

  3. (3)

$d(fu,fv)\geq 2\rho$ for each $u,v\in C_{u_{0},\rho}$ and $u\neq v$,

  4. (4)

$d(fu,fv)<\rho+d(v,fu)$ for each $u,v\in C_{u_{0},\rho}$ and $u\neq v$,

then the self-mapping $f$ fixes the circle $C_{u_{0},\rho}.$

###### Proof.

Consider $u\in C_{u_{0},\rho}$ to be an arbitrary point. Using the conditions
(1) and (2), we get

$2d(u,u_{0})-d(fu,u_{0})\leq d(u,u_{0})+Ld(u,fu)\text{,}$
$2\rho-d(fu,u_{0})\leq\rho+Ld(u,fu)$

and

$\rho\leq d(fu,u_{0})+Ld(u,fu)\leq\rho+Ld(u,fu)\text{.}$ (2.3)

Similarly to the arguments used in the proof of Theorem 2.1, a direct
computation shows that the circle $C_{u_{0},\rho}$ is fixed by $f$. ∎

######  Remark 2.7.

Notice that, if we consider the case $L=-1$ in the condition $(1)$ of Theorem
2.6 for $u\in C_{u_{0},\rho}$ then we get

$d(u,fu)\leq\theta_{\rho}(d(u,u_{0}))+d(fu,u_{0})-2d(u,u_{0})=\rho+d(fu,u_{0})-2\rho=\varphi(u)+\varphi(fu)-2\rho\text{.}$

Hence the condition $(C1)^{\ast}$ is satisfied. Also, the condition $(2)$ of
Theorem 2.6 is contained in the condition $(C2)^{\ast}$. Therefore, Theorem
2.6 is a special case of Theorem 1.2 in this case. For the cases
$L\in\left(-\infty,0\right)$, Theorem 2.6 is a generalization of Theorem 1.2.

Now, we give some illustrative examples.

######  Example 2.8.

Consider the usual metric space $\left(\mathbb{R},d\right)$ and the circle
$C_{0,1}=\left\\{-1,1\right\\}$. Define the map
$f_{4}:\mathbb{R}\rightarrow\mathbb{R}$ as

$f_{4}x=\left\\{\begin{array}[]{ccc}\frac{1}{x}&;&u\in\left\\{-1,1\right\\}\\\
2x&;&\text{otherwise}\end{array}\right.\text{,}$

for each $x\in\mathbb{R}$, hence $f_{4}$ satisfies the hypothesis of Theorem
2.6 for $L=-\frac{1}{2}$. Clearly, $C_{0,1}$ is the fixed circle of $f_{4}$.
It is easy to check that $f_{4}$ does not satisfy the condition $(1)$ of
Theorem 2.1 for any $L\in\left(-\infty,0\right]$.

######  Example 2.9.

Consider the usual metric space $\left(\mathbb{R},d\right)$ and the circles
$C_{0,1}=\left\\{-1,1\right\\}$ and $C_{1,2}=\left\\{-1,3\right\\}$. Define
the self-mapping $f_{5}:\mathbb{R}\rightarrow\mathbb{R}$ as

$f_{5}x=\left\\{\begin{array}[]{ccc}x&;&x\in C_{0,1}\cup C_{1,2}\\\ \alpha
x&;&\text{otherwise}\end{array}\right.\text{,}$

for each $x\in\mathbb{R}$ and $\alpha\geq 2$, then $f_{5}$ satisfies the
hypothesis of Theorem 2.6 for $L=0$ and for each of the circles $C_{0,1}$ and
$C_{1,2}$. Clearly, $C_{0,1}$ and $C_{1,2}$ are the fixed circles of $f_{5}$.
Notice that the fixed circles $C_{0,1}$ and $C_{1,2}$ are not disjoint.

Considering Example 2.5 and Example 2.9, we deduce that a fixed circle need
not to be unique in Theorem 2.1 and Theorem 2.6. If a fixed circle is non
unique then two fixed circle of a self-mapping can be disjoint or not. Next,
we prove a theorem where $f$ fixes a unique circle.

######  Theorem 2.10.

Let $(X,d)$ be a metric space and $f:X\rightarrow X$ be a self-mapping which
fixes the circle $C_{u_{0},\rho}$. If the condition

$d(fu,fv)<\max\left\\{d(v,fu),d(v,fv)\right\\}\text{,}$ (2.4)

is satisfied by $f$ for all $u\in C_{u_{0},\rho}$ and $v\in X\setminus
C_{u_{0},\rho}$, then $C_{u_{0},\rho}$ is the unique fixed circle of $f$.

###### Proof.

Let $C_{u_{1},\mu}$ be another fixed circle of $f$. If we take $u\in
C_{u_{0},\rho}$ and $v\in C_{u_{1},\mu}$ with $u\neq v$, then using the
inequality (2.4), we obtain

$\displaystyle d(u,v)$ $\displaystyle=$ $\displaystyle d(fu,fv)$
$\displaystyle<$
$\displaystyle\max\left\\{d(v,fu),d(v,fv)\right\\}=d(u,v)\text{,}$

a contradiction. We have $u=v$ for all $u\in C_{u_{0},\rho}$, $v\in
C_{u_{1},\mu}$ hence $f$ only fixes the circle $C_{u_{0},\rho}.$ ∎

In the following example, we show that the converse of Theorem 2.10 is not
true in general.

######  Example 2.11.

Consider the usual metric space $\left(\mathbb{C},d\right)$ and the circle
$C_{0,\frac{1}{4}}.$ Define $f_{6}$ on $\mathbb{C}$ as follows$:$

$f_{6}z=\left\\{\begin{array}[]{ccc}\frac{1}{16\overline{z}}&\text{if}&z\neq
0\\\ 0&\text{if}&z=0\end{array}\right.\text{,}$

for $z\in\mathbb{C}$, where $\overline{z}$ denotes the complex conjugate of
$z$. It is not difficult to see that $C_{0,\frac{1}{4}}$ is the unique fixed
circle of $f_{6}$ where $f_{6}$ does not satisfy the hypothesis of Theorem
2.10.

Now, we give the following example as an illustration of Theorem 2.10.

######  Example 2.12.

Let $Y=\left\\{-1,0,1\right\\}$ and the metric $d:Y\times
Y\rightarrow\left[0,\infty\right)$ be defined by

$d(u,v)=\left\\{\begin{array}[]{ccc}0&;&u=v\\\
\left|u\right|+\left|v\right|&;&u\neq v\end{array}\right.\text{,}$

for all $u\in Y$. If we consider the self-mapping $f_{7}:Y\rightarrow Y$
defined by

$f_{7}u=0\text{,}$

for any $u\in Y$, then $C_{1,1}=\left\\{0\right\\}$ is the unique fixed circle
of $f_{7}.$

Next, we present the following interesting theorem that involves the identity
map $I_{X}:X\rightarrow X$ defined by $I_{X}(u)=u$ for all $u\in X.$

######  Theorem 2.13.

Let $(X,d)$ be a metric space. Consider the map $f$ from $X$ to itself with
the fixed circle $C_{u_{0},\rho}$. The self-mapping $f$ satisfies the
condition

$d(u,fu)\leq\alpha\left[\max\left\\{d(u,fu),d(u_{0},fu)\right\\}-d(u_{0},fu)\right]\text{,}$
(2.5)

for all $u\in X$ and some $\alpha\in\left(0,1\right)$ if and only if
$f=I_{X}$.

###### Proof.

Let $u\in X$ with $fu\neq u$. By inequality (2.5), if $d(u,fu)\geq
d(u_{0},fu)$, then we get

$d(u,fu)\leq\alpha\left[d(u,fu)-d(u_{0},fu)\right]\leq\alpha d(u,fu)\text{,}$

which leads us to a contradiction due to the fact that
$\alpha\in\left(0,1\right)$. If $d(u,fu)\leq d(u_{0},fu)$, then we find

$d(u,fu)\leq\alpha\left[d(u_{0},fu)-d(u_{0},fu)\right]=0.$

Hence, $fu=u$ and that is $f=I_{X}$ since $u$ is an arbitrary in $X$.

Conversely, $I_{X}$ satisfies the condition (2.5) clearly. ∎

######  Corollary 2.14.

Let $(X,d)$ be a metric space and $f:X\rightarrow X$ be a self-mapping. If $f$
satisfies the hypothesis of Theorem 2.1 $($resp. Theorem 2.6$)$ but the
condition $($2.5$)$ is not satisfied, then $f\neq I_{X}$.

Now, we rewrite the following theorem given in [20].

######  Theorem 2.15.

[20] Let $(X,d)$ be a metric space. Consider the map $f$ from $X$ to itself
which have a fixed circle $C_{u_{0},\rho}$ and $\varphi$ as in $($1.2$)$. Then
$f$ satisfies the condition

$d(u,fu)\leq\frac{\varphi(u)-\varphi(fu)}{h}\text{,}$ (2.6)

for every $u\in Y$ and $h>1$ if and only if $f=I_{X}$.

######  Theorem 2.16.

Let $(X,d)$ be a metric space. Consider the map $f$ from $X$ to itself which
have a fixed circle $C_{u_{0},\rho}$ and $\varphi$ as in $($1.2$)$. Then $f$
satisfies $($2.5$)$ if and only if $f$ satisfies $($2.6$)$.

###### Proof.

The proof follows easily. ∎

##  3\. $F_{c}$-contractive and $F_{c}$-expanding mappings in metric spaces

In this section, we use a different approach to obtain new fixed-circle
results. First, we recall the definition of the following family of functions
which was introduced by Wardowski in [30].

######  Definition 3.1.

[30] Let $\mathbb{F}$ be the family of all functions
$F:(0,\infty)\rightarrow\mathbb{R}$ such that

$(F_{1})$ $F$ is strictly increasing,

$(F_{2})$ For each sequence $\left\\{\alpha_{n}\right\\}$ in
$\left(0,\infty\right)$ the following holds

$\underset{n\rightarrow\infty}{\lim}\alpha_{n}=0\text{ if and only if
}\underset{n\rightarrow\infty}{\lim}F(\alpha_{n})=-\infty\text{,}$

$(F_{3})$ There exists $k\in(0,1)$ such that $\underset{\alpha\rightarrow
0^{+}}{\lim}\alpha^{k}F(\alpha)=0$.

Some examples of functions that satisfies the conditions $(F_{1})$, $(F_{2})$
and $(F_{3})$ of Definition 3.1 are $F(u)=\ln(u)$, $F(u)=\ln(u)+u$,
$F(u)=-\frac{1}{\sqrt{u}}$ and $F(u)=\ln(u^{2}+u)$ (see [30] for more
details).

At this point, we introduce the following new contraction type.

######  Definition 3.2.

Let $(X,d)$ be a metric space and $f$ be a self-mapping on $X$. If there exist
$t>0$, $F\in\mathbb{F}$ and $u_{0}\in X$ such that

$d(u,fu)>0\Rightarrow t+F(d(u,fu))\leq F(d(u_{0},u))\text{,}$

for all $u\in X$, then $f$ is called as an $F_{c}$-contraction.

We note that the point $u_{0}$ mentioned in Definition 3.2 must be a fixed
point of the mapping $f$. Indeed, if $u_{0}$ is not a fixed point of $f$, then
we have $d(u_{0},fu_{0})>0$ and hence

$d(u_{0},fu_{0})>0\Rightarrow t+F(d(u_{0},fu_{0}))\leq
F(d(u_{0},u_{0}))\text{.}$

This is a contradiction since the domain of $F$ is $(0,\infty)$. Consequently,
we obtain the following proposition as an immediate consequence of Definition
3.2.

######  Proposition 3.3.

Let $(X,d)$ be a metric space. If $f$ is an $F_{c}$-contraction with
$u_{0}\in$ $X$ then we have $fu_{0}=u_{0}.$

Using this new type contraction we give the following fixed-circle theorem.

######  Theorem 3.4.

Let $(X,d)$ be a metric space and $f$ be an $F_{c}$-contraction with
$u_{0}\in$ $X$. Define the number $\sigma$ by

$\sigma=\inf\left\\{d(u,fu):u\neq fu,u\in X\right\\}\text{.}$

Then $C_{u_{0},\sigma}$ is a fixed circle of $f$. In particular, $f$ fixes
every circle $C_{u_{0},r}$ where $r<\sigma$.

###### Proof.

If $\sigma=0$ then clearly $C_{u_{0},\sigma}=\left\\{u_{0}\right\\}$ and by
Proposition 3.3, we see that $C_{u_{0},\sigma}$ is a fixed circle of $f$.
Assume $\sigma>0$ and let $u\in C_{u_{0},\sigma}$. If $fu\neq u$, then by the
definition of $\sigma$ we have $d(u,fu)\geq\sigma$. Hence using the
$F_{c}$-contractive property and the fact that $F$ is increasing, we obtain

$F(\sigma)\leq F(d(u,fu))\leq F(d(u_{0},u))-t<F(d(u_{0},u))=F(\sigma)\text{,}$

which leads to a contradiction. Therefore, we have $d(u,fu)=0$, that is,
$fu=u$. Consequently, $C_{u_{0},\sigma}$ is a fixed circle of $f$.

Now we show that $f$ also fixes any circle $C_{u_{0},r}$ with $r<\sigma$. Let
$u\in C_{u_{0},r}$ and assume that $d(u,fu)>0$. By the $F_{c}$-contractive
property, we have

$F(d(u,fu))\leq F(d(u_{0},u))-t<F(r)\text{.}$

Since $F$ is increasing, then we find

$d(u,fu)<r<\sigma.$

But $\sigma=\inf\left\\{d(u,fu):\text{for all }u\neq fu\right\\}$, which leads
us to a contradiction. Thus, $d(u,fu)=0$ and $fu=u$. Hence, $C_{u_{0},r}$ is a
fixed circle of $f$. ∎

######  Remark 3.5.

$1)$ Notice that, in Theorem 3.4, the $F_{c}$-contraction $f$ fixes the disc
$D_{u_{0},\sigma}$. Therefore, the center of any fixed circle is also fixed by
$f$. In Theorem 1.4, the self-mapping $f$ maps $C_{u_{0},\rho}$ into $($or
onto$)$ itself, but the center of the fixed circle need not to be fixed by
$f$.

$2)$ Related to the number of the elements of the set $X$, the number of the
fixed circles of an $F_{c}$-contractive self-mapping $f$ can be infinite
$($see Example 3.8$)$.

We give some illustrative examples.

######  Example 3.6.

Let $X=\left\\{0,1,e^{2},-e^{2},e^{2}-1,e^{2}+1\right\\}$ be the metric space
with the usual metric. Define the self-mapping $f_{8}:X\rightarrow X$ as

$f_{8}u=\left\\{\begin{array}[]{ccc}1&;&u=0\\\
u&;&\text{otherwise}\end{array}\right.\text{,}$

for all $u\in X$. Then the self-mapping $f_{8}$ is an $F_{c}$-contractive
self-mapping with $F=\ln u$, $t=1$ and $u_{0}=e^{2}$. Using Theorem 3.4, we
obtain $\sigma=1$ and $f_{8}$ fixes the circle
$C_{e^{2},1}=\left\\{e^{2}-1,e^{2}+1\right\\}$. Clearly, $\mathbb{C}_{8}$
fixes the disc $D_{e^{2},1}=\left\\{u\in Y:d(u,e^{2})\leq
1\right\\}=\left\\{e^{2},e^{2}-1,e^{2}+1\right\\}$. Notice that $f_{8}$ fixes
also the circle $C_{0,e^{2}}=\left\\{-e^{2},e^{2}\right\\}.$

The converse statement of Theorem 3.4 is not always true as seen in the
following example.

######  Example 3.7.

Let $(X,d)$ be a metric space, $u_{0}\in X$ any point and the self-mapping
$f_{9}:X\rightarrow X$ defined as

$f_{9}u=\left\\{\begin{array}[]{ccc}u&;&d(u,u_{0})\leq\mu\\\
u_{0}&;&d(u,u_{0})>\mu\end{array}\right.\text{,}$

for all $u\in X$ with any $\mu>0$. Then it can be easily seen that $f_{9}$ is
not an $F_{c}$-contractive self-mapping for the point $u_{0}$ but $f_{9}$
fixes every circle $C_{u_{0},r}$ where $r\leq\mu$.

######  Example 3.8.

Let $\left(\mathbb{C},d\right)$ be the usual metric space and define the self-
mapping $f_{10}:\mathbb{C}\rightarrow\mathbb{C}$ as

$f_{10}u=\left\\{\begin{array}[]{ccc}u&;&\left|u\right|<2\\\
u+1&;&\left|u\right|\geq 2\end{array}\right.\text{,}$

for all $u\in\mathbb{C}$. We have $\sigma=\min\left\\{d(u,f_{10}u):u\neq
f_{10}u\right\\}=1$. Then $f_{10}$ is an $F_{c}$-contractive self-mapping with
$F=\ln u$, $t=\ln 2$ and $u_{0}=0\in\mathbb{C}$. Evidently, the number of the
fixed circles of $f_{10}$ is infinite.

Now, to obtain a new fixed-circle theorem, we use the well-known fact that if
a self-mapping $f$ on $X$ is surjective, then there exists a self mapping
$f^{\ast}:X\rightarrow X$ such that the map $(f\circ f^{\ast})$ is the
identity map on $X$.

######  Definition 3.9.

A self-mapping $f$ on a metric space $X$ is called as an $F_{c}$-expanding map
if there exist $t<0$, $F\in\mathbb{F}$ and $u_{0}\in X$ such that

$d(u,fu)>0\Rightarrow F(d(u,fu))\leq F(d(u_{0},fu))+t\text{,}$

for all $u\in X$.

######  Theorem 3.10.

Let $(X,d)$ be a metric space. If $f:X\rightarrow X$ is a surjective
$F_{c}$-expanding map with $u_{0}\in X$, then $f$ has a fixed circle in $X.$

###### Proof.

Since $f$ is surjective, we know that there exists a self-mapping
$f^{\ast}:X\rightarrow X,$ such that the map $(f\circ f^{\ast})$ is the
identity map on $X$. Let $u\in X$ be such that $d(u,f^{\ast}u)>0$ and
$z=f^{\ast}u$. First, notice the following fact

$fz=f(f^{\ast}u)=(f\circ f^{\ast})u=u\text{.}$

Since

$d(z,fz)=d(fz,z)>0\text{,}$

now, by applying the $F_{c}$-expanding property of $f$ we get

$F\left(d(z,fz)\right)\leq F(d(u_{0},fz))+t$

and

$F\left(d(f^{\ast}u,u)\right)\leq F(d(u_{0},u))+t\text{.}$

Therefore, we obtain

$-t+F\left(d(f^{\ast}u,u)\right)\leq F(d(u_{0},u))\text{.}$

Consequently, $f^{\ast}$ is an $F_{c}$-contraction on $X$ with $u_{0}$ as
$-t>0$. Then by Theorem 3.4, $f^{\ast}$ has a fixed circle $C_{u_{0},\sigma}$.
Let $v\in C_{u_{0},\sigma}$ be any point. Using the fact that

$fv=f(f^{\ast}v)=v\text{,}$

we deduce that $fv=v$, that is $v$ is a fixed point of $f$, which implies that
$f$ also fixes $C_{u_{0},\sigma}$, as required. ∎

######  Example 3.11.

Let $X=\left\\{1,2,3,4,5\right\\}$ with the usual metric. Define the self-
mapping $f_{11}:X\rightarrow X$ by

$f_{11}u=\left\\{\begin{array}[]{ccc}2&;&u=1\\\ 1&;&u=2\\\
u&;&u\in\left\\{3,4,5\right\\}\end{array}\right.\text{.}$

$f_{11}$ is a surjective $F_{c}$-expanding map with $u_{0}=4$, $F(u)=\ln u$
and $t=-\ln 2$. We have

$\sigma=\min\left\\{d\left(u,fu\right):u\neq fu,u\in X\right\\}=1$

and the circle $C_{4,1}=\left\\{3,5\right\\}$ is the fixed circle of $f$.

######  Remark 3.12.

If $f$ is not a surjective map, then the result in Theorem 3.10 is not true
everywhen. For example, let $X=\left\\{1,2,3,4\right\\}$ with the usual metric
$d.$ Define the self-mapping $f_{12}:X\rightarrow X$ by

$f_{12}u=\left\\{\begin{array}[]{ccc}2&;&u\in\left\\{1,3\right\\}\\\
1&;&u=2\\\ 4&;&u=4\end{array}\right.\text{.}$

Then, it is easy to check that $f_{12}$ satisfies the condition

$d(u,fu)>0\Rightarrow F(d(u,fu))\leq F(d(u_{0},fu))+t$

for all$\ u\in X$, with $F\left(u\right)=\ln u$, $u_{0}=4$ and $t=-\ln 2$.
Therefore, $f_{12}$ satisfies all the conditions of Theorem 3.10, except that
$f_{12}$ is not surjective. Notice that $\sigma=1$ and $f_{12}$ does not fix
the circle $C_{4,1}$.

##  4\. Fixed point sets of activation functions

Activation functions are the primary neural networks decision-making units in
a neural network and hence it is critical to choose the most appropriate
activation function for neural network analysis [29]. Characteristic
properties of activation functions play an important role in learning and
stability issues of a neural network. A comprehensive analysis of different
activation functions with individual real-world applications was given in
[29]. We note that the fixed point sets of commonly used activation functions
(e.g. Ramp function, ReLU function, Leaky ReLU function) contain some fixed
discs and fixed circles. For example, let us consider the Leaky ReLU function
defined by

$f(x)=\max(kx,x)=\left\\{\begin{array}[]{ccc}kx&;&x\leq 0\\\
x&;&x>0\end{array}\right.\text{,}$

where $k\in\left[0,1\right]$. In [32], the Leaky-Reluplex algorithm was
proposed to verify Deep Neural Networks (DNNs) with Leaky ReLU activation
function (see [32] for more details). Now we consider the fixed point set of
the Leaky ReLU activation function by a geometric viewpoint. Let
$\rho=u_{0}\in\left(0,\infty\right)$ be any positive number and consider the
circle $C_{u_{0},\rho}=\left\\{0,2u_{0}\right\\}$. Then it is easy to check
that the function $f(x)$ satisfies the conditions of Theorem 2.1 for the
circle $C_{u_{0},\rho}$ with $L=0$. Clearly, the circle $C_{u_{0},\rho}$ is a
fixed circle of $f(x)$ and the center of the fixed circle is also fixed by
$f(x)$.

On the other hand, theoretic fixed point theorems have been extensively used
in the study of neural networks. For example, in [15], the existence of a
fixed point for every recurrent neural network was shown and a geometric
approach was used to locate where the fixed points are. Brouwer’s Fixed Point
Theorem was used to ensure the existence of a fixed point. This study shows
the importance of the geometric viewpoint and theoretic fixed point results in
applications. Obviously, our fixed circle and fixed disc results are important
for future studies in the study of neural networks.

##  5\. Conclusion and future works

In this section, we want to bring to the reader’s attention in connection with
the investigation of some open questions. Concerning the geometry of non
unique fixed points of a self-mapping on a metric space, we have obtained new
geometric (fixed-circle or fixed-disc) results. To do this, we use two
different approaches. One of them is to measure whether a given circle is
fixed or not by a self-mapping. Another approach is to find which circle is
fixed by a self-mapping under some contractive or expanding conditions. The
investigation of new conditions which ensure a circle or a disc to be fixed by
a self-mapping can be considered as a future problem. For a self-mapping of
which fixed point set contains a circle or a disc, new contractive or
expanding conditions can also be investigated.

On the other hand, there are some examples of self-mappings which have a
common fixed circle. For example, let $\left(\mathbb{R},d\right)$ be the usual
metric space and consider the circle $C_{0,1}=\left\\{-1,1\right\\}$. We
define the self-mappings $f_{13}:\mathbb{R}\rightarrow\mathbb{R}$ and
$f_{14}:\mathbb{R}\rightarrow\mathbb{R}$ as

$f_{13}x=\left\\{\begin{array}[]{ccc}\frac{1}{x}&;&x\in\left\\{-1,1\right\\}\\\
0&;&\text{otherwise}\end{array}\right.\text{ and
}f_{14}x=\frac{5x+3}{3x+5}\text{,}$

for each $x\in\mathbb{R}$, respectively. Then both the self-mappings $f_{13}$
and $f_{14}$ fixes the circle $C_{0,1}=\left\\{-1,1\right\\}$, that is, the
circle $C_{0,1}=\left\\{-1,1\right\\}$ is a common fixed circle of the self-
mappings $f_{13}$ and $f_{14}$. At this point, the following question can be
left as a future study.

######  Question 5.1.

What is (are) the condition(s) to make any circle $C_{u_{0},\rho}$ as the
common fixed circle for two (or more than two) self-mappings?

Finally, the problems considered in this paper can also be studied on some
generalized metric spaces. For example, the notion of an $M_{s}$-metric space
was introduced in [13].

######  Notation 5.2.

We use the following notations.

1\. $m_{{s}_{u,v,z}}:=min\\{m_{s}(u,u,u),m_{s}(v,v,v),m_{s}(z,z,z)\\}$

2\. $M_{{s}_{u,v,z}}:=max\\{m_{s}(u,u,u),m_{s}(v,v,v),m_{s}(z,z,z)\\}$

######  Definition 5.3.

An $M_{s}$-metric on a nonempty set $Y$ is a function
$m_{s}:Y^{3}\rightarrow\mathbb{R}^{+}$ if for all $u,v,z,t\in Y$ we have

  1. (1)

$m_{s}(u,u,u)=m_{s}(v,v,v)=m_{s}(z,z,z)=m_{s}(u,v,z)\Longleftrightarrow
u=v=z,$

  2. (2)

$m_{{s}_{u,v,z}}\leq m_{s}(u,v,z),$

  3. (3)

$m_{s}(u,u,v)=m_{s}(v,v,u),$

  4. (4)

$\displaystyle(m_{s}(u,v,z)-m_{{s}_{u,v,z}})\leq$
$\displaystyle(m_{s}(u,u,t)-m_{{s}_{u,u,t}})$
$\displaystyle+(m_{s}(v,v,t)-m_{{s}_{v,v,t}})+(m_{s}(z,z,t)-m_{{s}_{z,z,t}}).$

Then the pair $(Y,m_{s})$ is called an $M_{s}$-metric space.

One can consult [13] for some examples and basic notions of an $M_{s}$-metric
space.

In $M_{s}$-metric spaces we define a circle as follow;

$C_{u_{0},\rho}=\\{u\in Y\mid m_{s}(u_{0},u,u)-m_{{s}_{{u_{0},u,u}}}=\rho\\}.$

######  Question 5.4.

Let $(Y,m_{s})$ be an $M_{s}$-metric space, $k>1$ and $f$ be a surjective
self-mapping on $Y$. Let we have

$m_{s}(u,fu,f^{2}u)\leq km_{s}(u_{0},u,fu),$

for every $u\in Y$ and some $u_{0}\in Y$. Does $f$ have point circle on $Y?$

######  Question 5.5.

Let $(Y,m_{s})$ be an $M_{s}$-metric space, $t>0$, $F\in\mathbb{F}$ and $f$ be
a surjective self-mapping on $Y$. Let we have

$m_{s}(u,fu,f^{2}u)>0\Rightarrow F(m_{s}(u,fu,f^{2}u))\geq
F(m_{s}(u_{0},u,fu))+t,$

for every $u\in Y$ and some $u_{0}\in Y$. Does $f$ have a fixed circle on $Y?$

## Acknowledgements

The first author would like to thank Prince Sultan University for funding this
work through research group Nonlinear Analysis Methods in Applied Mathematics
(NAMAM) group number RG-DES-2017-01-17.

## References

  * [1] I. Altun, M. Aslantaş and H. Şahin, Best proximity point results for p-proximal contractions, Acta Math. Hungar. (2020). https://doi.org/10.1007/s10474-020-01036-3
  * [2] T. V. An, N. V. Dung, Z. Kadelburg and S. Radenović, Various generalizations of metric spaces and fixed point theorems, Rev. R. Acad. Cienc. Exactas Fis. Nat. Ser. A Math. RACSAM 109 (2015), no. 1, 175-198.
  * [3] I. A. Bakhtin, The contraction mapping principle in almost metric spaces, Funct. Anal., Gos. Ped. Inst. Unianowsk 30 (1989), 26-37.
  * [4] J. Caristi, Fixed point theorems for mappings satisfying inwardness conditions, Trans. Amer. Math. Soc. 215 (1976), 241-251.
  * [5] S. K. Chatterjea, Fixed point theorem, C. R. Acad. Bulgare Sci. (25) 1972, 727-730.
  * [6] L. B. Ćirić, A generalization of Banach’s contraction principle, Proc. Amer. Math. Soc. 45 (1974), 267-273.
  * [7] B. Djafari Rouhani and S. Moradi, On the existence and approximation of fixed points for Ćirić type contractive mappings, Quaest. Math. 37 (2014), no. 2, 179-189.
  * [8] M. Edelstein, On fixed and periodic points under contractive mappings, J. Lond. Math. Soc. 37 (1962), 74-79.
  * [9] S. Gähler, 2-metrische Räume und ihre topologische Struktur, Math. Nachr. 26 (1963), 115-148.
  * [10] G. A. Jones and D. Singerman, Complex functions: an algebraic and geometric viewpoint. Cambridge university press, 1987\.
  * [11] R. Kannan, Some results on fixed points II, Am. Math. Mon. 76 (1969), 405-408.
  * [12] H. Karayılan, M. Telci, Caristi type fixed point theorems in fuzzy metric spaces, Hacet. J. Math. Stat. 48 (2019), no. 1, 75-86.
  * [13] N. Mlaiki, N. Souayah, K. Abodayeh, T. Abdeljawad, Contraction principles in $M_{s}-$metric spaces, J. Nonlinear Sci. Appl., 10 (2017), 575-582.
  * [14] Z. Mustafa and B. Sims, A new approach to generalized metric spaces, J. Nonlinear Convex Anal. 7 (2006), no. 2, 289-297.
  * [15] L. K. Li, Fixed point analysis for discrete-time recurrent neural networks, In: Proceedings 1992 IJCNN International Joint Conference on Neural Networks, Baltimore, MD, USA, 1992, pp. 134-139 vol.4, doi: 10.1109/IJCNN.1992.227277.
  * [16] D. P Mandic, The use of Möbius transformations in neural networks and signal processing. In Neural Networks for Signal Processing X. Proceedings of the 2000 IEEE Signal Processing Society Workshop (Cat. No. 00TH8501) (Vol. 1, pp. 185-194). IEEE.
  * [17] Z. D. Mitrović and S. Radenović, A common fixed point theorem of Jungck in rectangular _b_ -metric spaces, Acta Math. Hungar. 153 (2017), no.2, 401-407.
  * [18] V. V. Nemytskii, The fixed point method in analysis, Usp. Mat. Nauk 1 (1936), 141-174 (in Russian).
  * [19] M. Olgun, Ö. Biçer T. Alyıldız and İ. Altun, A related fixed point theorem for $F$-contractions on two metric spaces, Hacet. J. Math. Stat. 48 (2019), no. 1, 150-156.
  * [20] N. Y. Özgür and N. Taş, Some fixed-circle theorems on metric spaces, Bull. Malays. Math. Sci. Soc. 42 (4) (2019), 1433-1449.
  * [21] N. Y. Özgür, N. Taş and U. Çelik, New fixed-circle results on $S$-metric spaces, Bull. Math. Anal. Appl. 9 (2017), no. 2, 10-23.
  * [22] N. Y. Özgür and N. Taş, Fixed-circle problem on $S$-metric spaces with a geometric viewpoint, Facta Universitatis. Series: Mathematics and Informatics 34 (3) (2019), 459-472.
  * [23] N. Y. Özgür and N. Taş, Some fixed-circle theorems and discontinuity at fixed circle, AIP Conference Proceedings 1926, 020048 (2018).
  * [24] N. Y. Özgür, Ellipses and similarity transformations with norm functions, Turkish Journal of Mathematics, 42 (6) (2018), 3204-3210.
  * [25] L. Pasicki, A strong fixed point theorem, Topology Appl. 282 (2020), 107300, 18 pp.
  * [26] B. E. Rhoades, A comparison of various definitions of contractive mappings, Trans. Amer. Math. Soc. 226 (1977), 257-290.
  * [27] S. Sedghi, N. Shobe and A. Aliouche, A generalization of fixed point theorems in $S$-metric spaces, Mat. Vesnik 64 (2012), no. 3, 258-266.
  * [28] V. Sihag, R. K. Vats and C. Vetro, A fixed point theorem in $G$-metric spaces via $\alpha$-series, Quaest. Math. 37 (2014), no. 3, 429-434.
  * [29] T. Szandała, Review and Comparison of Commonly Used Activation Functions for Deep Neural Networks, arXiv:2010.09458
  * [30] D. Wardowski, Fixed points of a new type of contractive mappings in complete metric spaces, Fixed Point Theory and Applications 2012, 2012:94.
  * [31] Wolfram Research, Inc., Mathematica, Version 12.0, Champaign, IL (2019).
  * [32] J. Xu, Z. Li, B. Du, M. Zhang and J. Liu, Reluplex made more practical: Leaky ReLU. In 2020 IEEE Symposium on Computers and Communications (ISCC) (pp. 1-7). IEEE, (2020, July).
  * [33] L. Zhang, Implementation of fixed-point neuron models with threshold, ramp and sigmoid activation functions, In: IOP Conference Series: Materials Science and Engineering Vol. 224, No. 1, p. 012054, (2017).