]University of Washington Bothell, Washington, USA

# Phoenix: A Federated Generative Diffusion Model

Fiona Victoria Stanley Jothiraj<EMAIL_ADDRESS>Afra Mashhadi
<EMAIL_ADDRESS>[

###### Abstract

Generative AI has made impressive strides in enabling users to create diverse
and realistic visual content such as images, videos, and audio. However,
training generative models on large centralized datasets can pose challenges
in terms of data privacy, security, and accessibility. Federated learning (FL)
is an approach that uses decentralized techniques to collaboratively train a
shared deep learning model while retaining the training data on individual
edge devices to preserve data privacy. This paper proposes a novel method for
training a Denoising Diffusion Probabilistic Model (DDPM) across multiple data
sources, using FL techniques. Diffusion models, a newly emerging generative
model, show promising results in achieving superior quality images than
Generative Adversarial Networks (GANs). Our proposed method Phoenix is an
unconditional diffusion model that leverages strategies to improve the data
diversity of generated samples even when trained on data with statistical
heterogeneity or Non-IID (Non-Independent and Identically Distributed) data.
We demonstrate how our approach outperforms the default diffusion model in a
FL setting. These results are indicative that high-quality samples can be
generated by maintaining data diversity, preserving privacy, and reducing
communication between data sources, offering exciting new possibilities in the
field of generative AI.

###### keywords:

Federated learning, Generative AI, Diffusion Models, Heterogeneous data

##  1 Introduction

In recent years, Generative AI has emerged as a rapidly growing field of
research and development of innovative tools such as Stable diffusion [1],
Imagen [2], ChatGPT that are used beyond the computer science community.
Generative AI refers to generating high-quality synthetic content using
advanced AI techniques such as natural language processing (NLP), computer
vision (CV), and other fields of machine learning (ML). Conventional AI models
were created to perform classical, regression, or clustering tasks that helped
analyze existing data. What sets generative AI is its distinctive ability to
generate novel content based on the patterns and information learned from the
training data.

Deep generative models (DGMs), a deep learning approach in Generative AI are a
special class of probabilistic neural networks that can estimate the
likelihood of each image or observation to generate new samples based on the
underlying distribution. Commonly used DGM techniques include generative
adversarial networks (GANs), Variational Autoencoders (VAEs), and Diffusion
Models. This method of unsupervised learning has potential applications, like
data augmentation, code generation, text, video and audio synthesis, anomaly
detection, etc [3].

At the same time, pressing data privacy concerns have prompted the development
of a distribution training approach that differs from centralized training.
Federated Learning (FL) [4] aimed to create a decentralized collaborative
learning scenario wherein the user data is trained locally without the need
for data to be transferred to a central server. This privacy-by-design
training technique meant that several edge devices could be trained with rich
representations of global data without any direct data interaction. The
process involves training local data on each client and transmitting the
learned parameters (model weights) from each round of training to the global
model for aggregation. Hence, FL offers the potential to create a high-
performing global model without the need to collect training data in a central
location. However, research has shown that existing GAN models suffer from
heterogeneity challenges of FL paradigm [5] [6].

This paper presents a novel method to train a generative unconditional
diffusion model in a distributed way for creating synthetic images.
Specifically, we aim to address the problem of statistical heterogeneity in FL
when local data is heterogeneous (referred to as non-IID). We first
demonstrate that generated samples’ quality and mode coverage for state-of-
the-art GAN models suffer from heterogeneity in FL. Next, we propose two
strategies to address statistical challenges when designing a diffusion model
in FL, namely Data sharing Strategy and Personalization & Threshold Filtering.
The effectiveness of these strategies is evaluated through experiments to show
the improvement in data quality and mode coverage over GANs. We particularly
utilize unconditional diffusion models that generate data samples without
specific conditioning or external factors such as prompts. These models learn
the underlying probability distribution of the training data and generate new
samples (based on seed value) that resemble the training data. To the best of
our knowledge, no prior work has been done on applying generative diffusion
models in FL.

The algorithm name “Phoenix” is aptly chosen for our approach due to its
transformative nature. Just as how the mythical bird rises from ashes, the
diffusion model can be symbolized by its transition from chaos (pure noise) to
creation (generated data). Our study provides the first step in providing a
promising solution to train diffusion models through FL for image synthesis
tackling the statistical heterogeneity of clients.

This article is outlined as follows: Section 2 presents related works on
generative diffusion models and FL. Section 3 outlines the proposed FL
methodology for handling IID and Non-IID data, along with quantitative
metrics. Section 4 covers implementation, experiments, and results. Finally,
Section 5 discusses limitations, implications, and future directions.

##  2 Related Work

###  2.1 Generative Models

Generative Artificial Intelligence is a new class of AI algorithms that aim to
generate new content or output based on the vast amount of data that it has
been trained on. Researchers have highly sought them due to their
exceptionally high-quality data samples generated by the models. This new
family of models, also known as deep generative models (DGMs), combines the
power of generative models and deep neural networks. One of the first
generative models was proposed in 2014 [7] called the adversarial nets
framework. The framework consists of a generative model that acts against an
adversary discriminative model, which learns to distinguish whether a data
sample is indeed from the original data distribution. It was analogous to a
counterfeit team who produces counterfeit currency notes and tries to get away
with it (i.e. generative model) and the police who detect the counterfeit
currency notes (i.e., discriminative model). Both the generator and
discriminator are deep neural networks, and the output of the generator is fed
as input to the discriminator. During backpropagation, the weights of the
generator are updated through the discriminator’s classification task.

The paper [8] originally introduced the idea of diffusion probabilistic models
that aim to learn how to reverse a gradual multi-step noising or decaying
process. The diffusion probabilistic model or diffusion model is a
parameterized Markov chain that produces samples after finite samples.
Transitions of this chain are taught to learn how to reverse a diffusion
process when the chain gradually adds noise to the data until all information
is destroyed. The DDPM Model [9] shows that extremely high-quality samples
could be generated on the CIFAR-10 and LSUN datasets. Their work solely relied
on predicting the noise found in the image, not the mean, and fixing the
variance of the Gaussian noise in the forward pass. Further improvements on
the DDPM model [10] showed the importance of learning variances of the reverse
diffusion process that allows for sampling with fewer forward passes without
affecting sample quality.

###  2.2 Federated Learning

Federated learning (FL) [4, 11] is an emerging Machine learning technique that
enables ML models to be trained in distributed data on edge devices without
being stored on a central server. In FL, each client retains its local
training dataset, ensuring that data is not transmitted to a central server.
Instead, the clients (or individual devices) are trained on the neural network
models, and only the computed model updates are communicated. The FL technique
can thus significantly reduce the privacy and security risks in comparison to
the traditional centralized technique. As per the White House Report [12], the
FL technique best makes use of principles such as data minimization and
security. While FL offers privacy and security benefits over traditional
methods, it also faces certain challenges. The training data present in
clients are typically personalized and hence not representative of the global
data distribution. This poses a problem of non-IID data, which is described in
detail in section 2.2. Since the clients act as edge devices, there is
typically limited communication, or they are frequently offline; hence, some
devices train faster than others.

After each round of the local model, the computed model weights are sent to
the central server for aggregation. Various model aggregation techniques are
used depending on the nature of the local data and the system behavior such as
FedSGD, FedAvg [4], FedProx [13], QFedAvg [14] and FedOptim [15]. Out of which
FedAvg is mostly used as a benchmark.

Heterogeneity Challenges in FL: It is common in a FL network to have clients
with different data distributions. For instance, each patient’s medical
history can be treated as a distinct dataset in a healthcare dataset. The data
within these datasets is likely to have been drawn from different
distributions. Such forms of data are called Non-IID data or Non-Independent
and identically distributed [16]. Although IID data is the simplest form of
data distribution to deal with, it is unrealistic to assume that the data
present in edge devices is IID since the clients are unique.

Several efforts are being carried out to deal with this highly skewed non-IID
data. Most methods involve data-based, algorithmic, and system-based
approaches [17]. The data-based approach preprocesses client data before
training, such as using data sharing or data augmentation techniques [18].
Algorithmic-based methods employ learning techniques like knowledge
distillation, multi-task learning, and personalization layers. System-based
approaches use client-based clustering methods to better understand
heterogeneous data environments.

Stability Challenges in FL: In recent years, much research has been made to
use GANs in an FL setting to personalize the client tasks and heterogeneous
data distribution problems [19, 20, 21, 22]. However, GANs have limitations
such as mode collapse, convergence issues, and scalability challenges. To
address these drawbacks, Diffusion Models have emerged as a more suitable
approach for generative AI tasks, effectively overcoming these challenges.

##  3 Methodology

###  3.1 Diffusion Model

A denoising diffusion model is a generative model that transforms noisy data,
typically originating from a Gaussian distribution, into high-quality samples
of the desired data distribution. A neural network backed by a U-Net model
architecture [23] is typically used to achieve this. This model learns to
gradually denoise the data, resulting in a proper image.

Figure 1: Directed Graphical Model of Diffusion Model [9]

The two-step process involved in diffusion models is illustrated in Figure 1
and is explained as follows:

Forward diffusion process: Given an image x0, the forward process aims to add
Gaussian noise at each time step t (pre-defined) till an isotropic Gaussian
distribution is achieved. As the step size t increases, the image loses all
its distinguishable features, eventually becoming complete noise.

If $q(x_{0})$ is the real data distribution of real images and a sample image
from this distribution is $x_{0}\sim q(x_{0})$, then the forward diffusion
process can be denoted as $q(x_{t}\mid x_{t-1})$. Gaussian noise is added at
every time step t based on a variance scheduler $\beta$,
$0<\beta_{1}<\beta_{2}<\beta_{3}<....<\beta_{T}<1$ as

$q(x_{t}\mid x_{t-1})=N(x_{t};\sqrt{1-\beta_{t}}x_{t-1},\beta_{t}I)$ (1)

The term $\sqrt{1-\beta_{t}}x_{t-1}$ is the mean of the Gaussian distribution
denoted by $\mu_{t}$ and $\beta_{t}$ is the variance of the Gaussian
distribution denoted by $\sigma_{t}^{2}$ that is based on sampling
$\epsilon\sim N(0,I)$. Hence the next image can be calculated by

$x_{t}=\sqrt{1-\beta_{t}}x_{t-1}+\sqrt{\beta_{t}}\epsilon$ (2)

The forward diffusion process starts with an image $x_{0}$ and adds noise in T
steps $x_{1},...,x_{t},...,x_{T}$ until only pure Gaussian noise remains.

Reverse diffusion process: A neural network (typically U-Net) is trained to
denoise the images containing pure noise till the actual image is retrieved.

Figure 1 illustrates that knowing the conditional distribution $p(x_{t-1}\mid
x_{t})$ allows effortless image reconstruction. However, since this
distribution requires knowledge of all training images, we employ Neural
Networks to learn the approximate conditional probability distribution
$p_{\theta}(x_{t-1}\mid x_{t})$, with $\theta$ representing the learned
parameters. The neural network learns the mean and variance of these
distributions for efficient image recovery and reconstruction.

####  3.1.1 Hyperparameters

  * •

Variance Scheduler: The rate at which noise is added to the images is
controlled by the variance scheduler $\beta$. This pre-defined parameter can
be a constant integer or chosen as a scheduler over T timesteps. Earlier works
[9] employ a linear schedule from $\beta_{1}=10^{-4}$ to $\beta_{T}=0.02$.
However, this linear schedule’s effectiveness is limited for smaller
resolutions like 32 x 32 and 64 x 64, where it introduces excessive noise
without improving sample quality. The improved work [10] introduced a cosine
scheduler with linear drop-off in the middle of the decay process, while
preserving information at the start and end, leading to slower destruction of
useful information and improved accuracy in prediction.

  * •

Diffusion Steps: The number of diffusion steps, denoted as T, determines the
decay process. Prior works [9] used T = 1000, while the improved DDPM [10]
trained models with 4000 steps. To address the time-consuming nature, they
proposed sampling intermediate steps of 25, 50, 100, 1000, etc.

  * •

Learning Rate: The learning rate (lr) regulates the weight update speed during
training. It requires careful selection to avoid sub-optimal solutions (with a
high learning rate) or getting stuck at local minima (with a low learning
rate) during gradient descent.

###  3.2 Phoenix Algorithm

We propose Phoenix, a novel diffusion neural network model that is
specifically designed to be trained in a FL setting. The primary focus of our
work is to explore the implications and effects of utilizing such a model on
two distinct data scenarios: independent and identically distributed (IID)
data and non-IID data. The default Phoenix framework utilizes 10 clients, each
with 100 local epochs and 10 server rounds. The training process involves
splitting the CIFAR-10 dataset into train and test sets, further dividing the
training data among the clients. Clients train locally using diffusion models
with a U-Net backbone architecture. The model weights are averaged in the
global server after 100 local epochs. Gradient descent is employed for weight
updates, with generated image samples saved locally for evaluation. This
iterative process ensures continuous improvement and the generation of high-
quality synthetic data.

####  3.2.1 Data Sharing Strategy

One way to solve the diversity issues faced by Non-IID data is to utilize a
data-sharing strategy that uses a small subset of global data shared between
all devices before FL training. By sharing a small subset of global data, the
overlap of data distribution across clients can be increased, thereby
improving the overall model performance. Prior experiments [18] show that when
using a CIFAR-10 dataset trained on CNN models, they achieved a 30% increase
in test accuracy when using 5% of the globally shared data.

The stepwise process of data sharing strategy for a CIFAR-10 dataset is
explained as follows,

  1. 1.

The CIFAR-10 training set, comprising 50,000 image samples, is divided into
two parts: the Client (C) with 40,000 examples and the Server (S) with 10,000
examples.

  2. 2.

The Client (C) part is split into ten clients chosen as the number of clients
that participate in the FL training process. The partition is usually a case
of 1-class or 2-class non-IID Data. ie. The number of classes in a client is
one or utmost two, which helps simulate the scenario of non-IID Data.

  3. 3.

The Server (S) part is split into ten groups as a globally shared data (G)
based on a factor $\beta$ that is quantified by $\beta=\frac{\left\lvert
G\right\rvert}{\left\lvert C\right\rvert}\times 100\%$. $\beta$ can range from
2.5% to 25%.

  4. 4.

Next, the global warmup model is trained on globally shared data (G) for the
required number of epochs till it reaches the desired accuracy.

  5. 5.

From the globally shared data (G), a fraction of data known as $\alpha$ is
merged with every client part (C) for FL training. $\alpha$ of zero means that
no data from G is shared with client, and $\alpha$ of 100 means that all the
data from G is merged with every client.

####  3.2.2 Personalization layers & Threshold Filtering

Personalization layers: Statistical Heterogeneity [24] i.e., data distribution
is different for different clients and typically impacts the performance of ML
models. The personalization layer-based approach [25] is one popular way of
handling different clients with very different data distributions. It aids in
the customization of models to individual users or devices without
compromising user privacy. To better capture the features/properties each
client learns, the deep neural networks are divided into personalization and
base layers. The base layers are typically co-trained by the clients and take
part in the model aggregation stage, whereas the personalization layers [26]
do not leave the individual clients.

We use U-Net [23], a convolution neural network, as the backbone model
architecture for diffusion models. U-Net contains a total of eight basic
blocks: 4 blocks on the encoder side and 4 on the decoder side. To better
understand the effects of personalization layers, we consider the last basic
block on the decoder side containing convolution layers to be the
personalization layers.

Threshold Filtering: We propose another strategy to improve the overall model
performance in the global model by means of a threshold filtering technique.
In the context of FL, threshold filtering can be used to remove (or)
disconnect underperforming clients from the active training process (Figure
2). Precision and recall are the performance metrics to determine if a client
is performing below optimal levels. Clients that do not meet the pre-
set/average values of the threshold are removed either temporarily or
permanently. This can be achieved in two ways: excluding from a particular
server communication round or removing from the training altogether.

In our method of threshold filtering, we use a warning mechanism to disconnect
clients only if they underperform consistently for more than two local
trainings. By implementing this two-strike approach of threshold filtering,
the FL system can help improve performance, efficiency, and fairness while
still maintaining its privacy and scalability advantages. This method of
threshold filtering technique offers several other benefits as listed below,

  * •

Robustness: We give all clients a second chance and do not penalize clients
immediately for temporary performance drops due to factors such as
fluctuations in data quality.

  * •

Fairness: By allowing underperforming clients to participate in further
training rounds before being removed, there is a fair evaluation of
performance. This eliminates premature exclusion that could arise due to
connection/communication/data issues.

  * •

Dynamic Adaption: The constant monitoring of a FL system helps keep track of
clients’ performance even when the client population or data distribution
changes.

  * •

Improved Global Model Performance: By removing underperforming clients, the
global model performance may be less impacted by noise or biased data.

  * •

Faster Convergence: Underperforming clients in a training process require more
server communication rounds to achieve optimal levels of performance. By
removing such clients, the models are trained on high-quality, relevant data,
thereby training efficient and faster convergence of the model.

  * •

Optimized Resource Utilization: The time and resources spent in training
clients that perform at suboptimal levels can be eliminated, which is a
significant overhead in FL.

Figure 2: Illustration of Personalization layers & Threshold Filtering
strategy in FL setting Step 1: Personalization layers, Step 2: Generate
samples to monitor performance and Step 3: Disconnect underperforming clients

###  3.3 Dataset and Data Preparation

The generative diffusion models were trained on the CIFAR-10 dataset [27]. The
CIFAR-10 dataset consists of 60k samples in 10 different classes of size 32 x
32, split into 50k training images and 10k test images. The Phoenix framework
trains the diffusion models using the 50k samples and evaluates the
performance of these models using the 10k test images. CIFAR-10 is a commonly
chosen benchmark dataset for evaluating neural network models in various
domains.

##### IID Data

The Independent and Identically Distributed (IID) data is simulated during
training. The CIFAR-10 dataset is distributed among the k-clients as the
diversity of image samples in each client is almost equal. Although the
occurrence of IID data distribution in real-world applications is not
practical, this is done to understand the behavior of diffusion model systems.

##### Non-IID Data

There exist three different ways to make data behave non-identically
distributed across clients [28] [29]: feature distribution skew, label
distribution skew and quantity skew. The experiments in Phoenix use label
distribution skew that is given a specific label, each client owns highly
different amounts of samples corresponding to that label. We follow the
distribution suggested by [18] where there are 2 class Non-IID data. A 2-class
non-IID case ensures that each client contains samples belonging to utmost two
classes.

###  3.4 Metrics

Inception score \- The IS score uses the Inception V3 Network pre-trained on
the ImageNet dataset to calculate the single floating point number score to
measure the diversity and fidelity of images.

Fréchet Inception Distance score \- FID [30] measures the Gaussian
distribution between real and generated images.

Precision and Recall \- Precision denotes what fraction of the generated
samples is realistic, and recall measures what fraction of the training set
manifold the generator covers. Both these metrics [31] [32] can effectively
measure the fidelity and diversity of the samples.

Classification Distribution \- We propose using a pre-trained state-of-the-art
classification model [33] LaNet that quotes a top-1 accuracy of 99.03% on the
CIFAR-10 dataset using the NASNet search space. By comparing the
classification results of the generated samples with those from the test set,
we can effectively measure the diversity of generated samples. If the
generated samples are diverse and realistic, we would expect to see a similar
distribution of classes between the two sets (generated and test set).
However, if the generated samples are not as diverse as expected, we would
expect to see a skewed distribution of classes. Using a pre-trained
classification model is an objective measure to evaluate generative models’
performance.

##  4 Results

###  4.1 Baseline Using GANs

We compare our proposed methods of diffusion model trained in a FL setting
with that of GANs. For the purpose of comparison, we chose the GAN
architecture - Deep convolutional generative adversarial networks (DCGAN)
[34]. DCGAN is a good baseline since it is a popular choice of GAN
architectures for image generation tasks. It also addresses several
limitations of the original GAN architecture improving data quality and
stability during training.

We experiment with three different training modes, centralized machine
learning [35] and FL with IID data and FL with Non-IID Data, using DCGAN as
our backbone architecture. We use the CIFAR-10 dataset containing 50,000
training data for these experiments. Pre-processing was performed on all
training images to resize, normalize and convert the images to tensor. All
models were trained using a mini-batch size of 128 and optimized using the
Adam optimizer. We set the learning rate as 0.0002 and the momentum term
$\beta$ as 0.5 to stabilize training. For FL, we used a 2 class Non-IID
simulated data [36] and set the following parameters prior to training: Server
Rounds = 10, Aggregation Strategy = FedAvg, Training Set = 50k samples,
Optimizer = Adam, lr=0.0002, Epochs = 50. The results of the training are
tabulated in Table 1.

Additionally, in order to visualize the coverage of classes from synthesized
data, we perform a classification task on the 10,000 generated samples. An
image classification task using the LaNet model was performed on our generated
sample since this model was also trained on the CIFAR-10 dataset. This open-
source project from Facebook Research has been ranked #17 in image
classification on CIFAR-10 with an accuracy of 99.03, containing over 44.1M
parameters. We compare this against the test set of the CIFAR-10 dataset
containing 10,000 samples with approximately 1000 samples per class, such as
airplanes, cars, birds, cats, deer, dogs, frogs, horses, ships, and trucks.
Our assumption is that the LaNet model’s classification task on these 10,000
samples would also result in the same result - 1000 samples are predicted per
class. This result serves as our baseline, and we aim to match the same
distribution of synthesized images with our proposed models.

Based on our experiment results in Table 1, it appears that the centralized
mode of training outperforms the FL technique in terms of metrics like FID,
IS, Precision, and Recall. Furthermore, it seems that the performance of FL
methods greatly depends on the type of data used. ie. The performance of FL on
non-IID is worse than that with IID data since it is influenced by the uneven
distribution of data across the participating devices. This can be visualized
by the distribution of generated data (10k samples) for different modes as
shown in Figure 4.

The experiments were conducted in the NVIDIA Tesla K80 Accelerator with a
memory size of 12 GB which is optimal for DCGAN training. The overall time to
train the centralized machine learning is approximately 5 hours, whereas the
FL takes approximately 2 hours per server round of training. DCGANs contain
3.5 million parameters in the generator model and 2.7 million parameters in
the discriminator model, totaling to approximately 6.2 million parameters.
This makes GAN models much faster to train and generate samples when compared
to Diffusion Models. However, GAN contains a non-convex optimization problem,
meaning that there are several local optima that the optimization algorithm
can get stuck in. This means that the generator and discriminator models are
unable to converge to a stable solution, and hence the performance can
oscillate or drop off completely (Figure 3).

Original Data from CIFAR-10

Generated samples at Step 500

Generated samples at Step 1000

Generated samples at Step 5000

Generated samples at Step 10000

Generated samples at Step 15000

Generated samples at Step 25000

Generated samples at Step 40000

Figure 3: Samples when training the DCGAN from step 500 to 40000. Each image (except the first one, which is the original test data set from CIFAR-10) Table 1: DCGAN training on CIFAR-10 data Type of Training | FID | IS | Precision | Recall
---|---|---|---|---
Centralized | 0.5632 | 3.9822 $\pm$ 0.2800 | 0.9243 | 0.4951
Federated Learning - IID Data | 1.9219 | 3.4588 $\pm$ 0.2313 | 0.8189 | 0.0744
Federated Learning - 2 Class Non-IID | 6.9550 | 1.5390 $\pm$ 0.0388 | 0.1772 | 0.001
|  |  |  |

###  4.2 Phoenix Algorithm

We conducted experiments by setting up the state-of-the-art Denoising
Diffusion Probabilistic Models (DDPM) [9] [10] in a distributed manner. We use
the hyperparameters and architecture topology as mentioned in their work,

  * •

Four ResNet blocks are used for downsampling

  * •

Four ResNet blocks are used for upsampling

  * •

Cosine schedule and Adam optimizer with Mean Squared Error

  * •

The learning rate is set to $1\times 10^{-4}$

  * •

Performance metrics are computed using 10K samples, as in prior works.

For implementation we use Flower framework [37], along with PyTorch Library,
DCGAN Library [35], Diffusers Library [38]. The experiments were conducted in
the GeForce RTX 2080 Ti with a memory size of 11 GB. The overall time to train
the centralized machine learning is approximately 2 hours/epoch, whereas the
FL takes approximately 11 hours per server round of training. DDPM model
contains nearly 35 million parameters which is six times the size of a DCGAN
model. This makes diffusion models relatively slower to train and generate
samples when compared to GANs. The visual sample quality of a Diffusion Model
trained on the CIFAR-10 dataset is shown in Figure 6. Based on the results of
the experiment in Table 2, it appears that the centralized mode of training
outperforms the federate learning technique in terms of metrics like FID, IS,
Precision, and Recall. Given that the paper focuses on improving the sample
quality of FL methods, we focus on those experiments over that of centralized
methods. Since the performance of 2-class non-iid on FL is significantly
poorer in terms of precision and recall, we propose two potential methods to
improve the performance of the non-IID method when generating synthetic data.

Table 2: Diffusion Model default training on CIFAR-10 dataset Type of Training | FID | IS | Precision | Recall
---|---|---|---|---
Centralized | 0.7842 | 3.9429 $\pm$ 0.1620 | 0.8956 | 0.4717
Federated Learning - IID Data | 0.1106 | 6.0631 $\pm$ 0.3753 | 0.8144 | 0.6628
Federated Learning - 2 Class Non-IID | 0.6351 | 4.5087 $\pm$ 0.3275 | 0.3344 | 0.5453
|  |  |  |

Figure 4: Distribution of generated sample classes based on classification
results from LaNet Model sorted in descending order for DCGAN (left) and
default diffusion model(right)

####  4.2.1 Data Sharing Strategy

The data-sharing strategy is one of the proposed approaches to overcome the
issue of statistical heterogeneity (non-iid) in generative models using FL.
Here, the participating devices share a subset of their data with each other
to create a more representative and diverse dataset prior to training [18].

We divided the CIFAR-10 training dataset (50,000 samples) into a client (C)
and server (S) part, each consisting of 40,000 and 10,000 samples,
respectively. Next, we split the client part into non-overlapping partitions
and randomly assigned these partitions to each participating client containing
two classes of images per client. The server part is split into partitions
(globally shared data G), and only a portion of the partition is used for
global training which is quantified by $\beta$ and can range from 2.5% to 25%.
Once the global warmup model is trained, a fraction of G (quantified by
$\alpha$) is merged with the client part (C) for FL training.

The data-sharing strategy experiment was conducted on ten clients using the
FedAvg aggregation strategy with a Cosine scheduler and 1000 decay steps.
Table 3 shows the results of each round for different values of $\alpha$ and
$\beta$. Here $\beta$ represents the percentage of data from the server part
(S) that was used for training at each client, and $\alpha$ represents the
percentage of data from $\beta$ used for training.

It can be inferred that increasing the percentage of data shared among clients
(i.e., increasing $\beta$) generally leads to lower FID (i.e., better image
quality), and higher IS, Precision and Recall values. However, with the
extreme 2-class non-IID data and a lower $\beta$ of 5%, we can still achieve
high precision and recall of 0.82 and 0.62, respectively, that outperforms the
default training model with precision and recall of 0.33 and 0.54
respectively. This indicates that not much of the globally shared data is
needed to improve the performance of synthesized images.

Moreover, it was observed that the entire server part (C) was not necessary to
distribute to all clients to achieve improved performance. Instead, a random
portion quantified by $\alpha$ could achieve similar performance. Since
$\beta$ = 25% yields the best performant model, we evaluated its combinations
by modifying the value of $\alpha$ ranging from 25% to 100%. By distributing
only 25% (i.e. additional 2.5K samples per client) of the server part (S)
data, we could achieve precision and recall of 0.82 and 0.67, respectively.
Additionally, by increasing the value of $\alpha$ to 100% (additional 10K
samples per client), we achieved the best model through our data-sharing
strategy with a precision and recall of 0.83 and 0.70. These results reveal
that data distribution of class with a $\beta$ = 25 and $\alpha$ = 100
improves by over 30%.

These results suggest that sharing a higher percentage of data among clients
can improve image quality, but increasing the percentage beyond a certain
threshold does not yield significant improvements. However, the optimal values
of $\alpha$ and $\beta$ may vary depending on the specific use case model and
dataset.

Table 3: Data sharing strategy experiment results with ten clients $\boldsymbol{\beta}$ (%) |  $\boldsymbol{\alpha}$ (%) | Server | Client | Test Set | FID | IS | Precision | Recall
---|---|---|---|---|---|---|---|---
5 | 100 | 2K | 6K | 10K | 0.2858 | 6.0624 $\pm$ 0.1583 | 0.8206 | 0.6240
15 | 100 | 6K | 10K | 10K | 0.0653 | 6.3676 $\pm$ 0.1820 | 0.7555 | 0.6930
25 | 100 | 10K | 14K | 10K | 0.0763 | 6.5758 $\pm$ 0.3126 | 0.8303 | 0.7006
25 | 25 | 10K | 6.5K | 10K | 0.2920 | 5.5283 $\pm$ 0.6442 | 0.8186 | 0.6701
25 | 50 | 10K | 9K | 10K | 0.2047 | 5.9563 $\pm$ 0.2638 | 0.8278 | 0.6783
25 | 75 | 10K | 11.5K | 10K | 0.1435 | 6.0122 $\pm$ 0.4829 | 0.8282 | 0.6934
|  |  |  |  |  |  |  |

Figure 5: Distribution of generated sample classes based on classification
results from LaNet Model sorted in descending order for Data Sharing strategy
(left) and Personalization layers & Threshold Filtering strategy (right)

####  4.2.2 Personalization layers & Threshold Filtering

The Phoenix algorithm also leverages personalization and threshold filtering
techniques to tackle statistical heterogeneity. By incorporating
personalization layers during training, the FL model can better adapt to the
participating devices, thereby providing personalized generated content. We
divide the diffusion model into personalization layers and base layers. Since
U-Net is the chosen model architecture for the reverse diffusion process, we
choose the personalization layers from this model. Our experiments designate
the last basic block with convolutional layers as the personalization layers
[39].

Table 4: Diffusion model training with Personalization layers & Threshold Filtering on CIFAR-10 dataset with 2 class Non-IID Client Drop Approach | FID | IS | Precision | Recall
---|---|---|---|---
Lowest Precision | 0.7607 | 5.3639 $\pm$ 0.3971 | 0.5920 | 0.7623
Threshold Precision: 0.7 | 1.2242 | 5.4681 $\pm$ 0.5142 | 0.5599 | 0.7614
Threshold Precision: 0.6 | 4.2548 | 2.6210 $\pm$ 0.1867 | 0.5337 | 0.259
|  |  |  |

Furthermore, in a scenario where the data is non-iid, it is possible that some
samples provided by participating clients do not contribute value to the
global server model. In the context of FL, threshold filtering is a technique
to disconnect clients that exhibit subpar precision and recall during
training. Since our experiments are simulation-based, new samples from clients
are unlikely to be provided during training. Therefore, we permanently
disconnect clients from participation in future rounds rather than temporarily
disconnecting them. The details of our experiments are explained as follows,

  * •

Server Round 1: All clients train in default mode and save the last basic
block as the personalization layer.

  * •

Server Round 2 onwards: Clients retrieve the stored personalization layers
before local training.

  * •

Server Round 5 onwards: Clients generate 1000 samples, compute precision and
recall, and log the metrics for server decisions.

  * •

Warn: Clients with lower precision or below the threshold are marked
separately.

  * •

Monitor and Disconnect: Marked clients were closely monitored and disconnected
if performance remains poor for two consecutive rounds.

The experiment was conducted with ten participating clients for ten server
rounds using the federated aggregation (FedAvg) strategy with a Cosine
scheduler and 1000 decay steps. Table 4 and Figure 5 show the results of
Diffusion model training with Personalization layers & Threshold Filtering on
the CIFAR-10 dataset. The experiment results show that the client drop
approach using the lowest precision yielded the best performance among the
three approaches. This is primarily because the lowest precision approach
provides all clients with equal opportunities for local training and only
disconnects clients with the lowest precision in each server round. On the
other hand, the other two methods employ pre-defined values, which may not be
practical during training since precision and recall tend to fluctuate between
server rounds. Hence, pre-defined value methods are not effective strategies
for improving performance. Furthermore, the addition of personalization layers
during training enhances the model’s ability to adapt to the unique
characteristics of each participating device. This is evident in its overall
performance compared to the default training of diffusion models. The visual
sample quality of a Diffusion Model trained on the CIFAR-10 dataset with
Personalization layers & Threshold Filtering Strategy is shown in Figure 6.

An additional observation that can be made is regarding the distribution of
generated samples for the different methods, as depicted in Figure 4, and
Figure 5. The ideal scenario for generated samples will be if they are closely
aligned with CIFAR-10 Test set line consisting of 10k samples equally
distributed among the 10 classes. However, the unconditional diffusion model
fails to reproduce this ideal scenario. Due to its random seed initialization
for generating images, it is highly improbable for the model to effectively
cover all the classes observed during training. However, we show how our
proposed methods try to minimize the gap between a biased mode coverage and
the ideal flat-line scenario.

Table 5: Performance comparison of generative model training methods using FL for non-IID data Model/Technique | FID | IS | Precision | Recall
---|---|---|---|---
Deep Convolutional GAN (DCGAN) | 6.9550 | 1.5390 | 0.1772 | 0.001
Denoising Diffusion Probabilistic Models (DDPM) | 0.6351 | 4.5087 | 0.5453 | 0.3344
Data Sharing Strategy DDPM - Ours | 0.0763 | 6.5758 | 0.8303 | 0.7006
Personalization & Threshold Filtering DDPM - Ours | 0.7607 | 5.3639 | 0.592 | 0.7623
|  |  |  |

##  5 Discussion

###  5.1 Summary

This paper introduces a novel technique called the Phoenix for training
unconditional diffusion models in a horizontal FL setting, which, to our
knowledge, has not been previously explored. Its primary objective is to
address the issue of mode coverage commonly encountered with non-IID datasets.

Our methods demonstrated superior model performance compared to existing
techniques, such as Deep Convolutional GANs in FL and Diffusion Models in
Centralized Mode. This performance improvement was particularly noticeable in
non-IID data settings, as illustrated in Table 5. An important point to
highlight is that the data-sharing approach achieved a significant performance
boost by sharing a mere 4-5% of the overall data among clients. This minimal
initial data sharing not only led to a significant boost in performance but
also kept the communication overhead at a minimum. The personalization &
threshold filtering techniques outperformed the comparison methods in terms of
precision and recall. However, they did not excel in image quality compared to
the other proposed technique. Further exploration in this area as future work
could unveil areas for improvement.

Figure 6: Generated Samples from Phoenix with Default Diffusion Training, Data
Sharing Strategy, and Personalizing Strategy respectively

###  5.2 Limitation

Sampling Time: Diffusion models have a major drawback in terms of sampling
steps and the long wall-clock time to sample synthetic data [40]. Since
diffusion models are based on a Markov chain of processes that learns to noise
and denoise an image through a fixed number of decay steps T (1000 or 4000),
the same number of steps are required during the inference phase. This means
that nearly 1000 steps are required to generate one image, which is
substantially slower than GANs. Although a large number of steps are used to
generate high-quality data in a controlled manner, it also comes with inherent
disadvantages like increased computation complexity and longer processing
times. However, several techniques [41, 42, 43] are used to speed up the
notoriously slow diffusion models that could be explored for future work.

Hardware Limitation: On-device training due to FL of diffusion models provides
better personalization of models and improved user privacy and security.
However, large diffusion models contain over a billion parameters [44], making
it difficult to deploy in resource-constrained edge devices in FL settings.
Our work employs diffusion models containing over 35 million parameters, which
is six times larger than the standard deep convolutional GANs. Some ways to
overcome the increased model size without affecting performance include, model
optimization [44], and compression [45].

###  5.3 Future Work

While this paper has been a start to utilizing unconditional diffusion models
in a FL setting for data privacy, security, and personalization, there are
several avenues for future research and exploration. One direction involves
extending to real-world applications in domains like finance and healthcare,
where data is dispersed across multiple institutions and hence cannot be
stored in a central server. Additionally, the development of robust evaluation
metrics that go beyond just fidelity and diversity to better capture the
novelty and fairness of generated samples is crucial for a comprehensive
assessment of generative models. From an algorithmic standpoint, there is a
need to delve deeper into privacy-preserving techniques such as differential
privacy and encrypted data FL which are exciting areas of research.
Additionally, diffusion models are computationally expensive, making them
difficult to deploy in edge devices as part of FL. Hence, the development of
smaller models or faster inference techniques is one possible example of
future work.

Although the results of generative AI are astonishing, many ethical concerns
exist. There are concerns about intellectual property (IP) and ownership of
generated content. Since generative AI models learn patterns and relationships
from existing data, it is highly likely that copyrighted works are used
without providing credits to the original creator. These ethical
considerations can be addressed through watermarking techniques for
traceability and accountability and by exploring fairness, bias, transparency,
and interpretability aspects of unconditional diffusion models in the context
of FL. These investigations will help shape ethical guidelines and best
practices for the responsible deployment of generative models in FL settings.

## References

  *   * Rombach et al. [2022] Rombach, R., Blattmann, A., Lorenz, D., Esser, P., Ommer, B.: High-resolution image synthesis with latent diffusion models. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10684–10695 (2022)
  * Saharia et al. [2022] Saharia, C., Chan, W., Saxena, S., Li, L., Whang, J., Denton, E.L., Ghasemipour, K., Gontijo Lopes, R., Karagol Ayan, B., Salimans, T., et al.: Photorealistic text-to-image diffusion models with deep language understanding. Advances in Neural Information Processing Systems 35, 36479–36494 (2022)
  * Bond-Taylor et al. [2022] Bond-Taylor, S., Leach, A., Long, Y., Willcocks, C.G.: Deep generative modelling: A comparative review of VAEs, GANs, normalizing flows, energy-based and autoregressive models. IEEE Transactions on Pattern Analysis and Machine Intelligence 44, 7327–7347 (2022) https://doi.org/10.1109/tpami.2021.3116668
  * McMahan et al. [2017] McMahan, B., Moore, E., Ramage, D., Hampson, S., Arcas, B.A.: Communication-efficient learning of deep networks from decentralized data. In: Artificial Intelligence and Statistics, pp. 1273–1282 (2017). PMLR
  * Zhang et al. [2021] Zhang, Y., Qu, H., Chang, Q., Liu, H., Metaxas, D., Chen, C.: Training federated gans with theoretical guarantees: A universal aggregation approach. arXiv preprint arXiv:2102.04655 (2021)
  * Google [2022] Google: Common Problems in GANs, https://developers.google.com/machine-learning/gan/problems (2022)
  * Goodfellow et al. [2020] Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., Bengio, Y.: Generative adversarial networks. Communications of the ACM 63(11), 139–144 (2020)
  * Sohl-Dickstein et al. [2015] Sohl-Dickstein, J., Weiss, E., Maheswaranathan, N., Ganguli, S.: Deep unsupervised learning using nonequilibrium thermodynamics. In: International Conference on Machine Learning, pp. 2256–2265 (2015). PMLR
  * Ho et al. [2020] Ho, J., Jain, A., Abbeel, P.: Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems 33, 6840–6851 (2020)
  * Nichol and Dhariwal [2021] Nichol, A.Q., Dhariwal, P.: Improved denoising diffusion probabilistic models. In: International Conference on Machine Learning, pp. 8162–8171 (2021). PMLR
  * Lo et al. [2021] Lo, S.K., Lu, Q., Wang, C., Paik, H.-Y., Zhu, L.: A systematic literature review on federated machine learning: From a software engineering perspective. ACM Computing Surveys (CSUR) 54(5), 1–39 (2021)
  * Report [2013] Report, W.H.: Consumer data privacy in a networked world: A framework for protecting privacy and promoting innovation in the global digital economy. Journal of Privacy and Confidentiality 4(2) (2013) https://doi.org/10.29012/jpc.v4i2.623
  * Li et al. [2020] Li, T., Sahu, A.K., Zaheer, M., Sanjabi, M., Talwalkar, A., Smith, V.: Federated optimization in heterogeneous networks. Proceedings of Machine learning and systems 2, 429–450 (2020)
  * Li et al. [2019] Li, T., Sanjabi, M., Beirami, A., Smith, V.: Fair resource allocation in federated learning. arXiv preprint arXiv:1905.10497 (2019)
  * Reddi et al. [2020] Reddi, S., Charles, Z., Zaheer, M., Garrett, Z., Rush, K., Konečnỳ, J., Kumar, S., McMahan, H.B.: Adaptive federated optimization. arXiv preprint arXiv:2003.00295 (2020)
  * Hellström et al. [2020] Hellström, H., Silva Jr, J.M.B.d., Amiri, M.M., Chen, M., Fodor, V., Poor, H.V., Fischione, C.: Wireless for machine learning. arXiv preprint arXiv:2008.13492 (2020)
  * Zhu et al. [2021] Zhu, H., Xu, J., Liu, S., Jin, Y.: Federated learning on non-iid data: A survey. Neurocomputing 465, 371–390 (2021)
  * Zhao et al. [2018] Zhao, Y., Li, M., Lai, L., Suda, N., Civin, D., Chandra, V.: Federated learning with non-iid data. arXiv preprint arXiv:1806.00582 (2018)
  * Li et al. [2023] Li, Z., Shao, J., Mao, Y., Wang, J.H., Zhang, J.: Federated learning with gan-based data synthesis for non-iid clients. In: Trustworthy Federated Learning: First International Workshop, FL 2022, Held in Conjunction with IJCAI 2022, Vienna, Austria, July 23, 2022, Revised Selected Papers, pp. 17–32 (2023). Springer
  * Cao et al. [2022] Cao, X., Sun, G., Yu, H., Guizani, M.: Perfed-gan: Personalized federated learning via generative adversarial networks. IEEE Internet of Things Journal (2022)
  * Ghonima [2021] Ghonima, R.: Implementation of gans using federated learning. In: 2021 Tenth International Conference on Intelligent Computing and Information Systems (ICICIS), pp. 142–148 (2021). IEEE
  * Fan and Liu [2020] Fan, C., Liu, P.: Federated generative adversarial learning. In: Pattern Recognition and Computer Vision: Third Chinese Conference, PRCV 2020, Nanjing, China, October 16–18, 2020, Proceedings, Part III 3, pp. 3–15 (2020). Springer
  * Ronneberger et al. [2015] Ronneberger, O., Fischer, P., Brox, T.: U-net: Convolutional networks for biomedical image segmentation. In: Medical Image Computing and Computer-Assisted Intervention–MICCAI 2015: 18th International Conference, Munich, Germany, October 5-9, 2015, Proceedings, Part III 18, pp. 234–241 (2015). Springer
  * Arivazhagan et al. [2019] Arivazhagan, M.G., Aggarwal, V., Singh, A.K., Choudhary, S.: Federated learning with personalization layers. arXiv preprint arXiv:1912.00818 (2019)
  * Nguyen et al. [2022] Nguyen, B.-L., Cao, T.C., Le, B.: Meta-learning and personalization layer in federated learning. In: Nguyen, N.T., Tran, T.K., Tukayev, U., Hong, T.-P., Trawiński, B., Szczerbicki, E. (eds.) Intelligent Information and Database Systems, pp. 209–221. Springer, Cham (2022)
  * Fallah et al. [2020] Fallah, A., Mokhtari, A., Ozdaglar, A.: Personalized federated learning with theoretical guarantees: A model-agnostic meta-learning approach. Advances in Neural Information Processing Systems 33, 3557–3568 (2020)
  * Krizhevsky et al. [2009] Krizhevsky, A., Hinton, G., et al.: Learning multiple layers of features from tiny images (2009)
  * Li et al. [2022] Li, Q., Diao, Y., Chen, Q., He, B.: Federated learning on non-iid data silos: An experimental study. In: 2022 IEEE 38th International Conference on Data Engineering (ICDE), pp. 965–978 (2022). IEEE
  * Li et al. [2020] Li, A., Sun, J., Wang, B., Duan, L., Li, S., Chen, Y., Li, H.: Lotteryfl: Personalized and communication-efficient federated learning with lottery ticket hypothesis on non-iid datasets. arXiv preprint arXiv:2008.03371 (2020)
  * Heusel et al. [2017] Heusel, M., Ramsauer, H., Unterthiner, T., Nessler, B., Hochreiter, S.: Gans trained by a two time-scale update rule converge to a local nash equilibrium. Advances in neural information processing systems 30 (2017)
  * Sajjadi et al. [2018] Sajjadi, M.S., Bachem, O., Lucic, M., Bousquet, O., Gelly, S.: Assessing generative models via precision and recall. Advances in neural information processing systems 31 (2018)
  * Kynkäänniemi et al. [2019] Kynkäänniemi, T., Karras, T., Laine, S., Lehtinen, J., Aila, T.: Improved precision and recall metric for assessing generative models. Advances in Neural Information Processing Systems 32 (2019)
  * Wang et al. [2022] Wang, L., Xie, S., Li, T., Fonseca, R., Tian, Y.: Sample-efficient neural architecture search by learning actions for monte carlo tree search. IEEE Transactions on Pattern Analysis and Machine Intelligence 44(9), 5503–5515 (2022) https://doi.org/10.1109/TPAMI.2021.3071343
  * Radford et al. [2015] Radford, A., Metz, L., Chintala, S.: Unsupervised representation learning with deep convolutional generative adversarial networks. arXiv preprint arXiv:1511.06434 (2015)
  * Karri [2019] Karri, S.T.: DCGAN-CIFAR10-pytorch, GitHub (2019)
  * Jeremy [2020] Jeremy: Non-iid-dataset-for-personalized-federated-learning, GitHub (2020)
  * Beutel et al. [2020] Beutel, D.J., Topal, T., Mathur, A., Qiu, X., Fernandez-Marques, J., Gao, Y., Sani, L., Li, K.H., Parcollet, T., Gusmão, P.P.B., et al.: Flower: A friendly federated learning research framework. arXiv preprint arXiv:2007.14390 (2020)
  * von Platen et al. [2022] Platen, P., Patil, S., Lozhkov, A., Cuenca, P., Lambert, N., Rasul, K., Davaadorj, M., Wolf, T.: Diffusers: State-of-the-art Diffusion Models
  * Nguyen Bao Long [2022] Nguyen Bao Long, C.T.C.: Meta-learning and Personalization Layer in Federated Learning, GitHub (2022)
  * Cao et al. [2022] Cao, H., Tan, C., Gao, Z., Chen, G., Heng, P.-A., Li, S.Z.: A survey on generative diffusion model. arXiv preprint arXiv:2209.02646 (2022)
  * Zhang and Chen [2022] Zhang, Q., Chen, Y.: Fast sampling of diffusion models with exponential integrator. arXiv preprint arXiv:2204.13902 (2022)
  * Vahdat et al. [2021] Vahdat, A., Kreis, K., Kautz, J.: Score-based generative modeling in latent space. Advances in Neural Information Processing Systems 34, 11287–11302 (2021)
  * Xiao et al. [2021] Xiao, Z., Kreis, K., Vahdat, A.: Tackling the generative learning trilemma with denoising diffusion gans. arXiv preprint arXiv:2112.07804 (2021)
  * Chen et al. [2023] Chen, Y.-H., Sarokin, R., Lee, J., Tang, J., Chang, C.-L., Kulik, A., Grundmann, M.: Speed is all you need: On-device acceleration of large diffusion models via gpu-aware optimizations. arXiv preprint arXiv:2304.11267 (2023)
  * Qualcomm [2023] Qualcomm: World’s First On-Device Demonstration of Stable Diffusion on Android


# On the Generation of Long Binary Sequences with Record-Breaking PSL Values

Miroslav Dimitrov , Tsonka Baitcheva , and Nikolay Nikolov This work has been
partially supported by the Bulgarian National Science Fund under contract
number DH 12/8, 15.12.2017.M. Dimitrov and T. Baicheva are with the Institute
of Mathematics and Informatics, Bulgarian Academy of Sciences, Sofia, Bulgaria
<EMAIL_ADDRESS>email:tsonka@math.bas.bg).N. Nikolov is with the
State Agency of National Security, Sofia, Bulgaria.

###### Abstract

Binary sequences are widely used in various practical fields, such as
telecommunications, radar technology, navigation, cryptography, measurement
sciences, biology or industry. In this paper, a method to generate long binary
sequences (LBS) with low peak sidelobe level (PSL) value is proposed. Having
an LBS with length $n$, both the time and memory complexities of the proposed
algorithm are $\mathcal{O}(n)$. During our experiments, we repeatedly reach
better PSL values than the currently known state of art constructions, such as
Legendre sequences, with or without rotations, Rudin-Shapiro sequences or
m-sequences, with or without rotations, by always reaching a record-breaking
PSL values strictly less than $\sqrt{n}$. Furthermore, the efficiency and
simplicity of the proposed method are particularly beneficial to the
lightweightness of the implementation, which allowed us to reach record-
breaking PSL values for less than a second.

###### Index Terms:

Autocorrelation, Binary Sequences, Peak Sidelobe Level (PSL)

##  I Introduction

The practical fields in which binary sequences with low PSL values could be
exploitable are manifold [1]. Despite the widely usage of binary sequences in
radar and sonar pulse compression systems [2], they are further used, for
example, in the estimation of the shape of hemodynamic responses [3], analysis
of visual neurons [4], audio watermarking [5], orthogonal frequency division
multiplexing [6], CDMA systems [7], scrambling algorithms [8], motion tracking
technologies [9] and many others.

Of special interest are those binary sequences possessing low PSL value. Some
strategies for construction of such sequences comprise the Barker codes [10],
Rudin-Shapiro sequences [11][12], maximal length shift register sequences, or
m-sequences [13], Gold codes [14], Kasami codes [15], Weil sequences [16],
Legendre sets [17] and others (see [18]).

M-sequences, Gold codes and Kasami sequences have ideal periodic
autocorrelation functions but have no constraints on the sidelobes of their
aperiodic autocorrelation functions, i.e. their PSL value is not pre-
determined. Same is true for Legendre sets and Rudin-Shapiro sequences.
Furthermore, it is difficult to calculate the growth of the PSL of the
aforementioned families of binary sequences. It is conjectured that the PSL
values of $m$-sequences grow like $\mathcal{O}(\sqrt{n})$, making them one of
the best methods to straightforwardly construct a binary sequences with near-
optimal PSL value. However, as stated in [19]:

> The claim that the PSL of $m$-sequences grows like $\mathcal{O}(\sqrt{n})$,
> which appears frequently in the radar literature, is concluded to be
> unproven and not currently supported by data.

As summarized in [20], during the years a variety of analytical constructions
and computer search methods are developed in order to construct binary
sequences with relatively small or minimal PSL. By an exhaustive search the
minimum values of the PSL for $n\leq 40$[21], $n\leq 48$[22], $n=64$[23],
$n\leq 68$[24], $n\leq 74$[25], $n\leq 80$ [26], $n\leq 82$ [27] and $n\leq
84$ [28] are obtained. The best currently known values for PSL for $85\leq
n\leq 105$ are published in [29], and for some discrete values of $n\geq 106$
in [30][31][32][33].

It appears that the current state of art computer search methods, like CAN
[34], ITROX [35], MWISL-Diag, MM-PSL [36] or DPM [37], could yield better, or
at least not worse PSL values, than the algebraic constructions. However, when
the length of the generated by a given heuristic algorithm binary sequences
rises, so is the overall time and memory complexity of the routine. As
concluded in [32]:

> As an indication of the runtime complexity of our EA111EA stands for
> Evolutionary Algorithm, the computing time is 58009 s or 16.1136 h for
> L=1019. For lengths up to 4096, the computing time required empirically
> shows a seemingly quadratic growth with L.

Thus, the main motivation of this work is to create an efficient and
lightweight algorithm, in terms of time and memory complexity, to address the
heuristic generation of very long binary sequences with near-optimal PSL
values.

##  II Preliminaries

Let $B=(b_{0},b_{1},\cdots,b_{n-1})$ be a binary sequence of length $n>1$,
where $b_{i}\in\\{-1,1\\},0\leq i\leq n-1$. The aperiodic autocorrelation
function of $B$, or AACF, is given by

$C_{u}(B)=\sum_{j=0}^{n-u-1}b_{j}b_{j+u},\ \ for\ u\in\\{0,1,\cdots,n-1\\}.$

$C_{0}(B)$ is called mainlobe and the rest $C_{u}(B)$ for
$u\in\\{1,\cdots,n-1\\}$ are called sidelobe levels. We define the peak
sidelobe level of $B$, or PSL [38], as

$B_{PSL}=\max_{0<u<n}\lvert C_{u}(B)\rvert.$

##  III Some observations about the PSL calculation

Let us denote $C_{n-i-1}(B)$ by $\hat{C}_{i}(B)$. Since this is just a
rearrangement of the sidelobes of $B$, it follows that:

$B_{PSL}=\max_{0<u<n}\lvert C_{u}(B)\rvert=\max_{0\leq
u<n-1}\lvert\hat{C}_{u}(B)\rvert.$

We will graphically represent the calculation of values of $\hat{C}_{i}(B)$
for a binary sequence of length 8 in Figure 1. The $x$-axis indexes represent
the elements of $B=(b_{0},b_{1},\cdots,b_{7})$, while the $y$ axes represents
the elements of $B$ in reverse order, i.e. $(b_{7},b_{6},\cdots,b_{0})$. Each
cell of the graphics corresponds to the product of the provided by the $x$ and
$y$-axis values. To calculate $\hat{C}_{i}(B)=\sum_{j=0}^{i}b_{j}b_{j+n-i-1}$
for some $i$ ($0\leq i\leq 7$), we start from the cell with coordinates
$(b_{i},b_{7})$. Then, by decreasing both indexes of the current cell by $1$
we jump to the next cell $(b_{i-1},b_{6})$ which will be added to the sum. We
continue this process until we reach the cell $(b_{0},b_{7-i})$.

$\kern 0.0pt\kern 2.5pt\kern-5.0pt\left[\kern
0.0pt\kern-2.5pt\kern-5.55557pt\vbox{\kern-0.86108pt\vbox{\vbox{
\halign{\kern\arraycolsep\hfil\@arstrut$\kbcolstyle#$\hfil\kern\arraycolsep&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep&&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep\cr
5.0pt\hfil\@arstrut$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
b_{0}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle b_{1}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle b_{2}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
b_{3}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle b_{4}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle b_{5}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
b_{6}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle b_{7}\\\b_{7}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{gray!70}$*$}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{gray!30}$*$}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{gray!70}$*$}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{gray!30}$*$}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{gray!70}$*$}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{gray!30}$*$}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{gray!70}$*$}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{black!70}$*$}\\\b_{6}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{gray!30}$*$}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{gray!70}$*$}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{gray!30}$*$}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{gray!70}$*$}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{gray!30}$*$}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{gray!70}$*$}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{black!70}$*$}\\\b_{5}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{gray!70}$*$}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{gray!30}$*$}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{gray!70}$*$}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{gray!30}$*$}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{gray!70}$*$}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{black!70}$*$}\\\b_{4}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{gray!30}$*$}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{gray!70}$*$}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{gray!30}$*$}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{gray!70}$*$}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{black!70}$*$}\\\b_{3}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{gray!70}$*$}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{gray!30}$*$}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{gray!70}$*$}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{black!70}$*$}\\\b_{2}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{gray!30}$*$}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{gray!70}$*$}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{black!70}$*$}\\\b_{1}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{gray!70}$*$}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{black!70}$*$}\\\b_{0}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\hbox{\pagecolor{black!70}$*$}\\\$\hfil\kern
5.0pt\crcr}}}}\right]$
Figure 1: A visual interpretation of the sidelobe calculation process, for a
binary sequence with length 8

As the value of the mainlobe $\hat{C}_{7}(B)$ is always 8, we can exclude it
from the PSL calculation. Having this in mind, we can define the PSL of the
binary sequence $B$ as the diagonal in Figure 1 with the highest absolute sum
of its elements compared to all other diagonals, excluding the main one.

Let us denote by $\overline{b_{i}}$ the flipped bit $b_{i}$, i.e.
$\overline{b_{i}}=-b_{i}$ and by $\hat{C}_{i}(B_{j})$ the sidelobe of the
binary sequence $B_{j}$, obtained from $B$ by flipping the bit on position
$j$.

We can further exploit the relations between the value of the sidelobe
$\hat{C}_{i}(\Psi)$ of a given binary sequence $\Psi$ with length $n$, and the
value of the sidelobe $\hat{C}_{i}(\Psi_{f})$, s.t. the binary sequence
$\Psi_{f}$ is equal to the binary sequence $\Psi$ with the bit on position $f$
flipped. We denote as $\Omega_{\Psi}$ the array of all the consequent
sidelobes of $\Psi$, i.e:

$\Omega_{\Psi}=\left[\hat{C}_{0}(\Psi),\hat{C}_{1}(\Psi),\cdots,\hat{C}_{n-2}(\Psi)\right]$

We denote as $\Omega_{\Psi_{f}}$ the array of all the consequent sidelobes of
$\Psi_{f}$, i.e:

$\Omega_{\Psi_{f}}=\left[\hat{C}_{0}(\Psi_{f}),\hat{C}_{1}(\Psi_{f}),\cdots,\hat{C}_{n-2}(\Psi_{f})\right]$

For convenience, we further denote the $i$-th element of a given array $A$ as
$A[i]$. For example, $\Omega_{\Psi}[3]=\hat{C}_{2}(\Psi)$.

The calculation of $\Omega_{\Psi}$, corresponding to some random binary
sequence $\Psi$, is not linear. The time complexity of the trivial
computational approach is $\mathcal{O}(n^{2})$ (two nested for cycles).
However, as shown in Wiener–Khinchin–Einstein theorem [39], the
autocorrelation function of a wide-sense-stationary random process has a
spectral decomposition given by the power spectrum of that process, we can use
one regular and one inverse Fast Fourier Transform (FFT), to achieve a faster
way of calculating $\Omega_{\Psi}$. Despite its time complexity of
$\mathcal{O}(n\log{n})$, its memory complexity is significantly higher than
the trivial computational approach.

By exploiting the observations made in this section, we present an algorithm
which can calculate the array $\Omega_{\Psi_{f}}$, if we hold the array
$\Omega_{\Psi}$ in memory, with time and memory complexity of
$\mathcal{O}(n)$. The pseudo-code of the algorithm is given in Algorithm 1.
The following notations are used:

  * •

$\min_{\left(x,y\right)}$ : returns $x$, if $x\leq y$; otherwise, returns $y$.

  * •

$\max_{\left(x,y\right)}$ : returns $x$, if $x\geq y$; otherwise, returns $y$.

  * •

$x\mathrel{-}=y$ : same as $x=x-y$

  * •

$x\mathrel{*}=y$ : same as $x=x*y$

Algorithm 1 In-memory flip

1:procedure Flip($f,\Psi,\Omega_{\Psi},n$)

2: $\delta_{min}\leftarrow\min_{\left(n-f-1,f\right)}$

3: $\delta_{max}\leftarrow\max_{\left(n-f,f\right)}$

4: if $f\leq\frac{n-1}{2}$ then

5: for $q\in\left[0,\delta_{max}-\delta_{min}-1\right)$ do

6: $\Omega_{\Psi}[\delta_{min}+q]\mathrel{-}=2\Psi[f]\Psi[n-q-1]$

7: end for

8: else

9: for $q\in\left[0,\delta_{max}-\delta_{min}\right)$ do

10: $\Omega_{\Psi}[\delta_{min}+q]\mathrel{-}=2\Psi[f]\Psi[q]$

11: end for

12: end if

13: if $f\leq\frac{n-1}{2}$ then

14: for $q\in\left[0,n-\delta_{max}\right)$ do

15:
$\Omega_{\Psi}[\delta_{max}+q-1]\mathrel{-}=2\Psi[f]\left(\Psi[2f-q]+\Psi[q]\right)$

16: end for

17: else

18: for $q\in\left[0,n-\delta_{max}-1\right)$ do

19: $\Omega_{\Psi}[\delta_{max}+q]\mathrel{-}=$

20: $2\Psi[f]\left(\Psi[\delta_{max}-\delta_{min}+q]+\Psi[n-q-1]\right)$

21: end for

22: end if

23: $\Psi[f]\mathrel{*}=-1$

24:end procedure

The procedure introduced in Algorithm 1 performs an in-place memory update of
$\Omega_{\Psi}$, when a single bit on position $f$ of $\Psi$ is flipped.
Therefore, when the procedure ends, both $\Psi$ and $\Omega$ are transformed
to $\Psi_{f}$ and $\Omega_{\Psi_{f}}$. We will note that the procedure is
reversible, i.e. if an in-place memory update of $\Omega_{\Psi_{f}}$ is made,
when a single bit on position $f$ of $\Psi_{f}$ is flipped, both $\Psi_{f}$
and $\Omega_{\Psi_{f}}$ are transformed back to $\Psi$ and $\Omega_{\Psi}$.

##  IV Algorithm for finding very long binary sequences with low PSL values

The basic ingredients of some heuristic algorithm could be summarized as:

  * •

$\mathcal{A}$: metaheuristic algorithm, like hill climbing, simulated
annealing, tabu search, etc.

  * •

$\mathcal{I}$: search operator, which is used to generate the candidates

  * •

$\mathcal{F}$: fitness function, which is used to compare the candidates

In our previous work [33], we have used shotgun hill climbing as
$\mathcal{A}$, a neighborhood search as $\mathcal{I}$, and the following
fitness function as $\mathcal{F}$:

$F(B)=\sum_{u=1}^{n-1}{\mathopen{|}C_{u}(B)\mathclose{|}^{4}}=\sum_{u=1}^{n-1}{\left(\mathopen{|}{\sum_{j=0}^{n-u-1}b_{j}b_{j+u}}\mathclose{|}\right)^{4}},$

where $B$ is a binary sequence with length $n$. However, using shotgun hill
climbing metaheuristic algorithm for finding very long binary sequences with
low PSL is not time efficient because the number of hops required to reach
some local optimum, grows exponentially when the length of the binary sequence
increases.

Using a neighborhood search to consequently pick the best candidate among all
neighbors could be beneficial in finding LBS with low PSL. However, in the
aspect of very long binary sequences this search strategy is extremely slow.
For example, in the case of a binary sequence with length $2^{16}$, and
$\mathcal{I}$ equivalent to a single flip, in each optimization step we need
to fitness all the $2^{16}$ neighbors of the current state $S$ and to pick the
one with the best score yielded by $\mathcal{F}$. This observation is still
true, even if all the neighbors of $S$ have better scores.

To overcome the disadvantages mentioned above, we choose the following
strategy:

  * •

$\mathcal{A}$: stochastic hill climbing metaheuristic algorithm. We visit a
random neighbor of the current state $S$ and accept it, if it is a better
candidate than $S$. Otherwise, we pick another neighbor of $S$ and repeat the
process.

  * •

$\mathcal{I}$: we choose a single flip as the search operator, so we can
exploit memory and time efficiency of Algorithm 1.

  * •

$\mathcal{F}$: since $\hat{C}(B)$s are rearrangements of the sidelobes of $B$,
we can use the same fitness function $F(B)$ as in [33], i.e:

$F(B)=\sum_{u=0}^{n-2}{\mathopen{|}\hat{C}_{u}(B)\mathclose{|}^{4}=\sum_{u=0}^{n-2}{\hat{C}_{u}(B)}^{4}}$

We need to further address the strategy described in $\mathcal{A}$ of picking
the next candidate, or neighbor, of $S$. Let us consider an approach of
consistently probing $x$ pseudo-randomly chosen neighbors. In case a better
candidate is found, we accept it; otherwise, we try again, until we have
accumulated a total number of $t$ consequent fails. Then, we announce that we
have reached a local optimum. This model can be described by the Bernoulli
distribution. The probability to achieve exactly $r$ successes in $N$ trials
is equal to:

$P\left(X=r\right)={N\choose r}p^{r}q^{N-r},$

where $p$ and $q$ are the probabilities of success and failure respectively,
i.e. $q=1-p$. We can easily calculate $P\left(X=0\right)$:

$P\left(X=0\right)={N\choose 0}p^{0}q^{N-0}=q^{N}=(1-p)^{N}$

We further calculate $P\left(X\geq 1\right)$:

$P\left(X\geq 1\right)=1-P\left(X=0\right)=1-(1-p)^{N}$

Thus, relaying solely on pseudorandom choices of neighbors is not efficient
and there is always a chance to miss the better candidate. We can increase the
probability of finding the eventual better candidate, but that significantly
overhead the optimization process. Missing a better candidate is undesirable
behavior of the optimization process, specially when we are dealing with very
long binary sequences.

The number of neighbors of a binary sequence $B$ with length $n$ is $n$. Let
us denote those neighbors as $i_{1},i_{2},\cdots,i_{n}$, where the $j$-th
neighbor $i_{j}$ is equal to $B$ with flipped bit on position $j$. We suggest
the following simple search strategy::

  1. 1.

we pick a pseudorandomly generated neighbor $i_{r}$

  2. 2.

we consequently try, for all $x\in\left[1,n-1\right]$, the neighbors
$i_{\left(r+x\right)\mod n}$

We want to emphasize on the extreme situation when the local optimum is
already reached, i.e. $k=0$. The suggested search strategy will detect that in
exactly $n$ steps, which is an optimal scenario. Furthermore and more
importantly, we never miss a better candidate, if any, and we keep the non-
deterministic nature of the search routine at the same time.

We suggest Algorithm 2 for finding very long binary sequences with low PSL
which is based on the above described
$\left(\mathcal{A},\mathcal{I},\mathcal{F}\right)$. The following notations
and functions are used in the pseudo-code:

  * •

$\Psi$ is a random (initial) binary sequence.

  * •

$x,y\leftarrow a,b$ is equivalent to the statements $x=a$ and $y=b$.

  * •

$R\left(n\right)$ : a function, which generates a pseudo-random integer number
$\in\left[0,n\right)$.

  * •

$Q\left(x,B,\Omega_{B}\right)$ : a function, which makes $x$ flips at random
bit positions in $B$. We pass $\Omega_{B}$ as argument, so we can use the in-
place memory function $Flip$. We apply this function to escape the local
minimum, when we are stuck in such.

  * •

beacon : we further implant a beacon in the cost function $F$, so we can
simultaneously calculate the PSL of the given binary sequence. Such approach
adds a negligible overhead, if any, to the cost function routine.

Algorithm 2 An algorithm for binary sequences PSL optimization

1:BestCost, Cost $\leftarrow$ $F(\Omega_{\Psi})$, 0

2:isGImpr, isLImpr $\leftarrow$ True, False

3:while true do

4: if isGImpr then

5: r $\leftarrow$ R(n)

6: for $i\in\left[0,n\right)$ do

7: $Flip\left(\left(r+i\right)\%n,\Psi,\Omega_{\Psi},n\right)$

8: Cost $\leftarrow F(\Omega_{\Psi})$ $\triangleright$ * the beacon is here *

9: if BestCost $>$ Cost then

10: BestCost $\leftarrow$ Cost

11: isLImpr $\leftarrow$ True

12: break

13: else

14: $Flip\left(\left(r+i\right)\%n,\Psi,\Omega_{\Psi},n\right)$

15: end if

16: end for

17: if isLImpr then

18: isGImpr, isLImpr $\leftarrow$ True, False

19: continue

20: else

21: isGImpr $\leftarrow$ False

22: end if

23: else

24: r $\leftarrow$ R(4)

25: Q(1+r, $\Psi$, $\Omega_{\Psi}$)

26: isGImpr, isLImpr $\leftarrow$ True, False

27: end if

28:end while

##  V On the complexity of Algorithm 2

We emphasize that the complexity of Algorithm 2 mainly depends on the
complexity of Algorithm 1, because in each iteration during the optimization
process, Algorithm 1 is called twice, in case the new candidate is worse than
the current one, and once, if the new candidate is better. The in-memory flip
function applied in Algorithm 1 passes only once through $\Omega_{\Psi}$
array, without creating any memory overheads, to reach time and memory
complexities of $\mathcal{O}(n)$. The same observation is true for the simple
cost function $F$ \- it passes only once through $\Omega_{\Psi}$ to sum all
quadrupled values of its elements. The function $Q$ is a random number of
calls of $F$ (between 1 and 4). The remaining part of Algorithm 2 consists of
a simple automata, which rules the continuous optimization process. Therefore,
both time and memory complexities of Algorithm 2 are $\mathcal{O}(n)$.

##  VI Results

We have implemented Algorithm 2 by using the C language and a mid-range
computer station. Given the linear time and memory complexity of the
algorithm, we were able to repeatedly generate binary sequences with record-
breaking PSL values for less than a second. As stated in [32], the time
required to reach a PSL value 26, for a binary sequence with length 1019, is
58009 seconds or 16.1136 hours. For comparison, by using Algorithm 2, we reach
this value for less than a second.

We present the results achieved by Algorithm 2, for binary sequences with
lengths $x^{2}$ for $x\in\left[18,44\right]$, compared with the currently
known state of art algorithms found in the literature, like CAN [34], ITROX
[35], MWISL-Diag, MM-PSL [36], DPM [37], 1bCAN [40]. We will refer to this
collection of algorithms as collection A. We want to emphasize, that the
differences between the proposed algorithm with algorithms from collection A
are manifold. For example, we do not use converging functions, mini regular or
quadratic optimization problems, floating-based arithmetic. Furthermore, the
provided algorithm does not suffer from an unique navigation trace through the
sequence search space. The experiments were based on 12 instances of each
algorithm (each ran to a distinct thread of the processor). Furthermore, the
lifetime of our algorithm is restricted to 1 minute. As shown in Figure 2, we
significantly outperform the best results achieved by state of art algorithms.
In fact, for some of the lengths, less than a second was needed to reach a
record-breaking PSL.

Figure 2: Comparison to other state of the art algorithms known in literature

In contrast to some other state of the art algorithms, the computing
complexity of the algorithm presented in this work does not grow
quadratically. Maybe this is the reason for the lack of published results for
binary sequences of lengths greater than $2^{12}$. Nevertheless, the results
with which we can further compare are $m$-sequences. However, such sequences
exists only for lengths $2^{n}-1$, $n\geq 1,n\in N$.

In Table I we present the best PSL values of binary m-sequences with length
$n$ (with or without rotation), yielded by some primitive polynomial of degree
$n$ over $GF(2)$ from [41] denoted by $\mathbb{M}^{\mathbb{F}}_{n}$ and the
binary sequences generated by Algorithm 2 denoted by $\mathbb{A}_{n}$ for
lengths $2^{n}-1$ and $13\leq n\leq 17$. As it can be seen from Table I, our
results significantly outperform the best results achieved by m-sequences.

TABLE I: Reached PSL values compared to known results from m-sequences exhaustive search $n$ | $2^{n}-1$ | $\mathbb{M}^{\mathbb{F}}_{n}$ | $\mathbb{A}_{n}$
---|---|---|---
13 | 8191 | 85 | 77
14 | 16383 | 125 | 115
15 | 32767 | 175 | 171
16 | 65535 | 258 | 254
17 | 131071 | 363 | 360

##  VII Conclusions

In this paper we present an efficient heuristic algorithm for finding very
long binary sequences with record-breaking PSL values. Since the time and
memory complexities of the suggested algorithm are both $\mathcal{O}(n)$, we
were able to construct binary sequences with record-breaking PSL values for
less than a second.

## References

  * [1] S. W. Golomb and G. Gong, _Signal design for good correlation: for wireless communication, cryptography, and radar_. Cambridge University Press, 2005.
  * [2] J. J. Kroszczynski, “Pulse compression by means of linear-period modulation,” _Proceedings of the IEEE_ , vol. 57, no. 7, pp. 1260–1266, 1969.
  * [3] G. T. Buracas and G. M. Boynton, “Efficient design of event-related fmri experiments using m-sequences,” _Neuroimage_ , vol. 16, no. 3, pp. 801–813, 2002.
  * [4] R. C. Reid, J. Victor, and R. Shapley, “The use of m-sequences in the analysis of visual neurons: linear receptive field properties,” _Visual neuroscience_ , vol. 14, no. 6, pp. 1015–1027, 1997.
  * [5] N. Cvejic, A. Keskinarkaus, and T. Seppanen, “Audio watermarking using m-sequences and temporal masking,” in _Proceedings of the 2001 IEEE Workshop on the Applications of Signal Processing to Audio and Acoustics (Cat. No. 01TH8575)_. IEEE, 2001, pp. 227–230.
  * [6] C. Tellambura, “Use of m-sequences for ofdm peak-to-average power ratio reduction,” _Electronics Letters_ , vol. 33, no. 15, pp. 1300–1301, 1997\.
  * [7] S. Ulukus and R. D. Yates, “Optimum multiuser detection is tractable for synchronous cdma systems using m-sequences,” _IEEE Communications Letters_ , vol. 2, no. 4, pp. 89–91, 1998.
  * [8] Y. Zhou, K. Panetta, and S. Agaian, “An image scrambling algorithm using parameter bases m-sequences,” in _2008 International Conference on Machine Learning and Cybernetics_ , vol. 7. IEEE, 2008, pp. 3695–3698.
  * [9] R. Xiao, C. Harrison, K. D. Willis, I. Poupyrev, and S. E. Hudson, “Lumitrack: low cost, high precision, high speed tracking with projected m-sequences,” in _Proceedings of the 26th annual ACM symposium on User interface software and technology_ , 2013, pp. 3–12.
  * [10] R. H. Barker and W. Jackson, “Group synchronization of binary digital systems in Communication Theory,” _Academic Press, New York_ , pp. 273–287, 1953\.
  * [11] W. Rudin, “Some theorems on fourier coefficients,” _Proceedings of the American Mathematical Society_ , vol. 10, no. 6, pp. 855–859, 1959.
  * [12] H. S. Shapiro, “Extremal problems for polynomials and power series,” Ph.D. dissertation, Massachusetts Institute of Technology, 1952.
  * [13] S. W. Golomb _et al._ , _Shift register sequences_. Aegean Park Press, 1967.
  * [14] R. Gold, “Optimal binary sequences for spread spectrum multiplexing (Corresp.),” _IEEE Transactions on Information Theory_ , vol. 13, no. 4, pp. 619–621, 1967.
  * [15] T. Kasami, “Weight distribution formula for some class of cyclic codes,” _Coordinated Science Laboratory Report no. R-285_ , 1966.
  * [16] J. J. Rushanan, “Weil sequences: A family of binary sequences with good correlation properties,” in _2006 IEEE International Symposium on Information Theory_. IEEE, 2006, pp. 1648–1652.
  * [17] A. Pott, _Finite geometry and character theory_. Springer, 2006.
  * [18] N. Levanon and E. Mozeson, _Radar signals_. John Wiley & Sons, 2004.
  * [19] J. Jedwab and K. Yoshida, “The peak sidelobe level of families of binary sequences,” _IEEE transactions on information theory_ , vol. 52, no. 5, pp. 2247–2254, 2006.
  * [20] M. A. Nasrabadi and M. H. Bastani, “A survey on the design of binary pulse compression codes with low autocorrelation,” in _Trends in Telecommunications Technologies_. IntechOpen, 2010.
  * [21] J. Lindner, “Binary sequences up to length 40 with best possible autocorrelation function,” _Electronics letters_ , vol. 11, no. 21, pp. 507–507, 1975.
  * [22] J. Baden and M. Cohen, “Optimal peak sidelobe filters for biphase pulse compression,” in _IEEE International Conference on Radar_. IEEE, 1990, pp. 249–252.
  * [23] G. Coxson and J. Russo, “Efficient exhaustive search for optimal-peak-sidelobe binary codes,” _IEEE Transactions on Aerospace and Electronic Systems_ , vol. 41, no. 1, pp. 302–308, 2005.
  * [24] A. Leukhin and E. Potehin, “Binary sequences with minimum peak sidelobe level up to length 68,” _arXiv preprint arXiv:1212.4930_ , 2012.
  * [25] A. N. Leukhin and E. N. Potekhin, “Optimal peak sidelobe level sequences up to length 74,” in _2013 European Radar Conference_. IEEE, 2013, pp. 495–498.
  * [26] Leukhin, Anatolii N and Potekhin, Egor N, “Exhaustive search for optimal minimum peak sidelobe binary sequences up to length 80,” in _International Conference on Sequences and Their Applications_. Springer, 2014, pp. 157–169.
  * [27] A. Leukhin and E. Potekhin, “A Bernasconi model for constructing ground-state spin systems and optimal binary sequences,” in _Journal of Physics: Conference Series_ , vol. 613, no. 1. IOP Publishing, 2015, p. 012006.
  * [28] A. Leukhin, N. Parsaev, V. Bezrodnyi, and N. Kokovihina, “The exhaustive search for optimum minimum peak sidelobe binary sequences,” _Bulletin of the Russian Academy of Sciences: Physics_ , vol. 81, no. 5, pp. 575–578, 2017\.
  * [29] C. J. Nunn and G. E. Coxson, “Best-known autocorrelation peak sidelobe levels for binary codes of length 71 to 105,” _IEEE transactions on Aerospace and Electronic Systems_ , vol. 44, no. 1, pp. 392–395, 2008.
  * [30] A. Dzvonkovskaya and H. Rohling, “Long binary phase codes with good autocorrelation properties,” in _2008 International Radar Symposium_. IEEE, 2008, pp. 1–4.
  * [31] K. L. Du, W. H. Wu, and W. H. Mow, “Determination of long binary sequences having low autocorrelation functions,” Jul. 23 2013, uS Patent 8,493,245.
  * [32] W. H. Mow, K.-L. Du, and W. H. Wu, “New evolutionary search for long low autocorrelation binary sequences,” _IEEE Transactions on aerospace and electronic systems_ , vol. 51, no. 1, pp. 290–303, 2015.
  * [33] M. Dimitrov, T. Baitcheva, and N. Nikolov, “Efficient generation of low autocorrelation binary sequences,” _IEEE Signal Processing Letters_ , vol. 27, pp. 341–345, 2020.
  * [34] H. He, P. Stoica, and J. Li, “Designing unimodular sequence sets with good correlations—including an application to mimo radar,” _IEEE Transactions on Signal Processing_ , vol. 57, no. 11, pp. 4391–4405, 2009.
  * [35] M. Soltanalian and P. Stoica, “Computational design of sequences with good correlation properties,” _IEEE Transactions on Signal processing_ , vol. 60, no. 5, pp. 2180–2193, 2012.
  * [36] J. Song, P. Babu, and D. P. Palomar, “Sequence design to minimize the weighted integrated and peak sidelobe levels,” _IEEE Transactions on Signal Processing_ , vol. 64, no. 8, pp. 2051–2064, 2015.
  * [37] M. A. Kerahroodi, A. Aubry, A. De Maio, M. M. Naghsh, and M. Modarres-Hashemi, “A coordinate-descent framework to design low psl/isl sequences,” _IEEE Transactions on Signal Processing_ , vol. 65, no. 22, pp. 5942–5956, 2017.
  * [38] R. Turyn _et al._ , “Sequences with small correlation,” in _Error correcting codes_. Wiley New York, 1968, pp. 195–228.
  * [39] N. Wiener, _Extrapolation, interpolation, and smoothing of stationary time series_. The MIT press, 1964.
  * [40] R. Lin, M. Soltanalian, B. Tang, and J. Li, “Efficient design of binary sequences with low autocorrelation sidelobes,” _IEEE Transactions on Signal Processing_ , vol. 67, no. 24, pp. 6397–6410, 2019.
  * [41] D. Dmitriev and J. Jedwab, “Bounds on the growth rate of the peak sidelobe level of binary sequences,” _Advances in Mathematics of Communications_ , vol. 1, no. 4, p. 461, 2007.