# Designing Binary Sequence Set with Optimized Correlation Properties via ADMM
Approach

Jiangtao Wang

###### Abstract

In this paper, we design low correlation binary sequences favorable in
wireless communication and radar applications. First, we formulate the
designing problem as a nonconvex combination optimization problem with
flexible correlation interval; second, by relaxing constraints and introducing
auxiliary variables, the original minimization problem is equivalent to a
consensus continuous optimization problem; third, to achieve its good
approximate solution efficiently, we propose the distributed executable
algorithms based on alternating direction method of multipliers (ADMM);
fourth, we prove that the proposed ADMM algorithms can converge to some
stationary point of the approximate problem. Moreover, the computational
complexity analysis is considered. Simulation results demonstrate that the
proposed ADMM approaches outperform state-of-the-art ones in either
computational cost or selection of correlation interval of the designed binary
sequences.

###### Index Terms:

Binary sequence, auto/cross-correlation, Box ADMM, convergence/complexity
analysis.

##  I Introduction

CONSTANT modulus sequences with good correlation play a fundamental role in
modern communication systems [1]–[3]. These sequences are widely used in a
variety of applications, such as power control [4], channel estimation [5],
[6], synchronization [7], signal detection and separation [8], and mitigation
of interference [9], etc. Among these sequences, binary sequences, such as
$m$-sequences [10], Kasami code [11], Gold code [12], Barker code [13], Bent
code [14], etc., have been widely studied due to their simplicity of
implementation and high-energy efficiency.

Generally speaking, perfect correlation sequences are desired in communication
systems when their autocorrelation values are zero for all shifts different
from zero and corss-correllation values are zero for every shift. It is known
that these perfect unitary sequences do not exist and this is the main
challenge to construct zero-correlation sequences limited by bounds [3]. For
Baker codes, Storer and Turyn proved that there are no sequences for odd
$N\geq 13$ [15] and except $N=4$, no other perfect period binary sequences
exist with $N<548964900$ [16]. Therefore, zero correlation zone (ZCZ)
sequence, whose correlation values within a zone are zero, are proposed in
[17] and and so do low correlation zone (LCZ) sequences in [18]. In fact, the
construction of low correlation binary sequences is a well-known computational
problem.

At the early stage, exhaustive search method is the main tool in the
construction of short sequence with ideal correlation properties. The authors
in [19] used the trace function to construct cascaded Gordon-Mills-Welch (GMW)
sequence with low autocorrelation and three valued cross-correlation. The
authors in [20] presented five new classes of binary sequences of period
$2^{N}-1$ with ideal autocorrelation by extensive computer search. Based on
the framework of exhaustive search algorithm, authors in [21] customized the
fast method to construct binary sequences with low autocorrelations. In [22],
the author adopted a hybrid approach combining simulated annealing approach
with a traditional iterative code selection algorithm to design orthogonal
polyphase sequence sets. The authors in [23] proposed an iterated variable
depth search algorithm to search binary sequences with integrated sidelobe
level (ISL) and low peak sidelobe level (PSL). Owing to the exponential size
$\mathcal{O}(2^{N})$ of the configuration space, above exhaustive search
methods are limited to design short sequences.

Pseudo-Noise (PN) sequences generated from Feedback Shift Registers (FSR) can
be designed as long sequences. A kind of these sequences, $m$-sequences, are
easily generated using linear FSR with length $2^{N}-1$. Many sequences, such
as Gold code, Kasami code, GMW sequence are derived from $m$-sequences. But
the disadvantage of these sequences is that they are relatively small in
number [24]. Interleaved technique is another method used to analyse and
design sequences with good correlation [25]. Its key idea is construct long
sequences from short ones [26],[27]. More literature on this area can be found
in [28]-[30] and the references therein. This kind of computational design
method is simple to implement, but it can only be designed for sequences with
length of $2^{N}-1$ or $2^{N}$, which leads to its lack of flexibility.

The limitations motivated the researchers to perform analytical construction
method to design sequences. In recent years, a large number of literatures
related to constant modulus sequences design have emerged (see [31]–[35] and
references therein). As a special case of that, the study of discrete sequence
also attracts many researchers. The authors in [36] bridged the gap between
the exhaustive search method and the analytical constructions method, and
proposed a construction method which can be accomplished in polynomial time.
The authors in [37] formulated the sequence sets design as a quadratically
constrained quadratic program problem and proposed an algorithm based on
semidefinite program (SDP) relaxation and randomized projection technique to
tackle it. An efficient coordinate-descent framework method was proposed to
design sequences with good ISL/PSL for MIMO radars and communication systems
in [38],[39]. Due to element-wise optimization, this method has the drawback
of low efficiency. In [40],[41], the authors formulated the sequence design
with similarity constraint as quadratic optimization problem, the Serial
Iterative Algorithm (SIA) [40] and Alternating Direction Penalty Method (ADPM)
algorithm [41] are proposed successively. The authors in [42] adopt the
effective alternating direction method of multipliers (ADMM) to design
discrete phase sequence with desired minimized sidelobes. Majorization-
Minimization (MM) technique is also considered to tackle the quartic objective
function. However, this method has the disadvantage of relatively high
computational complexity.

In this paper, we focus on designing binary sequence sets with good
correlation properties with low complexity algorithm. The main contributions
of this paper are as follows.

1) In order to meet the needs of various scenarios, this paper establishes the
discrete Pareto-optimal model to minimize of the ISL and PSL on the basis of
previous work [38][39]. In addition, this paper considers a correlation
interval of interest, which can be a single shift, a segment, or a collection
of them. Compared with the existing works, the model proposed in this paper is
more flexible.

2) For the formulated design problem with discrete constraints, this paper
transform it to continuous problem based on relaxation idea. To solve it
efficiently, two algorithms Penalty Box ADMM and $\ell_{p}$-Box ADMM are
proposed. Through theoretical analysis, it is proved that the proposed methods
converge to the stationary point of the approximate problem. If the weight of
penalty term in Penalty Box ADMM is reasonably chosen, the correlation
performance of the generated sequence is a litter bit better than that of
$\ell_{p}$-Box ADMM. However, $\ell_{p}$-Box ADMM without weight parameter is
easier to implement.

3) Different from the serial execution methods in [38]–[41], the proposed
algorithm can be executed distributedly leading to high efficiency. Besides,
the proposed methods utilize inherent sparse structure of the optimization
problem to achieve polynomial computational complexity which is lower than
existing works e.g. [38]–[41]. Simulation results involving convergence and
correlation are utilized to show improved performance in comparison with the
state-of-the-art methods.

The rest of the paper is organized as follows. In Section II, we formulate the
binary sequence design problem to a nonconvex consensus optimization problem.
In Section III, Box ADMM framework is customized to solve the nonconvex
problem. To encourage binary solution, Penalty Box ADMM and $\ell_{p}$-Box
ADMM algorithms are proposed. The performance analysis, including convergence
and computational complexity of the proposed ADMM approach, is presented in
Section IV. Finally, Section V demonstrates the effectiveness of the proposed
ADMM algorithms and the conclusions are given in Section VI.

_Notation_ : bold lowercase and uppercase letters denote column vectors and
matrices and italics denote scalars. $\mathds{R}$ and $\mathds{C}$ denote the
real field and the complex field respectively. Other notations used through
this paper are presented in Table I.

TABLE I: Notations Notation | Description
---|---
$\mathbb{R}^{N\times M}$ |  the sets of $N\times M$-dimensional real-valued matrix
$\mathbf{x}^{T}$ |  the transpose of vector $\mathbf{x}$
$\mathbf{I}_{N}$ |  $N\times N$-dimensional identity matrix
$|{x}|$ |  the absolute value of ${x}$
$\|\mathbf{x}\|_{2}$ |  the Euclidean norm of vector $\mathbf{x}$
$\|\mathbf{x}\|_{p}$ |  the $\ell_{p}$-norm of vector $\mathbf{x}$, defined as $(\sum\limits_{k}|\mathbf{x}_{k}|^{p})^{\frac{1}{p}}$
$\|\mathbf{X}\|_{F}$ |  the Frobenius norm of matrix $\mathbf{X}$
$\|\mathbf{x}\|_{\infty}$ |  the infinite norm of vector $\mathbf{x}$
$\nabla f(\cdot)$ |  the gradient of function $f(\cdot)$
$\langle\mathbf{x},\mathbf{y}\rangle$ |  the dot product of $\mathbf{x}$ and $\mathbf{y}$
$\mathop{\prod}(\mathbf{x})$ |  the projection of $\mathbf{x}$

##  II Problem Formulation

###  II-A System Model

Let consider a binary sequence set
$\mathbf{X}=[\mathbf{x}_{1},\mathbf{x}_{2},\cdots,\mathbf{x}_{M}]$, and each
element in sequences $\\{\mathbf{x}_{i}\\}_{i=1}^{M}$ is $-1$ or $1$. The
aperiodic and periodic correlation functions of sequence $\mathbf{x}_{i}$ and
$\mathbf{x}_{j}$ at shift $n$ are defined as

$\begin{split}r_{ij,n}^{\mathcal{AP}}\\!=\\!\\!\sum_{k=n+1}^{N}x_{i,k}x_{j,k-n},r_{ij,n}^{\mathcal{P}}\\!=\\!\\!\sum_{k=n+1}^{N}x_{i,k}x_{j,k-n_{mod(N)}},\end{split}$
(1)

where $i,j=1,\cdots,M;n=-N+1,\cdots,N-1$. When $i=j$,
$r_{ij,n}^{\mathcal{AP}}$ and $r_{ij,n}^{\mathcal{P}}$ represent the
aperiodic/periodic auto-correlation function of
$\\{\mathbf{x}_{i}\\}_{i=1}^{M}$. Otherwise, they are cross-correlation
functions.

There are some metrics that are used to evaluate the goodness of the
correlation properties of binary sequences. The most commonly used ones are
the ISL [43], PSL[44], and Peak to Average Power Radio (PAPR) [45], etc. ISL
gives the relationship among the sequence and its shift version. It is often
used to measure the synchronization performance between the received signal
and all the interference signals caused by multipath in the wireless
communication system. PSL is a metric derived from the autocorrelation
function which describes the relationship among the maximum of the side lobes
(SL). It means the worst case of interference caused by SL to main lobe.
Therefore binary sequence sets with small PSL value are desirable.

In this paper, we consider the optimization metric of PSL. The definitions is
given in (2).

$\displaystyle PSL:\sum_{i=1}^{M}\max_{l\in\mathds{L}\backslash
0}\bigg{\\{}|r_{ii,l}|\bigg{\\}}+\sum_{i=1}^{M}\sum_{\begin{subarray}{c}j=1\\\
j\neq
i\end{subarray}}^{M}\max_{l\in\mathds{L}}\bigg{\\{}|r_{ij,l}|\bigg{\\}},$ (2a)

where $r_{ij,l}=r_{ij,l}^{\mathcal{AP}}$ and $r_{ij,l}=r_{ij,l}^{\mathcal{P}}$
address the aperiodic/periodic function respectively. $\mathds{L}$ denotes the
shift set interval of interest. To facilitate the subsequent expression, we
denote it as $f(\mathbf{X})$. By utilizing off-line matrices
$\mathbf{S}_{l}^{\mathcal{AP}}$ and cyclic shift matrices
$\mathbf{S}_{l}^{\mathcal{P}}$ defined in (3), (4) and denote
$\mathbf{x}_{i}=\mathbf{X}\mathbf{s}_{i}$, where $i$-th element in
$\mathbf{s}_{i}$ is $1$ and the rest elements are zeros.

$\begin{split}&\qquad\qquad\quad l~{}{\rm zeros}\\\
&{\bf{S}}_{l}^{\mathcal{AP}}=\left[\begin{array}[]{ccccc}\overbrace{0~{}\cdots~{}0}&1&{}\hfil&\mathbf{\scalebox{1.5}{0}}\\\
{}\hfil&{}\hfil&\ddots&{}\hfil\\\ {}\hfil&{}\hfil&{}\hfil&1\\\
\mathbf{\scalebox{2.5}{0}}&{}\hfil&{}\hfil&{}\hfil\\\
\end{array}\right],\end{split}$ (3) $\begin{split}&\qquad\qquad\quad l~{}{\rm
zeros}\\\
&{\bf{S}}_{l}^{\mathcal{P}}=\left[\begin{array}[]{ccccc}\overbrace{0~{}\cdots~{}0}&1&{}\hfil&\mathbf{\scalebox{1.5}{0}}\\\
{}\hfil&{}\hfil&\ddots&{}\hfil\\\ {}\hfil&{}\hfil&{}\hfil&1\\\
\mathbf{\scalebox{2.5}{I}}_{l}&{}\hfil&{}\hfil&{}\hfil\\\
\end{array}\right],\end{split}$ (4)

$f(\mathbf{X})$ can be rewritten as

$\begin{split}&f(\mathbf{X})\\!=\\!\\!\sum_{i=1}^{M}\max_{l\in\mathds{L}\backslash
0}\bigg{\\{}|(\mathbf{X}\mathbf{s}_{i})^{T}\mathbf{S}_{l}\mathbf{X}\mathbf{s}_{i}|\bigg{\\}}\\!\\!\\\
&\hskip 85.35826pt+\\!\\!\sum_{i=1}^{M}\sum_{\begin{subarray}{c}j=1\\\ j\neq
i\end{subarray}}^{M}\max_{l\in\mathds{L}}\bigg{\\{}|(\mathbf{X}\mathbf{s}_{i})^{T}\mathbf{S}_{l}\mathbf{X}\mathbf{s}_{j}|\bigg{\\}}\\\
&\hskip
21.33955pt=\\!\\!\sum_{i=1}^{M}\sum_{j=1}^{M}\max_{l\in\mathds{L}}\bigg{\\{}f_{ij,l}(\mathbf{X})\bigg{\\}},\end{split}$
(5)

where

$\begin{split}f_{ij,l}(\mathbf{X})\triangleq|(\mathbf{X}\mathbf{s}_{i})^{T}\mathbf{S}_{l}\mathbf{X}\mathbf{s}_{j}-N\delta_{|i-j|+|l|}|.\end{split}$
(6)

In (6), $\delta_{|i-j|+|l|}$ in (5) denotes the Dirac-$\delta$ function and
$\mathbf{S}_{l}=\mathbf{S}_{l}^{\mathcal{AP}}$ and
$\mathbf{S}_{l}=\mathbf{S}_{l}^{\mathcal{P}}$ are aperiodic and periodic cases
respectively. To facilitate the subsequent expression, we define the notation
set $\mathbb{O}=\\{ij,l|,i,j=1,\cdots,M,l\in\mathds{L}\\}$. Then, the problem
for designing binary sequence set with good PSL can be formulated as

$\begin{split}&\hskip 5.69046pt\min_{\mathbf{X}\in\mathbb{R}^{N\times
M}}\hskip
14.22636pt\sum_{i,j=1}^{M}\max_{l\in\mathds{L}}\big{\\{}f_{o}(\mathbf{X})\big{\\}},\\\
&{\rm subject\ to}\hskip 14.22636pt\mathbf{X}\in\mathcal{X},\end{split}$ (7)

where

$\mathcal{X}=\\{\mathbf{X}|x_{i,n}\in\\{-1,1\\},\ i=1,\cdots,M,\
n=1,\cdots,N\\}.$

Since the constraint $\mathbf{X}\in\mathcal{X}$ is discrete, problem (7) is a
combination optimization problem with respect to variable $\pm 1$. That means
the computational complexity of obtaining global optimal solution to problem
(7) grows exponentially with the size of set $\mathcal{X}$. Such a high
complexity in practical application is unbearable. The usual way to solve this
problem is to relax the binary constraint to continuous box constraints, i.e.,
$\mathbf{X}\in\mathcal{X}_{B}$, where

$\mathcal{X}_{B}=\left\\{\mathbf{X}{\big{|}}\ \mathbf{x}_{i}\in[-1,1],\
i=1,\cdots,M\right\\}.$

The relaxed operation of binary constraint may lead the elements in
$\mathbf{X}$ to be non-binary solution during the iteration process. To
encourage binary solutions, some penalty method, e.g., adding the penalty term
in the objective function can be introduced. However, the non-convexity of the
added penalty term may lead to further issues, namely undesirable local minima
and sensitivity to the initialization. To tackle it, we relax the binary
constraint to $\ell_{p}$-Box intersection.

_Proposition:_ $\ell_{p}$-Box Intersection [49]: The binary set
$\\{-1,1\\}^{N\times M}$ can be equivalently replaced by the intersection
between a sphere $\mathcal{X}_{S}$ and a box $\mathcal{X}_{B}$, as follows:

$\begin{split}\mathbf{X}\\!\in\\!\\{-1,1\\}^{N\\!\times\\!M}\\!\Leftrightarrow\\!\mathbf{X}\\!\in\\!\mathcal{X}_{S}\bigcap\mathcal{X}_{B}.\end{split}$
(8)

Figure 1: Geometric illustration of the equivalence between $\ell_{p}$-Box
intersection and the set of binary points in $\mathbb{R}^{2}$,
$p=\\{1,2,5\\}$.

where

$\begin{split}\mathcal{X}_{S}=\left\\{\mathbf{X}:\\!\|\mathbf{X}\|_{p}^{p}\\!=\\!MN\right\\}.\end{split}$
(9)

Note that $\mathcal{X}_{S}$ can be seen as a $(MN-1)$-dimensional
$\ell_{p}$-sphere centered at origin of axes with radius $(MN)^{\frac{1}{p}}$
and $p\in(0,\infty)$. To illustrate this proposition, we present a
$2$-dimensional example with different $p$ parameters in Fig. 1. It is obvious
from the figure that binary set $\\{-1,1\\}^{2}$ is the intersection between
the sphere $\mathcal{X}_{S}$ and the box $\mathcal{X}_{B}$.

By relaxing the binary constraint to $\ell_{p}$-Box and introducing auxiliary
variables $\\{\mathbf{Z}_{o}\in\mathbb{R}^{N\times M}\\}_{o\in\mathbb{O}}$,
problem (7) can be transformed into the following global consensus problem

$\begin{split}&\min_{\\{\mathbf{X}_{1},\mathbf{X}_{2},\mathbf{Z}_{o}\\}\in\mathbb{R}^{N\times
M}}\sum_{i,j=1}^{M}\max_{l\in\mathds{L}}\big{\\{}f_{o}(\mathbf{Z}_{o})\big{\\}},\\\
&{\rm subject\ to}\
\mathbf{X}_{1}\\!\in\\!\mathcal{X}_{B},\\!\mathbf{X}_{2}\\!\in\\!\mathcal{X}_{S},\\!\mathbf{X}_{1}\\!=\\!\mathbf{Z}_{o},\mathbf{X}_{2}\\!=\\!\mathbf{Z}_{o},o\in\mathbb{O}.\end{split}$
(10)

The introduction of auxiliary variables makes each subproblem have its local
variables. Thus, each subproblem can be solved in parallel. Define the
following matrices

$\begin{split}&\bar{\mathbf{X}}=[\mathbf{X}_{1};\mathbf{X}_{2}],\
\mathbf{A}=[\mathbf{I}_{N};\mathbf{I}_{N}].\end{split}$ (11)

The linear constraints can be rewritten as
$\mathbf{A}\mathbf{Z}_{o}=\bar{\mathbf{X}}$.

##  III Solving Algorithm

In this section, one algorithm named $l_{p}$-Box ADMM algorithm is developed
to solve problem (10). In comparison with the state-of-the-art methods, one
major benefit of proposed algorithm is the parallel execution structure.
Another benefit is that the feasible region of the optimization variable is
relaxed to the intersection of two continuous regions. The former one benefit
can greatly improve the algorithm execution’s efficiency. The latter one can
promote the sequence with better correlation performance.

###  III-A $\ell_{p}$-Box ADMM Algorithm

In (11), $\mathbf{A}^{T}=[\mathbf{I}_{N},\mathbf{I}_{N}]\in\mathbb{R}^{N\times
2N}$ is full row rank, i.e., $rank(\mathbf{A}^{T})=N<2N$. Main difficulty
during the convergence analysis is the constraint
$\mathbf{A}\mathbf{Z}_{o}=\mathbf{X}$. To tackle it, define
$\bar{\mathbf{A}}=[\mathbf{A},\sigma\mathbf{I}_{2N}]\in\mathbb{R}^{2N\times
3N},\ \bar{\mathbf{Z}}_{o}=[\mathbf{Z}_{o};\hat{\mathbf{Z}}_{o}],$ where
$[\hat{\mathbf{Z}}_{o1};\hat{\mathbf{Z}}_{o2}]=\hat{\mathbf{Z}}_{o}$ are
introduced perturbed variable to construct constraint
$\bar{\mathbf{A}}\bar{\mathbf{Z}}_{o}=\bar{\mathbf{X}}$, i.e.,

$\begin{split}\mathbf{A}\mathbf{Z}_{o}+\sigma\hat{\mathbf{Z}}_{o}=\bar{\mathbf{X}},\end{split}$
(12)

where $\sigma>0$ is sufficiently small. Then, the associated perturbed problem
is presented as

$\begin{split}&\min_{\\{\mathbf{X},\bar{\mathbf{Z}}_{o}\\}\in\mathbb{R}^{N\times
M}}\sum_{i,j=1}^{M}\left(\max_{l\in\mathds{L}}\big{\\{}f_{o}(\mathbf{Z}_{o})\big{\\}}+\frac{\sigma^{2}}{2}\hat{\mathbf{Z}}_{o}^{T}\hat{\mathbf{Z}}_{o}\right),\\\
&{\rm subject\ to}\
\mathbf{X}_{1}\\!\in\\!\mathcal{X}_{B},\mathbf{X}_{2}\\!\in\\!\mathcal{X}_{S},\bar{\mathbf{A}}\bar{\mathbf{Z}}_{o}=\bar{\mathbf{X}},o\in\mathbb{O}.\end{split}$
(13)

ADMM, a popular technique, is suitable for solving problem (10) with multiple
separable subproblems. The corresponding augmented Lagrangian function can be
expressed as

$\begin{split}&\mathcal{L}\left(\bar{\mathbf{X}},\\{\bar{\mathbf{Z}}_{o},\mathbf{\Lambda}_{o}\\}_{o\in\mathbb{O}}\right)\\\
=\
&\sum_{i,j=1}^{M}\left(\max_{l\in\mathds{L}}\big{\\{}f_{o}(\mathbf{Z}_{o})\big{\\}}+\frac{\sigma^{2}}{2}\hat{\mathbf{Z}}_{o}^{T}\hat{\mathbf{Z}}_{o}\right)\\\
&\hskip
17.07182pt{+\sum\limits_{o\in\mathbb{O}}{\left({\left\langle{\mathbf{\Lambda}}_{o},\bar{\mathbf{X}}-\bar{\mathbf{A}}\bar{\mathbf{Z}}_{o}\right\rangle+\frac{{{\rho_{o}}}}{2}\left\|{\bar{\mathbf{X}}-{\bar{\mathbf{A}}\bar{\mathbf{Z}}_{o}}}\right\|_{F}^{2}}\right)}}.\end{split}$
(14)

where $\\{\mathbf{\Lambda}_{o}\in\mathbb{R}^{N\times
M},\rho_{o}>0\\}_{o\in\mathbb{O}}$ are Lagrangian multipliers and penalty
parameters respectively. Thus, the $\ell_{p}$-Box ADMM framework to solve
problem (10) can be described as

$\displaystyle\bar{\mathbf{X}}^{k+1}=\underset{\mathbf{X}_{1}\in\mathcal{X}_{B},\mathbf{X}_{2}\in\mathcal{X}_{S}}{\arg\min}\
\
\mathcal{L}\left(\bar{\mathbf{X}},\\{\bar{\mathbf{Z}}_{o}^{k},\mathbf{\Lambda}_{o}^{k}\\}_{o\in\mathbb{O}}\right),$
(15a)
$\displaystyle\bar{\mathbf{Z}}_{o}^{k+1}=\underset{\bar{\mathbf{Z}}_{o}}{\arg\min}\
\
\mathcal{L}\left(\bar{\mathbf{X}}^{k+1},\bar{\mathbf{Z}}_{o},\mathbf{\Lambda}_{o}^{k}\right),o\in\mathbb{O},$
(15b)
$\displaystyle\mathbf{\Lambda}_{o}^{k+1}=\mathbf{\Lambda}_{o}^{k}+\rho_{o}(\bar{\mathbf{X}}^{k+1}-\bar{\mathbf{A}}\bar{\mathbf{Z}}_{o}^{k+1}),o\in\mathbb{O},$
(15c)

where $k$ denotes the iteration number. Since function $\mathcal{L}(\cdot)$ is
nonconvex related to variable $\mathbf{Z}_{o}$. The challenge of implementing
Penalty Box ADMM is how to solve (15b).

####  III-A1 Solving Subproblem (15a)

Problem (15a) can be equivalent to the following problem

$\begin{split}&\min_{\bar{\mathbf{X}}\in\mathbb{R}^{N\\!\times\\!M}}\sum\limits_{o\in\mathbb{O}}{\left({\left\langle{\mathbf{\Lambda}}_{o}^{k},\bar{\mathbf{X}}-\bar{\mathbf{A}}\bar{\mathbf{Z}}_{o}^{k}\right\rangle+\frac{{{\rho_{o}}}}{2}\left\|{\bar{\mathbf{X}}-{\bar{\mathbf{A}}\bar{\mathbf{Z}}_{o}^{k}}}\right\|_{F}^{2}}\right)},\\\
&\ {\rm subject\ to}\hskip 5.69046pt\
\mathbf{X}_{1}\in\mathcal{X}_{B},\mathbf{X}_{2}\in\mathcal{X}_{S}.\end{split}$
(16)

In problem (16), objective function is quadratic w.r.t. $\bar{\mathbf{X}}$ and
$\mathbf{X}_{1}\in\mathcal{X}_{B},\mathbf{X}_{2}\in\mathcal{X}_{S}$. Thus, the
optimal solution to (16) can be obtained through the following procedures: set
the gradient function to be zero, i.e.,

$\begin{split}\nabla_{\bar{\mathbf{X}}}{\left[\sum\limits_{o\in\mathbb{O}}{\left({\left\langle{{\mathbf{\Lambda}}_{o}^{k},{\bar{\mathbf{X}}}\\!-\\!\bar{\mathbf{A}}\bar{\mathbf{Z}}_{o}^{k}}\right\rangle+\frac{{{\rho_{o}}}}{2}\left\|{{\bar{\mathbf{X}}}\\!-\\!\bar{\mathbf{A}}\bar{\mathbf{Z}}_{o}^{k}}\right\|_{F}^{2}}\right)}\right]}\\!=\\!0.\end{split}$
(17)

Then, we obtain its solution

$\begin{split}\hat{\mathbf{X}}^{k+1}=\left[\begin{array}[]{c}\hat{\mathbf{X}}_{1}^{k+1}\\\
\hat{\mathbf{X}}_{2}^{k+1}\\\
\end{array}\right]=\frac{{\mathop{\sum}\limits_{o\in\mathbb{O}}({\rho_{o}}\bar{\mathbf{A}}\bar{\mathbf{Z}}_{o}^{k}-{\mathbf{\Lambda}}_{o}^{k})}}{{\mathop{\sum}\limits_{o\in\mathbb{O}}\rho_{o}}}.\end{split}$
(18)

Projecting $\hat{\mathbf{X}}_{1}^{k+1}$ and $\hat{\mathbf{X}}_{2}^{k+1}$ onto
$\mathcal{X}_{B}$ and $\mathcal{X}_{S}$ respectively, we can obtain

$\begin{split}{\mathbf{X}}_{1}^{k+1}=\mathop{\prod}\limits_{\mathbf{X}\in\mathcal{X}_{B}}\left(\hat{\mathbf{X}}_{1}^{k+1}\right),{\mathbf{X}}_{2}^{k+1}=\mathop{\prod}\limits_{\mathbf{X}\in\mathcal{X}_{S}}\left(\hat{\mathbf{X}}_{2}^{k+1}\right),\end{split}$
(19)

where $\mathop{\prod}\limits_{\mathbf{X}\in\mathcal{X}_{B}}(\cdot)$ project
every entry of the input variable onto $[-1,1]$ and

$\begin{split}\mathop{\prod}\limits_{\mathbf{X}\in\mathcal{X}_{S}}\left(\mathbf{X}\right)=\frac{\mathbf{X}}{\|\mathbf{X}\|_{p}}(MN)^{1/p}.\end{split}$
(20)

Problem (15a)’s solution is
$\bar{\mathbf{X}}^{k+1}=[{\mathbf{X}}_{1}^{k+1};{\mathbf{X}}_{2}^{k+1}]$.

####  III-A2 Solving Subproblem (15b)

Since (15b) is an unconstrained problem, the major challenge to solve it is
how to handle
$\mathop{\max}\limits_{l\in\mathds{L}}\left\\{f_{o}(\mathbf{Z}_{o})\right\\}$.
Define the following vector

$\begin{split}\mathbf{f}_{ij}(\\{\mathbf{Z}_{o}\\})=\left[\cdots,f_{ij,l}(\mathbf{Z}_{ij,l}),f_{ij,l+1}(\mathbf{Z}_{ij,l+1}),\cdots\right]\in\mathbb{R}^{|\mathds{L}|}.\end{split}$

Then,
$\mathop{\max}\limits_{l\in\mathds{L}}\left\\{f_{o}(\mathbf{Z}_{o})\right\\}$
is equivalent to $\|\mathbf{f}_{ij}(\\{\mathbf{Z}_{o}\\})\|_{\infty}$. Given
that from an analytical point of view, the $\ell_{\infty}$-norm is not a well-
behaved function, $\ell_{q}$-norms will be used instead, i.e.,

$\begin{split}\mathop{\max}\limits_{l\in\mathds{L}}\left\\{f_{o}(\mathbf{Z}_{o})\right\\}\\!=\\!\lim_{q\rightarrow\infty}\|\mathbf{f}_{ij}(\\{\mathbf{Z}_{o}\\})\|_{q}\\!=\\!\left(\sum_{l\in\mathds{L}}f_{o}^{q}(\mathbf{Z}_{o})\right)^{\\!\frac{1}{q}},\end{split}$
(21)

where $q>2$ is a integer. Minimizing
$\left(\sum\limits_{l\in\mathds{L}}f_{o}^{q}(\mathbf{Z}_{o})\right)^{\\!\frac{1}{q}}$
is equivalent to minimizing
$\sum\limits_{l\in\mathds{L}}f_{o}^{q}(\mathbf{Z}_{o})$. Assuming the current
iteration index is $k$, $f_{o}^{q}(\mathbf{Z}_{o})$ can be majored at point
$\mathbf{Z}_{o}^{k}$ [46] [47], i.e.,

$\begin{split}f_{o}^{q}(\mathbf{Z}_{o})\leq\frac{q}{2}f_{o}^{q-2}(\mathbf{Z}_{o}^{k})f_{o}^{2}(\mathbf{Z}_{o})+f_{cons}.\end{split}$
(22)

where $f_{cons}$ is the constant term. Plugging (21) and (22) into problem
(15b) and dropping the constant term, we get the following approximate problem

$\begin{split}\min_{\\{\bar{\mathbf{Z}}_{o}\\}}\mathcal{L}\left(\bar{\mathbf{X}},\\{\bar{\mathbf{Z}}_{o},\mathbf{\Lambda}_{o}\\}_{o\in\mathbb{O}}\right),\end{split}$
(23)

where

$\begin{split}&\mathcal{L}\left(\bar{\mathbf{X}},\\{\bar{\mathbf{Z}}_{o},\mathbf{\Lambda}_{o}\\}_{o\in\mathbb{O}}\right)\\\
=\
&\sum_{o\in\mathbb{O}}\left(w_{o}f_{o}^{2}(\mathbf{Z}_{o})+\sigma^{2}\hat{\mathbf{Z}}_{o}^{T}\hat{\mathbf{Z}}_{o}\right.\\\
&\hskip
39.83368pt\left.+{\left\langle{\mathbf{\Lambda}}_{o},{\bar{\mathbf{X}}}-\bar{\mathbf{A}}\bar{\mathbf{Z}}_{o}\right\rangle+\frac{{{\rho_{o}}}}{2}\left\|{{\bar{\mathbf{X}}}-{\bar{\mathbf{A}}\bar{\mathbf{Z}}_{o}}}\right\|_{F}^{2}}\right)\\\
=\
&\sum_{o\in\mathbb{O}}\mathcal{L}_{o}\left(\bar{\mathbf{X}},\bar{\mathbf{Z}}_{o},\mathbf{\Lambda}_{o}\right).\end{split}$
(24)

where $w_{o}$ is the normalized weight

$\begin{split}{w}_{o}=\left(\frac{f_{o}(\mathbf{Z}_{o}^{k})}{\mathop{\max}\limits_{o\in\mathbb{O}}\left\\{f_{o}(\mathbf{Z}_{o}^{k})\right\\}}\right)^{q-2}.\end{split}$
(25)

For all $o\in\mathbb{O}$, subproblems in (23) are independent of each other
and each subproblem is unconstrained w.r.t. variable $\mathbf{Z}_{o}$. That
means subproblems in (23) can be implemented in parallel. However, solving
problem (23) is still difficult, since $f_{o}^{2}(\mathbf{Z}_{o})$ is
nonconvex related to $\mathbf{Z}_{o}$ (see (6)). To tackle it, we have the
following lemma, which indicates that
$\\{f_{o}^{2}(\mathbf{Z})\\}_{o\in\mathbb{O}}$ are continuous, differentiable
and have Lipschitz continuous gradients in the finite domain
$\mathcal{X}_{c}=\left\\{\mathbf{X}{\big{|}}\ \mathbf{{x}}_{i}\in[-c,c],\
i=1,\cdots,M\right\\}$ of the point $\mathbf{\hat{X}}\in\mathcal{X}_{B}$ (see
proof in Appendix A).

###### Lemma 1

gradients $\nabla f_{o}(\mathbf{X})$ are Lipschitz continuous, i.e.,

$\begin{split}\|\nabla f^{2}_{o}(\mathbf{\tilde{X}})\\!-\\!\nabla
f_{o}^{2}(\mathbf{\hat{X}})\|_{F}\\!\leq\\!L_{o}\|\mathbf{\tilde{X}}\\!-\\!\mathbf{\hat{X}}\|_{F},\
o\in\mathbb{O},\end{split}$ (26)

where $\mathbf{\tilde{X}}\in\mathcal{X}_{c}$,
$\mathbf{\hat{X}}\in\mathcal{X}_{B}$ and constants

$\begin{split}L_{o}\\!\geq\\!2(N+1){\hat{c}}^{2},\
{\hat{c}}=\max\\{c,1\\}.\end{split}$ (27)

Based on Lemma 1 and Decent Lemma in [48], we have

$\begin{split}&\mathcal{L}_{o}\left(\bar{\mathbf{X}}^{k+1},\bar{\mathbf{Z}}_{o},\mathbf{\Lambda}_{o}^{k}\right)\\\
\leq&\ {w}_{o}f_{o}^{2}(\mathbf{X}^{k+1})+\\!\\!\left\langle{w}_{o}\nabla
f^{2}_{o}(\mathbf{X}^{k+1}),\mathbf{Z}_{o}-\mathbf{X}^{k+1}\right\rangle\\\
&\hskip
2.84544pt+\frac{{w}_{o}L_{o}}{2}\left\|{\mathbf{X}^{k+1}-{\mathbf{Z}}_{o}}\right\|_{F}^{2}+\left\langle\mathbf{\Lambda}_{o}^{k},\bar{\mathbf{X}}^{k+1}-\bar{\mathbf{A}}\bar{\mathbf{Z}}_{o}\right\rangle\\\
&\hskip
2.84544pt+\frac{\rho_{o}}{2}\left\|{\bar{\mathbf{X}}^{k+1}-\bar{\mathbf{A}}\bar{\mathbf{Z}}_{o}}\right\|_{F}^{2}+\frac{\sigma^{2}}{2}\hat{\mathbf{Z}}_{o}^{T}\hat{\mathbf{Z}}_{o}.\end{split}$
(28)

Define the right-hand side of the above inequality as
$\mathcal{U}_{o}(\mathbf{Z}_{o})$. We customize the $\ell_{p}$-Box ADMM by
minimizing it instead of (23). Since $\mathcal{U}_{o}(\mathbf{Z}_{o})$ is
convex quadratic function w.r.t. $\mathbf{Z}_{o}$, the optimal solution can be
obtained by setting
$\nabla_{\mathbf{Z}_{o}}\mathcal{U}_{o}(\mathbf{Z}_{o})=0$. Through solving
the equation, we get the solution

$\displaystyle\hat{\mathbf{Z}}_{o}^{k+1}$
$\displaystyle=\frac{\mathbf{\Lambda}_{o}^{k}+\rho_{o}(\bar{\mathbf{X}}^{k+1}-\mathbf{A}\mathbf{Z}_{o}^{k})}{(\rho_{o}+1)\sigma},$
(29a) $\displaystyle\mathbf{Z}_{o}^{k+1}$
$\displaystyle\\!=\\!\mathbf{X}^{k+1}\\!+\\!\frac{\mathbf{A}^{T}(\mathbf{\Lambda}_{o}^{k}\\!-\\!\rho_{o}\sigma\hat{\mathbf{Z}}_{o}^{k+1})\\!-\\!{w}_{o}\nabla
f^{2}_{o}(\mathbf{X}^{k+1})}{2\rho_{o}+{w}_{o}L_{o}},$ (29b)

where

$\begin{split}\mathbf{X}^{k+1}=\frac{\mathbf{A}^{T}(\bar{\mathbf{X}}^{k+1}-\sigma\hat{\mathbf{Z}}_{o}^{k+1})}{2}.\end{split}$
(30)

Combining (15c), (19) and (29), we summarize the customized Penalty Box ADMM
algorithm in Table II.

TABLE II: The customized Penalty Box ADMM algorithm  Initialization: Compute
Lipschitz constants $\\{L_{o},\\!l\\!\in\\!\mathds{L}\\}$
---
according to (27). Set iteration index $k\\!=\\!1$, initialize
$\bar{\mathbf{X}}^{1}$ and $\\{\mathbf{\Lambda}_{o}^{1},o\in\mathbb{O}\\}$
randomly, and let
$\\{\bar{\mathbf{X}}^{1}=\bar{\mathbf{A}}\bar{\mathbf{Z}}_{o}^{1},$
$o\in\mathbb{O}\\}$.
repeat
S.1 Compute ${\bar{\mathbf{X}}}^{k+1}$ via (18) and (19) , i.e.,
$\bar{\mathbf{X}}^{k+1}=\left[\begin{array}[]{c}\mathop{\prod}\limits_{\mathbf{X}\in\mathcal{X}_{B}}\left(\hat{\mathbf{X}}_{1}^{k+1}\right)\\\
\mathop{\prod}\limits_{\mathbf{X}\in\mathcal{X}_{S}}\left(\hat{\mathbf{X}}_{2}^{k+1}\right)\\\
\end{array}\right].$
S.2 Compute $\\{\bar{\mathbf{Z}}_{o}^{k+1},o\in\mathbb{O}\\}$ via (29) in
parallel, i.e.,
$\hat{\mathbf{Z}}_{o}^{k+1}=\frac{\mathbf{\Lambda}_{o}^{k}+\rho_{o}(\bar{\mathbf{X}}^{k+1}-\mathbf{A}\mathbf{Z}_{o}^{k})}{(\rho_{o}+1)\sigma}$,
$\mathbf{Z}_{o}^{k+1}=\mathbf{X}^{k+1}\\!+\\!\frac{\mathbf{A}^{T}(\mathbf{\Lambda}_{o}^{k}\\!-\\!\rho_{o}\sigma\hat{\mathbf{Z}}_{o}^{k+1})\\!-\\!{w}_{o}\nabla
f^{2}_{o}(\mathbf{X}^{k+1})}{2\rho_{o}+{w}_{o}L_{o}}.$
S.3 Compute $\\{\mathbf{\Lambda}_{o}^{k+1},o\in\mathbb{O}\\}$ via (15c) in
parallel, i.e.,
$\mathbf{\Lambda}_{o}^{k+1}\\!=\mathbf{\Lambda}_{o}^{k}+\rho_{o}(\bar{\mathbf{X}}^{k+1}-\bar{\mathbf{A}}\bar{\mathbf{Z}}_{o}^{k+1})$.
until some preset termination criterion is satisfied.
Let $\mathbf{X}^{k+1}$ be the output.

_Remarks on proposed ADMM algorithms:_
$\bullet$ In model (10), we relax the problem to continuous variable problem.
Different from traditional methods [38][39], the proposed algorithms optimize
variable $\mathbf{X}$ as a whole rather than individual elements of
$\mathbf{X}$.
$\bullet$ During the iteration of the proposed algorithms, we introduce the
convex quadratic function $\mathcal{L}(\cdot)$. Even if the optimization and
projection operation are performed separately, both
$\prod\limits_{\mathbf{X}\in\mathcal{X}_{B}}(\cdot)$ and
$\mathop{\prod}\limits_{\mathbf{X}\in\mathcal{X}_{S}}(\cdot)$ can guarantee
the obtained solution is (locally) optimal.
$\bullet$ Parallel execution architecture of the proposed algorithms plays an
essential role leading to better implementation efficiency than the state-of-
the-art methods.
$\bullet$ The proposed algorithms are guaranteed convergent to some stationary
point of the nonconvex optimization problem if proper parameters are chosen.
We have several theorems in the following section.

##  IV Algorithm Analysis

In this section, we show several analyses on the proposed ADMM algorithm, such
as convergence and computational complexity. The proposed algorithms are
convergent to some stationary point of the approximate problem. To reduce the
algorithm’s computational complexity, we exploit the inherent sparsity
characteristic of the problem.

###  IV-A Convergence Issue

Before presenting the convergence conclusion, we first give a few
corresponding lemmas.

###### Lemma 2

For the proposed algorithm, the augmented Lagrangian function has the
following inequality

$\begin{split}&\mathcal{L}\left(\bar{\mathbf{X}}^{k},\\{\bar{\mathbf{Z}}_{o}^{k},\mathbf{\Lambda}_{o}^{k}\\}_{o\in\mathbb{O}}\right)\\!-\\!\mathcal{L}\left(\bar{\mathbf{X}}^{k+1},\\{\bar{\mathbf{Z}}_{o}^{k+1},\mathbf{\Lambda}_{o}^{k+1}\\}_{o\in\mathbb{O}}\right)\\\
&\geq\\!\sum\limits_{o\in\mathbb{O}}\frac{1}{{2\rho_{o}^{2}}}\left(\bar{\epsilon}_{o}\left\|{{\bar{\mathbf{X}}^{k+1}}-{\bar{\mathbf{X}}^{k}}}\right\|_{F}^{2}+{\epsilon}_{o}\left\|{{\mathbf{Z}}_{o}^{k+1}-{\mathbf{Z}}_{o}^{k}}\right\|_{F}^{2}\right.\\\
&\hskip
128.0374pt\left.+\hat{\epsilon}_{o}\left\|{\hat{\mathbf{Z}}_{o}^{k+1}-\hat{\mathbf{Z}}_{o}^{k}}\right\|_{F}^{2}\right).\end{split}$
(31)

In each $\ell_{p}$-Box ADMM iteration, if
${\epsilon}_{o},\bar{\epsilon}_{o},\hat{\epsilon}_{o}\geq 0$,
$\mathcal{L}\left(\bar{\mathbf{X}}^{k},\\{\bar{\mathbf{Z}}_{o}^{k},\mathbf{\Lambda}_{o}^{k}\\}_{o\in\mathbb{O}}\right)$
decreases sufficiently.

###### Lemma 3

If $\rho_{n}\geq 5L_{n}$, the augmented Lagrangian function is lower bounded,
i.e.,

$\mathcal{L}\left(\bar{\mathbf{X}}^{k},\\{\bar{\mathbf{Z}}_{o}^{k},\mathbf{\Lambda}_{o}^{k}\\}_{o\in\mathbb{O}}\right)\geq
0,\forall k.$ (32)

The proof of Lemma 2 and 3 is given in Appendix B.

Lemma 2 and 3 show that augmented Lagrangian function $\mathcal{L}(\cdot)$
decreases sufficiently and has a lower bound, which indicates it is
convergent. We have the following theorem to characterize the proposed
$\ell_{p}$-Box ADMM algorithm.

###### Theorem 1

$\forall{o\in\mathbb{O}}$ if penalty parameters $\rho_{o}$ and Lipschitz
constants $L_{o}$ satisfy some wild conditions, the proposed ADMM algorithms
converge to some stationary point $\mathbf{X}^{*}$ of approximate problem
(34), i.e.,

$\begin{split}\left\langle\nabla
F(\mathbf{X}^{*}),\mathbf{X}-\mathbf{X}^{*}\right\rangle\geq 0,\end{split}$
(33)

where

$\begin{split}F(\mathbf{X})=\sum_{o\in\mathbb{O}}w_{o}f_{o}^{2}(\mathbf{X}).\end{split}$
(34)

The detail of the proof and convergence conditions are given in Appendix C.

###  IV-B Implementation Analysis

Observing the proposed ADMM algorithm, the computational cost is mainly
multiplication of solving the gradient $\nabla f^{2}_{o}(\mathbf{X})$.
Function $f^{2}_{o}(\mathbf{X})$ is defined as

$\begin{split}f^{2}_{o}(\mathbf{X})\triangleq|\mathbf{s}_{i}^{T}\mathbf{X}^{T}\mathbf{S}_{l}\mathbf{X}\mathbf{s}_{j}-N\delta_{|i-j|+|l|}|^{2}.\end{split}$
(35)

For gradient $\nabla f^{2}_{o}(\mathbf{X})$, we have

$\begin{split}&\nabla
f^{2}_{o}(\mathbf{X})\\!\\!=\\!\\!\\!\left[\begin{array}[]{ccccccc}\frac{\partial
f^{2}_{o}(\mathbf{X})}{\partial x_{1,1}}&\cdots&\\!\\!\frac{\partial
f^{2}_{o}(\mathbf{X})}{\partial x_{m,1}}\\!\\!&\cdots&\frac{\partial
f^{2}_{o}(\mathbf{X})}{\partial x_{M,1}}\\\ \frac{\partial
f^{2}_{o}(\mathbf{X})}{\partial x_{1,2}}&\cdots&\frac{\partial
f^{2}_{o}(\mathbf{X})}{\partial x_{m,2}}&\cdots&\frac{\partial
f^{2}_{o}(\mathbf{X})}{\partial x_{M,2}}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\ \frac{\partial
f^{2}_{o}(\mathbf{X})}{\partial x_{1,N}}&\cdots&\\!\\!\frac{\partial
f^{2}_{o}(\mathbf{X})}{\partial x_{m,N}}\\!\\!&\cdots&\frac{\partial
f^{2}_{o}(\mathbf{X})}{\partial x_{M,N}}\\\
\end{array}\right]\\!\\!,\end{split}$ (36)

where

$\begin{split}&\ \ \frac{\partial f^{2}_{o}(\mathbf{X})}{\partial x_{i,n}}\\\
&=\\!2\text{Tr}\left(\\!\frac{\partial(\mathbf{s}_{i}^{T}\mathbf{X}^{T}\mathbf{S}_{l}\mathbf{X}\mathbf{s}_{j})^{T}}{\partial
x_{i,n}}(\mathbf{s}_{i}^{T}\mathbf{X}^{T}\mathbf{S}_{l}\mathbf{X}\mathbf{s}_{j}\\!\\!-\\!\\!N\delta_{|i-j|+|l|})\\!\right).\end{split}$
(37)

For
$\frac{\partial(\mathbf{s}_{i}^{T}\mathbf{X}^{T}\mathbf{S}_{l}\mathbf{X}\mathbf{s}_{j})}{\partial
x_{i,n}}$, when $l=0$, we have

$\begin{split}&\frac{\partial\mathbf{X}^{T}\mathbf{X}}{\partial
x_{i,n}}\\!\\!=\\!\\!\\!\left[\begin{array}[]{ccccccc}{}\hfil&n\\!\\!-\\!\\!1&{\rm
zeros}&\\!\\!{x_{i,1}}\\!\\!&{}\hfil&{}\hfil&{}\hfil\\\
{}\hfil&\\!\\!\\!\overbrace{\\!\mathbf{\scalebox{3.0}{0}}\\!}\\!\\!\\!&{}\hfil&\vdots&{}\hfil&\\!\\!\mathbf{\scalebox{3.0}{0}}\\!\\!&{}\hfil\\\
{}\hfil&{}\hfil&{}\hfil&\\!\\!{x_{i,n-1}}\\!\\!&{}\hfil&{}\hfil\\\
\\!\\!\\!{x_{i,1}}&\\!\\!\cdots\\!\\!&\\!{x_{i,n-1}}\\!&0&\\!\\!{x_{i,n+1}}\\!\\!&\\!\\!\cdots\\!\\!&\\!{x_{i,M}}\\!\\!\\!\\\
{}\hfil&{}\hfil&{}\hfil&\\!\\!{x_{i,n+1}}\\!\\!&{}\hfil&{}\hfil&{}\hfil\\\
{}\hfil&\\!\\!\mathbf{\scalebox{3.0}{0}}\\!\\!&{}\hfil&\vdots&{}\hfil&\\!\\!\mathbf{\scalebox{3.0}{0}}\\!\\!&{}\hfil\\\
{}\hfil&{}\hfil&{}\hfil&\\!\\!{x_{i,M}}\\!\\!&{}\hfil&{}\hfil&{}\hfil\\\
\end{array}\right]\\!\\!.\end{split}$ (38)

From (38), it can be found that there are $2(M-1)$ nonzero elements in
$\frac{\partial\mathbf{X}^{T}\mathbf{X}}{\partial x_{i,n}}$. It implies that
obtaining $\frac{\partial f^{2}_{o}(\mathbf{X})}{\partial\mathbf{X}}$ needs
$2N$ multiplications at most. Since
$\mathbb{O}=\\{ij,l|,i,j=1,\cdots,M,l\in\mathds{L}\\}$, there are
$M^{2}|\mathds{L}|$ entries in set $\mathbb{O}$, obtaining all $\\{\nabla
f^{2}_{o}(\mathbf{X}),o\in\mathbb{O}\\}$ needs $2M^{2}N|\mathds{L}|$
multiplications ($|\mathds{L}|$ denotes set $\mathds{L}$’s size). Observing
Table II, we can see that the computational cost of other terms is far less
than $\nabla f^{2}_{o}(\mathbf{X})$. Therefore, we can conclude that the
computational cost of the proposed ADMM algorithm is
$\mathcal{O}(M^{2}N|\mathds{L}|)$111It should be noted that the proposed
algorithm can be implemented in parallel, the computational time will not
increase proportionally with $|\mathds{L}|$..

##  V Simulation Results

Figure 2: Comparisons of aperiodic convergence performance with
$N=2048,M=1,\mathds{L}=[1,N-1]$.

Figure 3: Comparisons of periodic convergence performance with
$N=2048,M=1,\mathds{L}=[1,N-1]$.

In this section, several numerical examples are presented to illustrate the
performance of the proposed ADMM algorithm. The simulation parameters are set
as follows: For the proposed ADMM algorithm, we define primal/dual residuals
[50] at the $k$-th iteration as

$\begin{split}\mathbf{R}^{k}=\sum\limits_{o\in\mathbb{O}}\|\mathbf{X}^{k+1}-\mathbf{Z}_{o}^{k+1}\|_{F}^{2},\
\mathbf{D}^{k}=\sum\limits_{o\in\mathbb{O}}\|\mathbf{Z}_{o}^{k+1}-\mathbf{Z}_{o}^{k}\|_{F}^{2}.\end{split}$

Then, the termination criterion in the simulations is set as
$\mathbf{R}^{k}+\mathbf{D}^{k}\leq 10^{-3},$ or the maximum iteration number
$500$ is reached. In the simulations, we set $M=1,2$, $L\in[6,10]$, $N=2^{L}$
(aperiodic case) or $2^{L}-1$ (periodic case), and $\mathds{L}=[0,N/2]$ or
$[0,N-1]$ .

In comparison, two state-of-the-art methods, BiST [39] and MM-WeCorr [32], are
carried out here. All approaches are initialized with the random binary
sequence. Besides, all experiments are performed in MATLAB 2019b/Windows 7
environment on a computer with 2.1GHz Intel 4100$\times$2 CPU and 64GB RAM.

###  V-A Convergence Performance

Fig. 2 and 3 show the convergence characteristics of the proposed ADMM
algorithm. All results are obtained over $50$ independent trials. From Fig. 2,
we can see that both the ISL and PSL values of Penalty Box/$\ell_{p}$-Box ADMM
converge faster than the Box ADMM. While for the residual values, the result
in Fig. 3conv 2048 pis just the opposite. This is mostly because during the
iteration process, compared with $\ell_{p}$-Box ADM algorithm, the variable
elements of $\mathbf{X}$ in the Box ADMM algorithm more easily tend to be non-
binary solutions. Specifically, the existence of non-binary solutions makes
the residuals in each Box ADMM iteration smaller than other methods (see Fig.
2). Also it verifies that introducing extra processing methods (penalty terms
or $\ell_{p}$-Box) to encourage binary solutions is feasible and effective.

Here, it should be noted that the proposed ADMM algorithm converge to the
stationary point of the approximate problem. The exact convergence analysis is
presented in Theorem 1.

###  V-B Aperiodic correlation Performance

Figure 4: Comparison of the averaged aperiodic ISLR/PSLR values for different
algorithms over $50$ independent trails.

Figure 5: Aperiodic correlation levels with $N=512,M=1,\mathds{L}=[1,N-1]$.

Figure 6: Aperiodic correlation levels with $N=1024,M=1,\mathds{L}=[1,N/2]$.

Figure 7: Aperiodic correlation levels with
$N=2048,M=1,\mathds{L}=\big{\\{}[1,N/4],[N/2,3N/4]\big{\\}}$.

Figure 8: Aperiodic correlation levels with $N=512,M=2,\mathds{L}=[0,N/2]$.

To evaluate the correlation properties of the binary sequences, we use the
normalized ISL/PSL in $dB$

$\begin{split}{\rm ISLR}=10\lg\frac{\rm ISL}{MN^{2}},\ {\rm
PSLR}=10\lg\frac{{\rm PSL}^{2}}{MN^{2}}.\end{split}$

Fig. 4-7 compare the correlation performance between the proposed ADMM
algorithm and the MM-WeCorr and BiST approach. The sequences obtained via
quantization of MM-WeCorr, named MM-WeCorr (Binary), is also considered.

From Fig. 4, it can be seen that the aperiodic ISLR/PSLR of the proposed
methods is similar to BiST, about $5\sim 6$ dB lower than that of the
initialization version. For MM-WeCorr with continuous phase, this difference
value is more than $10$ dB, which enjoys the best correlation performance for
both ISLR and PSLR. But the ISLR/PSLR of its quantified version (MM-WeCorr
(Binary)) is only $2$ dB lower than the initialization version, even less.
Thus it can be seen that direct quantization of the designed continuous phase
sequence has a large loss of performance, which fully explains the necessity
of designing binary sequence.

Fig. 5 shows the example of correlation comparison with parameter
$N=512,M=1,\mathds{L}=[1,N-1]$. Among the proposed algorithms, MM-WeCorr
(Binary)’s correlation performance is only better than the initialization
which As for Penalty Box/$\ell_{p}$-Box ADMM, their performance is similar to
that of the BiST approach.

Fig. 6 presented a set of experiments with shift interval
$\mathds{L}=[1,N/2],N=1024,M=1$. It should be noted that the shift interval in
comparison algorithm BiST cannot be flexibly selected. Therefore, the
experiment of its algorithm is missing. From the figure, it can be seen that
compared with the random initialization, the correlation level of the proposed
algorithm with $\mathds{L}=[1,N/2]$ is lower about $4$ dB, but for MM-WeCorr
(Binary), only $1$ dB. The correlation comparison with parameter
$N=2048,M=1,\mathds{L}=\big{\\{}[1,N/4],[N/2,3N/4]\big{\\}}$ is given in Fig.
7. Two shift intervals in $\mathds{L}$ lead MM-WeCorr (Binary) is difficult to
implemented, therefore the results is missing. The normalized correlation
level in $\mathds{L}$ of proposed algorithm is lower about $4\sim 5$ dB than
that of random initilization. Fig. 8 shows the autocorrelation and cross-
correlation level with $\mathds{L}=[0,N/2]$ of two sequences respectively.
From the figures, we can see that the correlation level of the sequence
generated by the proposed ADMM algorithm is lower on average $2$ dB than that
of the initialization sequence. However, the same results in Fig. 6 is $4\sim
5$ dB with $M=1$. The inconsistency between the results of Fig. 6 and Fig. 8
is probably caused by the lack of design degrees of freedom with the increase
of $M$.

All the results in Fig. 6 – 8 illustrate the flexibility selectable
correlation interval of the model proposed in this paper.

###  V-C Periodic correlation Performance

Figure 9: Comparison of the averaged periodic ISLR/PSLR values for different
algorithms over $50$ independent trails.

Figure 10: Periodic correlation levels with $N=1023,M=1,\mathds{L}=[1,N-1]$.

Fig. 10 shows the comparison of the averaged periodic ISLR/PSLR values for
different algorithms. Reference [51] presented that $2\sqrt{N}$ is the PSL of
the best known set of the structured sequences (i.e., Gold, Kasami,
$m-$sequences, etc.). In this paper, we consider $2\sqrt{N}$ as the periodic
PSL comparison benchmark. From the figure, it can be seen that the periodic
ISLR/PSLR of the proposed $\ell_{p}$-Box ADMM is similar to BiST, about $7\sim
8$ dB lower than that of the initialization version and $3\sim 4$ dB lower
than $2\sqrt{N}$. If the weight of penalty term in Penalty Box ADMM is
reasonably chosen, the periodic PSL correlation performance of the generated
sequence is a litter bit lower than that of $\ell_{p}$-Box ADMM. Since there
is no penalty weight, $\ell_{p}$-Box ADMM is easier to implement.

###  V-D Computational Complexity

TABLE III: computational complexity BiST | MM-WeCorr | proposed ADMM algorithm
---|---|---
$\mathcal{O}(MN^{3})$ | $\mathcal{O}(M^{2}N^{2})$ | $\mathcal{O}(M^{2}N|\mathds{L}|)$

The computational complexity in each iteration of the proposed ADMM algorithm
and two state-of-the-art algorithms is listed in Table III. Since
$|\mathds{L}|\leq N$ and $M<N$, we can conclude that the computational
complexity of the proposed algorithm is cheaper than BiST and MM-WeCorr.
Besides, MM-WeCorr can not be used directly to design binary sequence.
Moreover, notice that, unlike BiST and MM-WeCorr, the proposed algorithm can
be performed in parallel, which means that they are more suitable for large-
scale applications from a practical viewpoint of implementation.

##  VI Conclusion

In this paper, we formulated the binary sequences with low correlation
properties design problem as a nonconvex combination optimization model. Then,
an efficient algorithm, named by Box ADMM, was proposed to solve the
formulated problem. To encourage binary solutions, ADMM algorithm,
$\ell_{p}$-Box ADMM algorithm is proposed based on Box ADMM algorithm. We
proved that, if proper parameters are chosen, the proposed ADMM algorithm
converge to some stationary point of the approximate problem. Moreover, we
also provided the computational complexity of the proposed approaches.
Numerical experiments showed that, compared to the state-of-the-art methods,
the proposed algorithm can choose the optimized correlation interval flexibly
and obtain good correlation performance. Besides, the parallel implementation
structure makes the proposed algorithm be more suitable for large-scale
applications.

##  Appendix A Proof of Lemma 1

The idea of proving lemma 1 is based on the definition of Lipschitz
continuity.

###  A-A For $\nabla f^{2}_{ii,0}({\mathbf{X}})$

We have the derivations in (39).

$\begin{split}\frac{\|\nabla f_{ii,0}^{2}({\mathbf{\tilde{X}}})-\nabla
f_{ii,0}^{2}(\mathbf{\hat{X}})\|^{2}_{F}}{\|{\mathbf{\tilde{X}}}-\mathbf{\hat{X}}\|^{2}_{F}}\leq\max_{i,n}\left\\{\left|\frac{\frac{\partial
f_{ii,0}^{2}(\mathbf{\tilde{X}})}{\partial x_{i,n}}-\frac{\partial
f_{ii,0}^{2}(\mathbf{\hat{X}})}{\partial\hat{x}_{i,n}}}{\tilde{x}_{i,n}-\hat{x}_{i,n}}\right|^{2}\right\\}.\end{split}$
(39)

Since $f^{2}_{ii,0}(\mathbf{X})$ is continuous and differentiable (see (6)),
according to the Lagrangian mean value theorem, there exists some point
$\bar{x}_{i,n}\in(\tilde{x}_{i,n},\hat{x}_{i,n})$ which satisfies

$\frac{\frac{\partial
f_{ii,0}^{2}(\mathbf{\tilde{x}})}{\partial\tilde{x}_{i,n}}-\frac{\partial
f_{ii,0}^{2}(\mathbf{\hat{x}})}{\partial\hat{x}_{i,n}}}{\tilde{x}_{i,n}-\hat{x}_{i,n}}=\frac{\partial^{2}f_{ii,0}^{2}(\mathbf{x})}{\partial\bar{x}_{i,n}^{2}}.$
(40)

Plugging (40) into (39), we get

$\begin{split}\\!\\!\\!\\!\\!\\!\frac{\|\nabla
f_{ii,0}^{2}(\mathbf{\tilde{X}})\\!\\!-\\!\\!\nabla
f_{ii,0}^{2}(\mathbf{\hat{X}})\|_{F}}{\|{\mathbf{\tilde{X}}}-\mathbf{\hat{X}}\|_{F}}\\!\leq\max_{i,n}\\!\left\\{\\!\left|\frac{\partial^{2}f_{ii,0}(\mathbf{X})}{\partial\bar{x}_{i,n}^{2}}\right|\\!\right\\}\\!.\end{split}$
(41)

According to the definition of Lipschitz continuity, we prove Lemma 1 through
bounding the right-hand side of (41). Based on (37), we have the derivations
in (42).

$\begin{split}\left|\\!\frac{\partial^{2}f_{ii,0}^{2}(\mathbf{X})}{\partial\bar{x}_{i,n}^{2}}\\!\right|\\!\\!\leq\\!2\\!\left|\\!\text{Tr}\left(\\!\frac{\partial
f_{ii,0}}{\partial\bar{x}_{i,n}}\frac{\partial
f_{ii,0}}{\partial\bar{x}_{i,n}}\\!\right)\\!\right|\\!\\!+\\!\\!2\left|\\!\text{Tr}\left(\\!\frac{\partial^{2}f_{ii,0}}{\partial\bar{x}_{i,n}^{2}}f_{ii,0}\\!\right)\\!\right|.\end{split}$
(42)

Since $\tilde{x}_{i}\in[-c,c]$ and $\hat{x}_{i}\in[-1,1]$, we have
$\bar{x}_{i,n}\in(-\hat{c},\hat{c})$, where $\hat{c}=\max\\{c,1\\}$. From
(38), we can see that the maximum modulus of elements in
$\frac{\partial\mathbf{X}^{T}\mathbf{X}}{\partial{\bar{x}_{i,n}}}$ is
${\hat{c}}$ and so do it for
$\frac{\partial(\mathbf{s}_{i}^{T}\mathbf{X}^{T}\mathbf{X}\mathbf{s}_{i})}{\partial
x_{i,n}}$. Then, the first term on the right-hand side of (42) should satisfy

$\begin{split}2\left|\text{Tr}\left(\frac{\partial
f_{ii,0}}{\partial\bar{x}_{i,n}}\frac{\partial
f_{ii,0}}{\partial\bar{x}_{i,n}}\right)\right|\leq 2{\hat{c}}^{2}.\end{split}$
(43)

Since $\mathbf{X}\in\mathcal{X}_{B}$, the maximum modulus of elements in
$\mathbf{X}^{T}\mathbf{X}$ is $Nc_{1}^{2}$ and (38) indicates that
$\frac{\partial^{2}f_{ii,0}}{\partial\bar{x}_{i,n}^{2}}$ only has $1$ nonzero
elements. Therefore, we can obtain the following inequality for the second
term in (42)

$2\left|\text{Tr}\left(\frac{\partial^{2}f_{ii,0}}{\partial\bar{x}_{i,n}^{2}}f_{ii,0}\right)\right|\leq
2N{\hat{c}}^{2}.$ (44)

Plugging (43) and (44) into (42), we get

$\left|\frac{\partial^{2}f_{ii,0}^{2}(\mathbf{X})}{\partial\bar{x}_{i,n}^{2}}\right|<2(N+1){\hat{c}}^{2}.$
(45)

Through combining the boundness of
$\left|\frac{\partial^{2}f_{ii,0}^{2}(\mathbf{X})}{\partial\bar{x}_{i,n}^{2}}\right|$
with (41), we can conclude that $\nabla f_{ii,0}(\mathbf{X})$ is Lipschitz
continuous with the constant $L_{ii,0}\geq 2(N+1){\hat{c}}^{2}$.

###  A-B For $\nabla f^{2}_{o}({\mathbf{X}})$

Through similar above derivations, we have

$\left|\frac{\partial^{2}f_{o}^{2}(\mathbf{X})}{\partial\bar{x}_{i,n}^{2}}\right|<2(N+1){\hat{c}}^{2},$
(46)

which results in gradients $\nabla f_{o}(\mathbf{X}),l\in\mathds{{L}}$ being
Lipschitz continuous with constant $L_{o}\geq 2(N+1){\hat{c}}^{2}$.
$\hfill\blacksquare$

##  Appendix B Proof of Lemma 2–3

###  B-A Proof of Lemma 2

To facilitate the subsequent derivations, we define the following quantities

$\begin{split}\Delta_{\bar{\mathbf{X}}}^{k}&\\!\\!=\\!\mathcal{L}\\!\left({{\bar{\mathbf{X}}^{k}},{{\left\\{{\bar{\mathbf{Z}}_{o}^{k},{\mathbf{\Lambda}}_{o}^{k}}\\!\right\\}}_{o\in\mathbb{O}}}}\right)\\!-\\!\mathcal{L}\\!\left({{\bar{\mathbf{X}}^{k+1}},{{\left\\{{\bar{\mathbf{Z}}_{o}^{k},{\mathbf{\Lambda}}_{o}^{k}}\right\\}}_{o\in\mathbb{O}}}}\right),\\\
\Delta_{{\bar{\mathbf{Z}}_{o}}}^{k}&\\!\\!=\\!\mathcal{L}_{o}\\!\left(\bar{\mathbf{X}}^{k+1},\bar{\mathbf{Z}}_{o}^{k},\mathbf{\Lambda}_{o}^{k}\right)\\!-\\!\mathcal{L}_{o}\\!\left({\bar{\mathbf{X}}^{k+1}},{\bar{\mathbf{Z}}_{o}^{k+1},{\mathbf{\Lambda}}_{o}^{k}}\right),\\\
\Delta_{{{\mathbf{\Lambda}}_{o}}}^{k}&\\!\\!=\\!\mathcal{L}_{o}\\!\\!\left({{\bar{\mathbf{X}}^{k+1}},\bar{\mathbf{Z}}_{o}^{k+1},{\mathbf{\Lambda}}_{o}^{k}}\right)\\!-\\!\mathcal{L}_{o}\\!\\!\left({{\bar{\mathbf{X}}^{k+1}},\bar{\mathbf{Z}}_{o}^{k+1},{\mathbf{\Lambda}}_{o}^{k+1}}\right).\\\
\end{split}$

Then, the successive difference in Lemma 2 can be rewritten as

$\begin{split}&\mathcal{L}_{o}\\!\left(\\!{{{\mathbf{X}}^{k}},{{\left\\{{\bar{\mathbf{Z}}_{o}^{k},{\mathbf{\Lambda}}_{o}^{k}}\right\\}}_{o\in\mathbb{O}}}}\right)\\!\\!-\\!\mathcal{L}_{o}\\!\left({{{\mathbf{X}}^{k+1}},{{\left\\{{\bar{\mathbf{Z}}_{o}^{k+1},{\mathbf{\Lambda}}_{o}^{k+1}}\right\\}}_{o\in\mathbb{O}}}}\\!\right)\\\
&=\Delta_{\bar{\mathbf{X}}}^{k}+\sum\limits_{o\in\mathbb{O}}{\left({\Delta_{{\bar{\mathbf{Z}}_{o}}}^{k}+\Delta_{{{\mathbf{\Lambda}}_{o}}}^{k}}\right)}.\end{split}$
(47)

####  B-A1 For $\Delta_{\mathbf{X}}^{k}$

According to $\mathcal{L}_{o}(\cdot)$’s strong convexity related to
$\bar{\mathbf{X}}$, we get

$\begin{split}&\Delta_{\bar{\mathbf{X}}}^{k}\geq\left\langle{{\nabla_{\bar{\mathbf{X}}}}\mathcal{L}_{o}\left({{{\bar{\mathbf{X}}}^{k+1}},{{\left\\{{\bar{\mathbf{Z}}_{o}^{k},{\mathbf{\Lambda}}_{o}^{k}}\right\\}}_{l\in\mathbb{L}}}}\right),{{\bar{\mathbf{X}}}^{k}}-{{\bar{\mathbf{X}}}^{k+1}}}\right\rangle\\\
&\hskip
71.13188pt+\left(\sum\limits_{o\in\mathbb{O}}\frac{\rho_{o}}{2}\right)\left\|{\bar{\mathbf{X}}^{k+1}}-\bar{\mathbf{X}}^{k}\right\|_{F}^{2}.\end{split}$
(48)

Since
$\bar{\mathbf{X}}^{k+1}=\underset{\mathbf{X}_{1}\in\mathcal{X}_{B},\mathbf{X}_{2}\in\mathcal{X}_{S}}{\arg\min}\
\
\mathcal{L}_{o}\left(\bar{\mathbf{X}},\\{\bar{\mathbf{Z}}_{o}^{k},\mathbf{\Lambda}_{o}^{k}\\}_{o\in\mathbb{O}}\right)$,
we have

$\begin{split}\left\langle{{\nabla_{\bar{\mathbf{X}}}}\mathcal{L}_{o}\left({{{\bar{\mathbf{X}}}^{k+1}},{{\left\\{{{\mathbf{Z}}_{o}^{k},{\mathbf{\Lambda}}_{o}^{k}}\right\\}}_{o\in\mathbb{O}}}}\right),{{\bar{\mathbf{X}}}^{k}}-{{\bar{\mathbf{X}}}^{k+1}}}\right\rangle\geq
0.\end{split}$ (49)

Plugging it into (48), we obtain

$\begin{split}\Delta_{\bar{\mathbf{X}}}^{k}\geq\left(\sum\limits_{o\in\mathbb{O}}\frac{\rho_{o}}{2}\right)\left\|{\bar{\mathbf{X}}^{k+1}}-\bar{\mathbf{X}}^{k}\right\|_{F}^{2}.\end{split}$
(50)

####  B-A2 For $\Delta_{{{\mathbf{Z}}_{o}}}^{k}$

$\begin{split}\Delta_{{\bar{\mathbf{Z}}_{o}}}^{k}&\geq{\mathcal{L}_{o}}\left({{\bar{\mathbf{X}}^{k+1}},\bar{\mathbf{Z}}_{o}^{k},{\mathbf{\Lambda}}_{o}^{k}}\right)-{\mathcal{U}_{o}}\left({{{\bar{\mathbf{X}}}^{k+1}},\bar{\mathbf{Z}}_{o}^{k+1},{\mathbf{\Lambda}}_{o}^{k}}\right)\\\
&={\mathcal{L}_{o}}\left({{{\bar{\mathbf{X}}}^{k+1}},\bar{\mathbf{Z}}_{o}^{k},{\mathbf{\Lambda}}_{o}^{k}}\right)-{\mathcal{U}_{o}}\left({{{\bar{\mathbf{X}}}^{k+1}},\bar{\mathbf{Z}}_{o}^{k},{\mathbf{\Lambda}}_{o}^{k}}\right)\\\
&\ \
+{\mathcal{U}_{o}}\left({{{\bar{\mathbf{X}}}^{k+1}},\bar{\mathbf{Z}}_{o}^{k},{\mathbf{\Lambda}}_{o}^{k}}\right)-{\mathcal{U}_{o}}\left({{{\bar{\mathbf{X}}}^{k+1}},\bar{\mathbf{Z}}_{o}^{k+1},{\mathbf{\Lambda}}_{o}^{k}}\right)\\\
&=\Delta_{\mathcal{L}\mathcal{U}}^{k}+\Delta_{\mathcal{U}}^{k}\end{split}$
(51)

$\begin{split}&\ \Delta_{\mathcal{L}\mathcal{U}}^{k}\\\
&\\!=\\!{{w}}_{o}\bigg{[}{f_{o}^{2}({{\mathbf{Z}}_{o}^{k}})\\!\\!-\\!\\!f_{o}^{2}({{{\mathbf{X}}^{k+1}}})\\!\\!+\\!\\!\left\langle{\nabla
f_{o}^{2}({{{\mathbf{X}}^{k+1}}}),{{\mathbf{X}}^{k+1}}\\!\\!-\\!\\!{\mathbf{Z}}_{o}^{k}}\right\rangle}\\\
&\hskip
113.81102pt\left.{-\frac{{{L_{o}}}}{2}\left\|{{{\mathbf{X}}^{k+1}}-{\mathbf{Z}}_{o}^{k}}\right\|_{F}^{2}}\right]\\\
&{\overset{(a)}{\geq}}\ {{w}}_{o}\bigg{[}\left\langle{\nabla
f_{o}^{2}\left({{\mathbf{Z}}_{o}^{k}}\right)-\nabla
f_{o}^{2}\left({{{\mathbf{X}}^{k+1}}}\right),{{\mathbf{X}}^{k+1}}-{\mathbf{Z}}_{o}^{k}}\right\rangle\\\
&\hskip
113.81102pt\left.-{L_{o}}\left\|{{{\mathbf{X}}^{k+1}}-{\mathbf{Z}}_{o}^{k}}\right\|_{F}^{2}\right]\\\
&{\overset{(b)}{\geq}}-2{{w_{o}}}{L_{o}}\left\|{{{\mathbf{X}}^{k+1}}-{\mathbf{Z}}_{o}^{k}}\right\|_{F}^{2}\\\
&\geq-4{{w_{o}}}{L_{o}}\left\|{\frac{\mathbf{A}^{T}(\bar{\mathbf{X}}^{k+1}-\sigma\hat{\mathbf{Z}}_{o}^{k+1})}{2}-{\mathbf{Z}}_{o}^{k+1}}\right\|_{F}^{2}\\\
&\hskip
113.81102pt-4{{w_{o}}}{L_{o}}\left\|{{\mathbf{Z}}_{o}^{k+1}-{\mathbf{Z}}_{o}^{k}}\right\|_{F}^{2}\\\
&\geq-\frac{{2{{w_{o}}}{L_{o}}}}{{\rho_{o}^{2}}}\left\|{{\mathbf{\Lambda}}_{o}^{k+1}\\!\\!-\\!{\mathbf{\Lambda}}_{o}^{k}}\right\|_{F}^{2}\\!\\!-\\!4{{w_{o}}}{L_{o}}\left\|{{\mathbf{Z}}_{o}^{k+1}\\!-\\!{\mathbf{Z}}_{o}^{k}}\right\|_{F}^{2},\end{split}$
(52)

where (a) and (b) come from Lemma 1. Similar to (48), according to
$\mathcal{U}(\cdot)$’s strong convexity related to $\bar{\mathbf{Z}}$, we have

$\begin{split}\Delta_{\mathcal{U}}^{k}\geq\frac{{{\rho_{o}}\\!+\\!{{w_{o}}}{L_{o}}}}{2}\left\|{{\mathbf{Z}}_{o}^{k+1}\\!\\!-\\!{\mathbf{Z}}_{o}^{k}}\right\|_{F}^{2}\\!\\!+\\!\frac{\rho_{o}\sigma^{2}}{2}\left\|{\hat{\mathbf{Z}}_{o}^{k+1}\\!-\\!\hat{\mathbf{Z}}_{o}^{k}}\right\|_{F}^{2},\end{split}$
(53)

Plugging (52) and (53) into (51), we obtain

$\begin{split}&\Delta_{{{\mathbf{Z}}_{o}}}^{k}\\!\geq\\!\frac{{{\rho_{o}}\\!-\\!\\!7{{w_{o}}}{L_{o}}}}{2}\left\|{{\mathbf{Z}}_{o}^{k+1}\\!\\!-\\!\\!{\mathbf{Z}}_{o}^{k}}\right\|_{F}^{2}\\!\\!+\\!\\!\frac{\rho_{o}\sigma^{2}}{2}\left\|{\hat{\mathbf{Z}}_{o}^{k+1}\\!-\\!\hat{\mathbf{Z}}_{o}^{k}}\right\|_{F}^{2}\\\
&\hskip
99.58464pt+\frac{{-2{{w_{o}}}{L_{o}}}}{{\rho_{o}^{2}}}\\!\left\|{{\mathbf{\Lambda}}_{o}^{k+1}\\!\\!-\\!\\!{\mathbf{\Lambda}}_{o}^{k}}\\!\right\|_{F}^{2}.\end{split}$
(54)

####  B-A3 For $\Delta_{{{\mathbf{\Lambda}}_{o}}}^{k}$

$\begin{split}\Delta_{{{\mathbf{\Lambda}}_{o}}}^{k}&={\left\langle{{\mathbf{\Lambda}}_{o}^{k+1}-{\mathbf{\Lambda}}_{o}^{k},\bar{\mathbf{A}}\bar{\mathbf{Z}}_{o}^{k+1}-{\bar{\mathbf{X}}^{k+1}}}\right\rangle}\\\
&={-\frac{1}{{{\rho_{o}}}}\left\|{{\mathbf{\Lambda}}_{o}^{k+1}-{\mathbf{\Lambda}}_{o}^{k}}\right\|_{F}^{2}}.\end{split}$
(55)

Solving
$\nabla_{\bar{\mathbf{Z}}_{o}}\mathcal{U}_{o}(\bar{\mathbf{Z}}_{o})=0$, we get

$\begin{split}\mathbf{\Lambda}_{o}^{k+1}\\!\\!=\\!(\bar{\mathbf{A}}^{T})^{-1}\\!\\!\left[\\!\begin{array}[]{c}\\!\\!{w}_{o}\\!\left(\nabla
f_{o}^{2}({\mathbf{X}}^{k+1}\\!)\\!+\\!{L_{o}}({\mathbf{Z}}_{o}^{k+1}\\!\\!-\\!\\!{\mathbf{X}}^{k+1})\right)\\!\\!\\\
\sigma^{2}\hat{\mathbf{Z}}_{o}^{k+1}\\!\\!\end{array}\\!\right].\end{split}$
(56)

Plugging it into

$\begin{split}&\left\|{{\mathbf{\Lambda}}_{o}^{k+1}-{\mathbf{\Lambda}}_{o}^{k}}\right\|_{F}^{2}\\\
=&\left\|\frac{1}{2}\left[\begin{array}[]{ccc}\mathbf{I}_{N}&\frac{1}{\sigma}\mathbf{I}_{N}&-\frac{1}{\sigma}\mathbf{I}_{N}\\\
\mathbf{I}_{N}&-\frac{1}{\sigma}\mathbf{I}_{N}&\frac{1}{\sigma}\mathbf{I}_{N}\end{array}\right]\right.\\\
&\left.\cdot\\!\\!\left[\\!\begin{array}[]{c}\\!\\!\\!{{w}}_{o}\\!\left(\\!{\nabla\\!f_{o}^{2}\\!({{{\mathbf{X}}^{k+1}}}\\!)\\!\\!-\\!\\!\nabla\\!f_{o}^{2}\\!({{{\mathbf{X}}^{k}}}\\!)\\!\\!+\\!\\!{L_{o}}\\!({{{\mathbf{Z}}_{o}^{k+1}}\\!\\!\\!-\\!\\!{\mathbf{X}}^{k+1}\\!\\!\\!-\\!\\!{{\mathbf{Z}}_{o}^{k}}\\!\\!+\\!\\!{\mathbf{X}}^{k}}\\!)}\right)\\!\\!\\!\\\
\sigma^{2}(\hat{\mathbf{Z}}_{o1}^{k+1}-\hat{\mathbf{Z}}_{o1}^{k})\\\
\sigma^{2}(\hat{\mathbf{Z}}_{o2}^{k+1}-\hat{\mathbf{Z}}_{o2}^{k})\end{array}\\!\\!\right]\\!\\!\right\|_{F}^{2}\\\
\leq&w_{o}^{2}L_{o}^{2}\left(8\|{\mathbf{X}}^{k+1}-{\mathbf{X}}^{k}\|_{F}^{2}+2\|{\mathbf{Z}}_{o}^{k+1}-{\mathbf{Z}}_{o}^{k}\|_{F}^{2}\right)\\\
&\hskip
128.0374pt+\sigma^{2}\|\hat{\mathbf{Z}}_{o}^{k+1}-\hat{\mathbf{Z}}_{o}^{k}\|_{F}^{2}.\end{split}$
(57)

For $\|{\mathbf{X}}^{k+1}-{\mathbf{X}}^{k}\|_{F}^{2}$, we have

$\begin{split}&\|{\mathbf{X}}^{k+1}\\!\\!-\\!{\mathbf{X}}^{k}\|_{F}^{2}\\!\\!=\\!\\!\left\|\\!\frac{\mathbf{A}^{T}(\bar{\mathbf{X}}^{k+1}\\!\\!-\\!\\!\sigma\hat{\mathbf{Z}}_{o}^{k+1})}{2}\\!\\!-\\!\\!\frac{\mathbf{A}^{T}(\bar{\mathbf{X}}^{k}\\!\\!-\\!\\!\sigma\hat{\mathbf{Z}}_{o}^{k})}{2}\\!\right\|_{F}^{2}\\\
&\leq\frac{1}{4}\left(\\!2\|\mathbf{A}^{T}(\bar{\mathbf{X}}^{k+1}\\!\\!-\\!\\!\bar{\mathbf{X}}^{k})\|_{F}^{2}\\!\\!+\\!2\sigma^{2}\|\mathbf{A}^{T}(\hat{\mathbf{Z}}_{o}^{k+1}\\!\\!-\\!\\!\hat{\mathbf{Z}}_{o}^{k+1})\|_{F}^{2}\\!\right)\\\
&\leq\|\bar{\mathbf{X}}^{k+1}\\!-\\!\bar{\mathbf{X}}^{k}\|_{F}^{2}\\!+\\!\sigma^{2}\|\hat{\mathbf{Z}}_{o}^{k+1}\\!-\\!\hat{\mathbf{Z}}_{o}^{k+1}\|_{F}^{2}.\end{split}$
(58)

Plugging (50), (54), (55), (57) and (58) into (47), we get

$\begin{split}&\mathcal{L}_{o}\left(\bar{\mathbf{X}}^{k},\\{\bar{\mathbf{Z}}_{o}^{k},\mathbf{\Lambda}_{o}^{k}\\}_{o\in\mathbb{O}}\right)\\!-\\!\mathcal{L}_{o}\left(\bar{\mathbf{X}}^{k+1},\\{\bar{\mathbf{Z}}_{o}^{k+1},\mathbf{\Lambda}_{o}^{k+1}\\}_{o\in\mathbb{O}}\right)\\\
&\geq\\!\sum\limits_{o\in\mathbb{O}}\frac{1}{{2\rho_{o}^{2}}}\left(\bar{\epsilon}_{o}\left\|{{\bar{\mathbf{X}}^{k+1}}-{\bar{\mathbf{X}}^{k}}}\right\|_{F}^{2}+{\epsilon}_{o}\left\|{{\mathbf{Z}}_{o}^{k+1}-{\mathbf{Z}}_{o}^{k}}\right\|_{F}^{2}\right.\\\
&\hskip
113.81102pt\left.+\hat{\epsilon}_{o}\sigma^{2}\left\|{\hat{\mathbf{Z}}_{o}^{k+1}-\hat{\mathbf{Z}}_{o}^{k}}\right\|_{F}^{2}\right),\end{split}$

where

$\begin{split}\bar{\epsilon}_{o}&=\rho_{o}^{3}-16{w}_{o}^{2}L_{o}^{2}\rho_{o}-32{w}_{o}^{3}L_{o}^{3},\\\
{\epsilon}_{o}&=\rho_{o}^{3}-7{{w_{o}}}{L_{o}}\rho_{o}^{2}-4{w}_{o}^{2}L_{o}^{2}\rho_{o}-8{w}_{o}^{3}L_{o}^{3},\\\
\hat{\epsilon}_{o}&=\rho_{o}^{3}-(16{w}_{o}^{2}L_{o}^{2}+2)\rho_{o}-32{w}_{o}^{3}L_{o}^{3}-4{w}_{o}L_{o}.\end{split}$
(59)

If $\bar{\epsilon}_{o},{\epsilon}_{o},\hat{\epsilon}_{o}\geq 0$,
$\mathcal{L}_{o}\left(\bar{\mathbf{X}}^{k},\\{\bar{\mathbf{Z}}_{o}^{k},\mathbf{\Lambda}_{o}^{k}\\}_{o\in\mathbb{O}}\right)$
decreases sufficiently. This completes the proof. $\hfill\blacksquare$

###  B-B Proof of Lemma 3

Plugging (56) into
$\mathcal{L}_{o}\\!\left({{\bar{\mathbf{X}}^{k+1}},\\{\bar{\mathbf{Z}}_{o}^{k+1},{\mathbf{\Lambda}}_{o}^{k+1}}\\}_{o\in\mathbb{O}}\right)$,
we get (60). $\mathcal{L}_{\mathbf{Z}_{o}}$ and
$\mathcal{L}_{\bar{\mathbf{Z}}_{o}}$ can be bounded by (61) and (62).

$\begin{split}&\mathcal{L}_{o}\\!\left({{\bar{\mathbf{X}}^{k+1}},\\{\bar{\mathbf{Z}}_{o}^{k+1},{\mathbf{\Lambda}}_{o}^{k+1}}\\}_{o\in\mathbb{O}}\right)\\\
&={{w}}_{o}{f}_{o}^{2}\left({{\mathbf{Z}}_{o}^{k+1}}\right)+\frac{\sigma^{2}}{2}\hat{\mathbf{Z}}_{o}^{T}\hat{\mathbf{Z}}_{o}+\left\langle\frac{1}{2}\left[\\!\begin{array}[]{c}\\!\\!{w}_{o}\\!\left(\nabla
f_{o}^{2}({\mathbf{X}}^{k+1}\\!)\\!+\\!{L_{o}}({\mathbf{Z}}_{o}^{k+1}\\!\\!-\\!\\!{\mathbf{X}}^{k+1})\right)\\!+\\!\sigma(\hat{\mathbf{Z}}_{o1}^{k+1}\\!-\\!\hat{\mathbf{Z}}_{o2}^{k+1})\\!\\!\\\
\\!\\!{w}_{o}\\!\left(\nabla
f_{o}^{2}({\mathbf{X}}^{k+1}\\!)\\!+\\!{L_{o}}({\mathbf{Z}}_{o}^{k+1}\\!\\!-\\!\\!{\mathbf{X}}^{k+1})\right)\\!+\\!\sigma(\hat{\mathbf{Z}}_{o2}^{k+1}\\!-\\!\hat{\mathbf{Z}}_{o1}^{k+1})\\!\\!\end{array}\\!\right],\bar{\mathbf{X}}^{k+1}-\bar{\mathbf{A}}\bar{\mathbf{Z}}_{o}^{k+1}\right\rangle\\\
&\hskip
14.22636pt+\frac{\rho_{o}}{2}\left\|\bar{\mathbf{X}}^{k+1}-\bar{\mathbf{A}}\bar{\mathbf{Z}}_{o}^{k+1}\right\|_{F}^{2}\\\
&=\mathcal{L}_{\mathbf{Z}_{o}}+\mathcal{L}_{\bar{\mathbf{Z}}_{o}}+\frac{\rho_{o}}{2}\left\|\bar{\mathbf{X}}^{k+1}-\bar{\mathbf{A}}\bar{\mathbf{Z}}_{o}^{k+1}\right\|_{F}^{2}\\\
\end{split}$ (60)
$\begin{split}\mathcal{L}_{\mathbf{Z}_{o}}&={{w}}_{o}{f}_{o}^{2}\left({{\mathbf{Z}}_{o}^{k+1}}\right)+\left\langle\frac{1}{2}\left[\\!\begin{array}[]{c}\\!\\!{w}_{o}\\!\left(\nabla
f_{o}^{2}({\mathbf{X}}^{k+1}\\!)+{L_{o}}({\mathbf{Z}}_{o}^{k+1}-{\mathbf{X}}^{k+1})\right)\\\
\\!\\!{w}_{o}\\!\left(\nabla
f_{o}^{2}({\mathbf{X}}^{k+1}\\!)+{L_{o}}({\mathbf{Z}}_{o}^{k+1}-{\mathbf{X}}^{k+1})\right)\end{array}\\!\\!\right],\bar{\mathbf{X}}^{k+1}-\bar{\mathbf{A}}\bar{\mathbf{Z}}_{o}^{k+1}\right\rangle\\\
&={{w}}_{o}{f}_{o}^{2}\left({{\mathbf{Z}}_{o}^{k+1}}\right)+\left\langle\frac{1}{2}\left[\\!\begin{array}[]{c}\\!\\!{w}_{o}\\!\left(\nabla
f_{o}^{2}({\mathbf{X}}^{k+1}\\!)\\!+\\!{L_{o}}({\mathbf{Z}}_{o}^{k+1}\\!\\!-\\!\\!{\mathbf{X}}^{k+1})\right)\end{array}\\!\\!\right],2{\mathbf{X}}^{k+1}-2{\mathbf{Z}}_{o}^{k+1}\right\rangle\\\
&\overset{(a)}{\geq}w_{o}f_{o}^{2}\left({\mathbf{Z}}_{o}^{k+1}\right)+\left\langle
w_{o}\nabla
f_{o}^{2}\left(\mathbf{Z}_{o}^{k+1}\right),\mathbf{X}^{k+1}-\mathbf{Z}_{o}^{k+1}\right\rangle-2w_{o}L_{o}\left\|\mathbf{X}^{k+1}-\mathbf{Z}_{o}^{k+1}\right\|_{F}^{2}\\\
&\overset{(b)}{\geq}{{w}}_{o}{f}_{o}^{2}\left({\mathbf{X}}^{k+1}\right)-\frac{{5{{w}}_{o}{L_{o}}}}{2}\\!\left\|{\mathbf{X}}^{k+1}-{\mathbf{Z}}_{o}^{k+1}\right\|_{F}^{2}\\\
&\geq{{w}}_{o}{f}_{o}^{2}\left({\mathbf{X}}^{k+1}\right)-\frac{{5{{w}}_{o}{L_{o}}}}{4}\\!\left\|\bar{\mathbf{X}}^{k+1}-\bar{\mathbf{A}}\bar{\mathbf{Z}}_{o}^{k+1}\right\|_{F}^{2},\end{split}$
(61)
$\begin{split}\mathcal{L}_{\bar{\mathbf{Z}}_{o}}&=\frac{\sigma^{2}}{2}\hat{\mathbf{Z}}_{o}^{T}\hat{\mathbf{Z}}_{o}+\left\langle\frac{1}{2}\left[\\!\begin{array}[]{c}\\!\\!\sigma(\hat{\mathbf{Z}}_{o1}^{k+1}\\!-\\!\hat{\mathbf{Z}}_{o2}^{k+1})\\!\\!\\\
\\!\\!\sigma(\hat{\mathbf{Z}}_{o2}^{k+1}\\!-\\!\hat{\mathbf{Z}}_{o1}^{k+1})\\!\\!\\\
\end{array}\\!\right],\bar{\mathbf{X}}^{k+1}-\bar{\mathbf{A}}\bar{\mathbf{Z}}_{o}^{k+1}\right\rangle\\\
&=\frac{\sigma^{2}}{2}\hat{\mathbf{Z}}_{o}^{T}\hat{\mathbf{Z}}_{o}+\frac{1}{2}\left\langle\sigma(\hat{\mathbf{Z}}_{o1}^{k+1}\\!-\\!\hat{\mathbf{Z}}_{o2}^{k+1}),(\mathbf{X}_{1}^{k+1}-\sigma\hat{\mathbf{Z}}_{o1}^{k+1}-{\mathbf{Z}}^{k+1})-(\mathbf{X}_{2}^{k+1}-\sigma\hat{\mathbf{Z}}_{o2}^{k+1}-{\mathbf{Z}}^{k+1})\right\rangle\\\
&\geq\frac{\sigma^{2}}{2}\hat{\mathbf{Z}}_{o}^{T}\hat{\mathbf{Z}}_{o}-\frac{1}{4}\left\|\sigma(\hat{\mathbf{Z}}_{o1}^{k+1}\\!-\\!\hat{\mathbf{Z}}_{o2}^{k+1})\right\|_{F}^{2}-\frac{1}{4}\left\|(\mathbf{X}_{1}^{k+1}-\sigma\hat{\mathbf{Z}}_{o1}^{k+1}-{\mathbf{Z}}^{k+1})-(\mathbf{X}_{2}^{k+1}-\sigma\hat{\mathbf{Z}}_{o2}^{k+1}-{\mathbf{Z}}^{k+1})\right\|_{F}^{2}\\\
&\geq-\frac{1}{4}\left(2\left\|(\mathbf{X}_{1}^{k+1}-\sigma\hat{\mathbf{Z}}_{o1}^{k+1}-{\mathbf{Z}}^{k+1})\right\|_{F}^{2}+2\left\|(\mathbf{X}_{2}^{k+1}-\sigma\hat{\mathbf{Z}}_{o2}^{k+1}-{\mathbf{Z}}^{k+1})\right\|_{F}^{2}\right)\\\
&=-\frac{1}{2}\left\|\bar{\mathbf{X}}^{k+1}-\bar{\mathbf{A}}\bar{\mathbf{Z}}_{o}^{k+1}\right\|_{F}^{2},\end{split}$
(62)

where (a) and (b) come from the Lipschitz continuity of the gradient of
$\nabla f_{o}^{2}\left({{{\mathbf{X}}}}\right)$. Plugging(61) and (62) into
(60) we can obtain

$\begin{split}&\mathcal{L}_{o}\\!\\!\left({{\bar{\mathbf{X}}^{k+1}},\\{\bar{\mathbf{Z}}_{o}^{k+1},{\mathbf{\Lambda}}_{o}^{k+1}}\\}_{o\in\mathbb{O}}\right)\\\
&\geq{{w}}_{o}{f}_{o}^{2}\left({{{\mathbf{X}}^{k+1}}}\right)\\!\\!+\\!\\!\frac{{2{\rho_{o}}\\!\\!-\\!5{{w}}_{o}{L_{o}}}\\!-\\!2}{4}\\!\left\|{{\bar{\mathbf{X}}^{k+1}}\\!\\!-\\!\\!\bar{\mathbf{A}}\bar{\mathbf{Z}}_{o}^{k+1}}\right\|_{F}^{2},\end{split}$
(63)

Since ${w}_{o}{f}_{o}^{2}\left({{{\mathbf{X}}^{k+1}}}\right)\geq 0$, if
$2{\rho_{o}}\\!\\!-\\!5w_{o}L_{o}\\!-\\!2\geq 0$, $\mathcal{L}_{o}(\cdot)$ is
lower bounded. $\hfill\blacksquare$

##  Appendix C Proof of Theorem 1

###  C-A For Box ADMM algorithm

We desire the conditions in Lemmas 2-3 hold, i.e.,
$\tilde{\epsilon}_{o},\bar{\epsilon}_{o}\geq 0$, and $\rho_{o}\geq
5\bar{w}_{o}L_{o}$. Through the famous Cardano formula [52], we can get that
when $\rho_{o}\geq 7.8\bar{w}_{o}L_{o}$ and $\rho_{o}\geq
5.3\bar{w}_{o}L_{o}$, $\tilde{\epsilon}_{o},\bar{\epsilon}_{o}\geq 0$ hold.
Therefore, we conclude that when $\rho_{o}\geq 7.8\bar{w}_{o}L_{o}$, all
conditions in Lemmas 2-3 hold. To simplify the description, we choose $\forall
l\in\mathds{{L}},\rho_{o}\geq 8\bar{w}_{o}L_{o}$.

For $k=1,2,\cdots,+\infty$, summing both sides of (31), we can obtain

$\begin{split}&\mathcal{L}_{o}\left(\bar{\mathbf{X}}^{1},\\{\bar{\mathbf{Z}}_{o}^{1},\mathbf{\Lambda}_{o}^{1}\\}_{o\in\mathbb{O}}\right)\\!-\\!\mathcal{L}_{o}\left(\bar{\mathbf{X}}^{k+1},\\{\bar{\mathbf{Z}}_{o}^{k+1},\mathbf{\Lambda}_{o}^{k+1}\\}_{o\in\mathbb{O}}\right)\\\
&\geq\\!\sum\limits_{k=1}^{+\infty}\sum\limits_{o\in\mathbb{O}}\frac{1}{{2\rho_{o}^{2}}}\left(\bar{\epsilon}_{o}\left\|{{\bar{\mathbf{X}}^{k+1}}-{\bar{\mathbf{X}}^{k}}}\right\|_{F}^{2}+{\epsilon}_{o}\left\|{{\mathbf{Z}}_{o}^{k+1}-{\mathbf{Z}}_{o}^{k}}\right\|_{F}^{2}\right.\\\
&\hskip
128.0374pt\left.+\hat{\epsilon}_{o}\sigma^{2}\left\|\hat{\mathbf{Z}}_{o}^{k+1}-\hat{\mathbf{Z}}_{o}^{k}\right\|_{F}^{2}\right).\end{split}$

According to the boundness of
$\mathcal{L}_{o}\\!\left({{\bar{\mathbf{X}}^{k+1}},\\{\bar{\mathbf{Z}}_{o}^{k+1},{\mathbf{\Lambda}}_{o}^{k+1}}\\}_{o\in\mathbb{O}}\right)$,
above equation can rewritten as

$\begin{split}&\mathcal{L}_{o}\left(\bar{\mathbf{X}}^{1},\\{\bar{\mathbf{Z}}_{o}^{1},\mathbf{\Lambda}_{o}^{1}\\}_{o\in\mathbb{O}}\right)\\\
&\geq\\!\sum\limits_{k=1}^{+\infty}\sum\limits_{o\in\mathbb{O}}\frac{1}{{2\rho_{o}^{2}}}\left(\bar{\epsilon}_{o}\left\|{{\bar{\mathbf{X}}^{k+1}}-{\bar{\mathbf{X}}^{k}}}\right\|_{F}^{2}+{\epsilon}_{o}\left\|{{\mathbf{Z}}_{o}^{k+1}-{\mathbf{Z}}_{o}^{k}}\right\|_{F}^{2}\right.\\\
&\hskip
128.0374pt\left.+\hat{\epsilon}_{o}\sigma^{2}\left\|\hat{\mathbf{Z}}_{o}^{k+1}-\hat{\mathbf{Z}}_{o}^{k}\right\|_{F}^{2}\right).\end{split}$

Since $\bar{\epsilon}_{o},\epsilon_{o},\hat{\epsilon}_{o}\geq 0$ and
$\mathcal{L}_{o}\\!\left({{\bar{\mathbf{X}}^{k+1}},\\{\bar{\mathbf{Z}}_{o}^{k+1},{\mathbf{\Lambda}}_{o}^{k+1}}\\}_{o\in\mathbb{O}}\right)$
is finite, we conclude that

$\begin{split}\lim_{k\rightarrow+\infty}\|{{\bar{\mathbf{X}}^{k+1}}-{\bar{\mathbf{X}}^{k}}}\|_{F}=0,\
\lim_{k\rightarrow+\infty}\|{\bar{\mathbf{Z}}_{o}^{k+1}-\bar{\mathbf{Z}}_{o}^{k}}\|_{F}=0.\end{split}$
(64)

Combining (57) and (15c), we get

$\begin{split}\lim_{k\rightarrow+\infty}\|{{{\mathbf{\Lambda}}_{o}^{k+1}}-{{\mathbf{\Lambda}}_{o}^{k}}}\|_{F}=0,\
\lim_{k\rightarrow+\infty}\|{\bar{\mathbf{X}}^{k+1}-\bar{\mathbf{A}}\bar{\mathbf{Z}}_{o}^{k+1}}\|_{F}=0.\end{split}$
(65)

$\left(\bar{\mathbf{X}}^{*},\\{\bar{\mathbf{Z}}_{o}^{*},\mathbf{\Lambda}_{o}^{*}\\}_{o\in\mathbb{O}}\right)$
denote some limit point of the proposed ADMM algorithm. Since
$\mathbf{X}_{1}\in\mathcal{X}_{B}$, $\mathbf{X}_{2}\in\mathcal{X}_{S}$, (64)
indicates $\bar{\mathbf{X}}^{k}$ converges to some limit point as
$k\rightarrow+\infty$, i.e.,

$\begin{split}\lim_{k\rightarrow+\infty}\bar{\mathbf{X}}^{k}=\bar{\mathbf{X}}^{*}.\end{split}$
(66)

Combining it with (65), we can see that $\\{\bar{\mathbf{Z}}_{o}^{k}\\}$
converges. From (56), we can obtain

$\begin{split}\bar{\mathbf{A}}^{T}\mathbf{\Lambda}_{o}^{k+1}\\!\\!=\\!\\!\left[\\!\begin{array}[]{c}\\!\\!{w}_{o}\\!\left(\nabla
f_{o}^{2}({\mathbf{X}}^{k+1}\\!)\\!+\\!{L_{o}}({\mathbf{Z}}_{o}^{k+1}\\!\\!-\\!\\!{\mathbf{X}}^{k+1})\right)\\!\\!\\\
\sigma^{2}\hat{\mathbf{Z}}_{o}^{k+1}\\!\\!\end{array}\\!\right].\end{split}$
(67)

Since
$\lim\limits_{k\rightarrow+\infty}{\mathbf{Z}}_{o}^{k}-{\mathbf{X}}^{k}=0$ and
$\nabla f_{o}^{2}({\mathbf{X}}^{k}\\!)$ is Lipschitz continuous, (67) can be
rewritten as

$\begin{split}\bar{\mathbf{A}}^{T}\mathbf{\Lambda}_{o}^{*}\\!\\!=\\!\\!\left[\begin{array}[]{c}\\!\\!{w}_{o}\\!\nabla
f_{o}^{2}({\mathbf{X}}^{*}\\!)\\\
\sigma^{2}\hat{\mathbf{Z}}_{o}^{*}\\!\\!\end{array}\right].\end{split}$ (68)

which means $\\{\mathbf{\Lambda}_{o}^{k}\\}$ converges. Based on (65), it can
be obtained

$\begin{split}{\bar{\mathbf{X}}^{*}=\bar{\mathbf{A}}\bar{\mathbf{Z}}_{o}^{*}}.\end{split}$
(69)

(68) and (69) indicate that $\bar{\mathbf{Z}}_{o}^{*}$ is a stationary point
of approximate problem(23). Utilizing (12), we get

$\begin{split}\|{\bar{\mathbf{X}}^{k+1}-{\mathbf{A}}{\mathbf{Z}}_{o}^{k+1}}\|&=\|\frac{1}{\rho_{o}}(\mathbf{\Lambda}_{o}^{k+1}-\mathbf{\Lambda}_{o}^{k})+\sigma\hat{\mathbf{Z}}_{o}^{k+1}\|\\\
&\leq\|\frac{1}{\rho_{o}}(\mathbf{\Lambda}_{o}^{k+1}-\mathbf{\Lambda}_{o}^{k})\|+\|\sigma\hat{\mathbf{Z}}_{o}^{k+1}\|.\end{split}$
(70)

Combining it with (65), we can obtain

$\begin{split}\lim_{k\rightarrow+\infty}\|{\bar{\mathbf{X}}^{k+1}-{\mathbf{A}}{\mathbf{Z}}_{o}^{k+1}}\|=\|{\bar{\mathbf{X}}^{*}-{\mathbf{A}}{\mathbf{Z}}_{o}^{*}}\|\leq\|\sigma\hat{\mathbf{Z}}_{o}^{*}\|=\mathcal{O}(\sigma),\end{split}$
(71)

which means that the stationary point $\bar{\mathbf{Z}}_{o}^{*}$ is close to
the stationary point of the original problem (10) within the range
$\mathcal{O}(\sigma)$.

$\hfill\blacksquare$

## References

  * [1] D. Chu, “Polyphase codes with good periodic correlation properties,” _IEEE Trans. Inf. Theory_ , vol. 18, no. 4, pp. 531-532, Jul. 1972.
  * [2] G. Gong, F. Huo, and Y. Yang, “Large zero autocorrelation zones of Golay sequences and their applications,” _IEEE Trans. Commun._ , vol. 61, no. 9, pp. 3967-3979, Sep. 2013.
  * [3] J. M. Velazquez-Gutierrez and C. Vargas-Rosales, “Sequence sets in wireless communication systems: A survey,” _IEEE Communications Surveys & Tutorials_, vol. 19, no. 2, pp. 1225-1248, 2017.
  * [4] Z. Liu, Y. L. Guan, and U. Parampalli, “New complete complementary codes for peak-to-mean power control in multi-carrier CDMA,” _IEEE Trans. Commun._ , vol. 62, no. 3, pp. 1105-1113, Mar. 2014.
  * [5] A. Milewski, “Periodic sequences with optimal properties for channel estimation and fast start-up equalization,” _IBM J. Res. Develop._ , vol. 27, no. 5, pp. 425-431, Sep. 1983.
  * [6] S.-H. Choi, J.-S. Baek, J.-S. Han, and J.-S. Seo, “Channel estimations using extended orthogonal codes for AF multiple-relay networks over frequency-selective fading channels,” _IEEE Trans. Veh. Technol._ , vol. 63, no. 1, pp. 417-423, Jan. 2014.
  * [7] U. Lambrette, M. Speth, and H. Meyr, “OFDM burst frequency synchronization by single carrier training data,” _IEEE Commun. Lett._ , vol. 1, no. 2, pp. 46-48, Mar. 1997.
  * [8] M. J. Golay, “Complementary series,” _IEEE Trans. Inf. Theory_ , vol. 7, no. 2, pp. 82-87, Apr. 1961.
  * [9] X. Tang and W.-H. Mow, “Design of spreading codes for quasisynchronous CDMA with intercell interference,” _IEEE J. Sel. Areas Commun._ , vol. 24, no. 1, pp. 84-93, Jan. 2006.
  * [10] S. W. Golomb, L. R. Welch, R. M. Goldstein, and A. W. Hales, _Shift Register Sequences_ , vol. 78. Laguna Hills, CA, USA: Aegean Park, 1982.
  * [11] J. Lahtonen, “On the odd and the aperiodic correlation properties of the Kasami sequences,” _IEEE Trans. Inf. Theory_ , vol. 41, no. 5, pp. 1506-1508, Sep. 1995.
  * [12] R. Gold, “Maximal recursive sequences with 3-valued recursive crosscorrelation functions (corresp.),” _IEEE Trans. Inf. Theory_ , vol. 14, no. 1, pp. 154-156, Jan. 1968.
  * [13] R. H. Barker, “Group synchronizing of binary digital systems,” _Communication Theory_. London, U.K.: Butterworth, 1953, pp. 273-287.
  * [14] P. V. Kumar and R. A. Scholtz, “Bounds on the linear span of bent sequences,” _IEEE Trans. Inf. Theory_ , vol. 29, no. 6, pp. 854-862, Nov. 1983.
  * [15] R. Turyn and J. Storer, “On binary sequences,” _Proc. Amer. Math. Soc._ , vol. 12, no. 3, pp. 394-399, 1961.
  * [16] K. H. Leung, and B. Schmidt, “The field descent method,” _Designs, Codes and Cryptography_ , vol. 36, no. 2, pp. 171-188, 2005.
  * [17] P. Z. Fan, N. Suehiro, N. Kuroyanagi, and X. M. Deng, “Class of binary sequences with zero correlation zone,” _Electron. Lett._ , vol. 35, no. 10, pp. 777-779, May 1999.
  * [18] J.-S. Chung and J.-S. No, “Low correlation zone sequences,” in _Sequences and Their Applications-SETA 2010_. Heidelberg, Germany: Springer-Verlag, 2010, pp. 1-29.
  * [19] A. Klapper, A. H. Chan and M. Goresky, “Cascaded GMW sequences,” _IEEE Trans. Inf. Theory_ , vol. 39, no. 1, pp. 177-183, Jan. 1993.
  * [20] Jong-Seon No, S. W. Golomb, Guang Gong, Hwan-Keun Lee and P. Gaal, “Binary pseudorandom sequences of period 2n-1 with ideal autocorrelation,” _IEEE Trans. Inf. Theory_ , vol. 44, no. 2, pp. 814-817, March 1998.
  * [21] S. Mertens, “Exhaustive search for low-autocorrelation binary sequences,” _J. Phys. A: Math. Gen._ , vol. 29, no. 18, pp. 473-481, 1996.
  * [22] Hai Deng, “Polyphase code design for orthogonal netted radar systems,” _IEEE Trans. Signal Process._ , vol. 52, no. 11, pp. 3126-3135, Nov. 2004.
  * [23] S. Wang, “Efficient heuristic method of search for binary sequences with good aperiodic autocorrelations,” _Electron. Lett._ , vol. 44, no. 12, pp. 731-732, 2008.
  * [24] C. Warty, S. Mattigiri, E. Gambi, and S. Spinsante, “De Bruijn sequences as secure spreading codes for wireless communications,” _Proc. Int. Conf. Adv. Comput. Commun. Informat. (ICACCI)_ , Mysore, India, Aug. 2013, pp. 315-320.
  * [25] Guang Gong, “Theory and applications of q-ary interleaved sequences,” _IEEE Trans. Inf. Theory_ , vol. 41, no. 2, pp. 400-411, Mar. 1995.
  * [26] N. Li and X. Tang, “On the linear complexity of binary sequences of period 4N with optimal autocorrelation value/magnitude,” _IEEE Trans. Inf. Theory_ , vol. 57, no. 11, pp. 7597-7604, Nov. 2011.
  * [27] X. Tang, G. Gong, “New constructions of binary sequences with optimal autocorrelation value/magnitude,” _IEEE Trans. Inf. Theory_ , vol. 56, no. 3, pp. 1278-1286, Mar. 2010.
  * [28] N. Yu and G. Gong, “New binary sequences with optimal autocorrelation magnitude,” _IEEE Trans. Inf. Theory_ , vol. 54, no. 10, pp. 4771-4779, Oct. 2008.
  * [29] Q. Wang and X. Du, “The linear complexity of binary sequences with optimal autocorrelation,” _IEEE Trans. Inf. Theory_ , vol. 56, no. 12, pp. 6388-6397, Dec. 2010.
  * [30] W. Su, Y. Yang, and C. Fan, “New optimal binary sequences with period 4p via interleaving Ding-Helleseth-Lam sequences,” _Des. Codes Cryptogr._ , vol. 86, no. 6, pp. 1329-1338, Jun. 2018.
  * [31] J. Song, P. Babu, and D. P. Palomar, “Optimization methods for designing sequences with low autocorrelation sidelobes,” _IEEE Trans. Signal Process._ , vol. 63, no. 15, pp. 3998-4009, Aug. 2015.
  * [32] J. Song, P. Babu, and D. P. Palomar, “Sequence set design with good correlation properties via majorization-minimization,” _IEEE Trans. Signal Process._ , vol. 64, no. 11, pp. 2866-2879, Feb. 2016.
  * [33] J. Liang, H. C. So, J. Li, and A. Farina, “Unimodular sequence design based on alternating direction method of multipliers,” _IEEE Trans. Signal Process._ , vol. 64, no. 20, pp. 5367-5381, Oct. 2016.
  * [34] Z. Cheng, Z. He, S. Zhang and J. Li, “Constant modulus waveform design for MIMO radar transmit beampattern,” _IEEE Trans. Signal Process._ , vol. 65, no. 18, pp. 4912-4923. Sep. 2017.
  * [35] J. Wang and Y. Wang, “On the design of constant modulus probing waveforms with good correlation properties for MIMO radar via consensus-ADMM approach,” _IEEE Trans. Signal Process._ , vol. 67, no. 16, pp. 4317-4332, Aug. 2019.
  * [36] A. Bose and M. Soltanalian, “Constructing binary sequences with good correlation properties: an efficient analytical-computational interplay,” _IEEE Trans. Signal Process._ , vol. 66, no. 11, pp. 2998-3007, Jun. 2018.
  * [37] D. Mo and M. F. Duarte, “Binary sequence set design for interferer rejection in multi-branch modulation,” _IEEE Trans. Signal Process._ , vol. 68, pp. 3769-3778, Jun. 2020.
  * [38] 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 Trans. Signal Process._ , vol. 65, no. 22, pp. 5942-5956, Nov. 2017.
  * [39] M. A. Kerahroodi, M. Modarres-Hashemi and M. M. Naghsh, “Designing sets of binary sequences for MIMO radar systems,” _IEEE Trans. Signal Process._ , vol. 67, no. 13, pp. 3347-3360, Jul. 2019.
  * [40] G. Cui, X. Yu, G. Foglia, Y. Huang and J. Li, “Quadratic optimization with similarity constraint for unimodular sequence synthesis,” _IEEE Trans. Signal Process._ , vol. 65, no. 18, pp. 4756-4769, Sep. 2017.
  * [41] X. Yu, G. Cui, J. Yang, J. Li and L. Kong, “Quadratic Optimization for Unimodular Sequence Design via an ADPM Framework,” _IEEE Trans. Signal Process._ , vol. 68, pp. 3619-3634, May. 2020.
  * [42] J. Zhang and N. Xu, “Discrete phase coded sequence set design for waveform-agile radar based on alternating direction method of multipliers,” _IEEE Trans. Aerosp. Electron. Syst._ , vol. 56, no. 6, pp. 4238-4252, Dec. 2020.
  * [43] Y.-C. Wang, X. Wang, H. Liu, and Z.-Q. Luo, “On the design of constant modulus probing signals for MIMO radar,” _IEEE Trans. Signal Process._ , vol. 60, no. 8, pp. 4432-4438, Aug. 2012.
  * [44] Z. Lin, W. Pu and Z. Luo, “Minimax design of constant modulus MIMO waveforms for active sensing,” _IEEE Signal Processing Letters_ , vol. 26, no. 10, pp. 1531-1535, Oct. 2019.
  * [45] X. Dai, H. Zhang, and Y. Wang, “New sequence design criteria for multipath channels,” _IEEE Trans. Veh. Technol._ , vol. 58, no. 8, pp. 4149-4157, Oct. 2009.
  * [46] J. Song, P. Babu, and D. Palomar, “Sequence design to minimize the weighted integrated and peak sidelobe levels,” _IEEE Trans. Signal Process._ , vol. 64, no. 8, pp. 2051-2064, Apr. 2016.
  * [47] W. Fan, J. Liang, G. Yu, H. C. So and G. Lu, “MIMO radar waveform design for quasi-equiripple transmit beampattern synthesis via weighted $l_{p}$-minimization,” _IEEE Trans. Signal Process._ , vol. 67, no. 13, pp. 3397-3411, Jul. 2019.
  * [48] D. P. Bertsekas, _Nonlinear Programming_. Belmont, MA, USA: Athena Scientific, pp. 667-668, 2nd ed., 1999.
  * [49] B. Wu and B. Ghanem, “$\ell_{p}$-Box ADMM: a versatile framework for integer programming,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 41, no. 7, pp. 1695-1708, Jul. 2019.
  * [50] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, “Distributed optimization and statistical learning via the alternating direction method of multipliers,” _Found. Trend. Mach. Learn._ , vol. 3, no. 1, pp. 1-122, Jan. 2011.
  * [51] Y. K. Han and K. Yang, “New M-ary sequencefamilies with low correlation and large size.” _IEEE Trans. Inf. Theory,_ vol. 55, no. 5, pp. 1815-1823, Apr. 2009.
  * [52] R. Wituła and D. Słota, “Cardano’s formula, square roots, Chebyshev polynomials and radicals,” _J. Optim. Theory Appl.,_ vol. 2, no. 363, pp. 639-647, 2010.