# Peeling Decoding of LDPC Codes with Applications in Compressed Sensing

Authors: Weijun Zeng; Huali Wang
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

We present a new approach for the analysis of iterative peeling decoding recovery algorithms in the context of Low-Density Parity-Check (LDPC) codes and compressed sensing. The iterative recovery algorithm is particularly interesting for its low measurement cost and low computational complexity. The asymptotic analysis can track the evolution of the fraction of unrecovered signal elements in each iteration, which is similar to the well-known density evolution analysis in the context of LDPC decoding algorithm. Our analysis shows that there exists a threshold on the density factor; if under this threshold, the recovery algorithm is successful; otherwise it will fail. Simulation results are also provided for verifying the agreement between the proposed asymptotic analysis and recovery algorithm. Compared with existing works of peeling decoding algorithm, focusing on the failure probability of the recovery algorithm, our proposed approach gives accurate evolution of performance with different parameters of measurement matrices and is easy to implement. We also show that the peeling decoding algorithm performs better than other schemes based on LDPC codes.


---

## Body

## 1. Introduction

Compressed sensing (CS) is a novel signal sampling theory that exploits the sparsity of signal [1, 2]. In the noiseless settings, the CS problem can be considered as estimating an original sparse signal x
∈
R
n from the linear measurement vector y
∈
R
m, m
≪
n; that is, y
=
H
x, where H is referred to as measurement matrix; this measurement process is also referred to asencoding. Generally, without additional information, it is impossible to recover x from y in the case m
≪
n. The signal x
∈
R
n is called k-sparse if the signal has no more than k nonzero entries, for k-sparse signal and with an appropriate measurement matrix H, even though when m
≪
n, y essentially contains enough information to recover the original signal x; this recovery process is also referred to asdecoding.Candés et al. in [1, 2] used the Gaussian random matrix as the measurement matrix and the l
1 norm minimization to recover the original signal. However, most of elements in Gaussian random matrix are nonzero, which requires a lot of storage space. Furthermore, these random matrices are often difficult or expensive in hardware implementation. Recently, many researchers have exploited some excellent sparse matrices of channel coding into the CS system [3–5]; compared with random measurement matrices, the sparse matrices could reduce the storage space and are easy to implement in hardware. As a special class of sparse matrices, the parity-check matrices of Low-Density Parity-Check (LDPC) codes can be used as good measurement matrices for CS under l
1 norm minimization [3]. In [3], the authors have pointed out that the l
1 norm minimization decoding of LDPC codes is very similar to the l
1 norm minimization of CS. Inspired by the work of [3], the authors of [4, 5] constructed a class of deterministic measurement matrices from finite geometry LDPC (FG-LDPC) codes. However, these works only focus on the construction of measurement matrices.From the class of measurement matrix, decoding algorithms can be assorted as algorithms with dense matrices and sparse matrices. Generally, decoding algorithms based on sparse matrices have lower complexity than the algorithms associated with dense matrices. As shown in our analysis in Section3, the decoding algorithm with sparse matrices is faster than the algorithms using dense matrices. Since the random dense matrices satisfy the well-known restricted isometry property (RIP) with high probability, the standard decoding algorithms for these matrices are in line with greedy or convex programming [1, 2, 6, 7]. The RIP is a sufficient condition which guarantees unique and perfect recovery of sparse signals via l
1-minimization [2]. It has been shown that the sparse matrices do not satisfy RIP when m
<
Ω
(
k
2
) [8]. However, the decoding algorithms with sparse matrices explore the insights from coding theory to assist in sparse recovery. In fact, through the design of sparse measurement matrices and decoding algorithm, both the measurement cost and decoding complexity can be simultaneously reduced.For the complexity of recovery algorithm, thel
1 norm minimization has a computation complexity of O
(
n
3
). To reduce this complexity, with the sparse measurement matrices, various low computational complexity message-passing algorithms have been introduced for reconstruction of sparse signals in CS [9–22]. In [9], the authors used the random sparse matrix as a new sparse measurement matrix and proposed an iterative algorithm of complexity of O
(
k
log
⁡
k
log
⁡
(
n
)
), while it only required m
=
O
(
k
log
⁡
(
n
)
) measurements. It was essentially the same as the ideal of verification decoding of packet-based LDPC codes in [23] and is rediscovered by Zhang in [11]. These verification-based (VB) recovery algorithms in the context of CS have been analyzed rigorously via the density evolution in [10, 11]. In [12], the VB algorithm was applied to the wideband spectrum sensing, where the measurement matrix is designed based on a block sparse matrix. Based on special nonnegative sparse signals, a new message-passing algorithm, called the Interval-Passing (IP) algorithm, was proposed in [13], which has a better performance than the VB algorithm in [11]. In [14], a combination scheme of both the IP algorithm and the VB algorithm was proposed for nonnegative sparse signals, which can perform better than either the IP algorithm or the VB algorithm. Based on expander graphs of the sparse measurement matrix, Jafarpour et al. in [15, 16] proposed a different iterative algorithm with a complexity of O
(
n
log
⁡
(
n
/
k
)
) using O
(
k
log
⁡
(
n
/
k
)
) measurements in the noiseless case. It should be worth noting that the above fast recovery algorithms only can get rid of the noiseless case.For the noise case, in [17], the authors assumed signal as Gaussian mixture priors and proposed a belief propagation (BP) algorithm. The main disadvantage with this approach is that decoding complexity grows exponentially. In a similar work [18], the authors assumed signal as Jeffreys’ priors and applied well-known least-squares algorithms to recover the signal. However, in [18], the sparsity k was assumed to be known.To overcome the restriction of the decoding algorithms discussed above, Pawar et al. in [19–22] designed a hybrid mix of the LDPC codes and Discrete Fourier Transform (DFT) framework (LDPC-DFT) and proposed a fast Short-and-Wide Iterative Fast Transform (SWIFT) peeling decoding recovery algorithm. It only needs O
(
k
) measurements and O
(
k
) iterative step to achieve the exact signal recovery in the noiseless case. In the presence of noise, both measurements and computational complexity for exact signal recovery are O
(
k
lo
g
1.3
⁡
(
n
)
). These frameworks also have been used in spectrum sensing in [24]; Hassanieh et al. in [24] presented a prime sampling technology that can capture GHz of spectrum in real-time with low speed analog-to-digital converters (ADCs); this prime sampling technology is essentially identical to the framework of [19–22, 25]. These frameworks of [19–22] also have been used in compressed sensing phase retrieval [26].In this study, we are interested in the sparse LDPC-DFT measurement matrices associated with SWIFT recovery algorithm [19–22], which can reduce both the measurement cost and computational complexity simultaneously. The authors in [19] analyzed the successful recovery probability of SWIFT algorithm via exploiting the connection between CS system and packet-communication system. Furthermore, in [22] the authors investigated the generalized family of LDPC-DFT measurement matrices in terms of the measurement cost, computational complexity, and recovery performance via a rough density evolution, where a local neighborhood of every edge in the graph should be cycle-free (tree-like). However, they only focused on reducing the number of measurements m required for successful recovery, for given k and n.In this paper, we investigate the performance measures of SWIFT recovery algorithm in the asymptotic case(
n
→
∞
) in order to give an estimate of the performance for given sparse measurement matrix and k in the finite n case, where our proposed approach gives accurate evolution of performance with different parameters of measurement matrices and is easy to implement. The analysis shows that there exists a threshold on the density factor α
=
k
/
n; if under this threshold, the recovery algorithm is successful; otherwise it will fail. It is shown that the threshold is dependent on the parameter of LDPC matrix, which provides a basis for us to design the sparse measurement matrices.


## 2. A Class of Hybrid LDPC-DFT Measurement Matrix and Their Fast Recovery Algorithm

In this section, we consider a special class of hybrid mix of the parity-check matrix of binary LDPC codes and DFT matrix (referred to as “LDPC-DFT measurement matrix”) and their fast recovery algorithm. We firstly introduce the sparse parity-check matrix of LDPC codes (referred to as “LDPC-based measurement matrix”) and its bipartite graph.


### 2.1. LDPC-Based Measurement Matrix and Measurement Graph

In channel coding, it is well known that the LDPC codes can be defined by the null space of its sparse parity-check matrix; the codes are classified as binary codes and nonbinary codes. In this paper, we only consider the case of binary codes. A sparse parity-check matrix can be represented by a bipartite graph. In a bipartite graph, two sets of nodes are defined as the code symbols and parity-check equations; they are labeled as “variable nodes” and “check nodes,” respectively. There is an edge between the variable nodev and check node c if and only if v appears in parity-check equation c.In CS, when the measurement matrix is sparse parity-check matrix, the measurement also has its own bipartite graph (referred to as “measurement graph”). We denote this measurement graph asG
=
(
V
∪
C
,
∂
), where the set of variable nodes V represents the original signal and the check nodes C represent measurement observations and ∂ is set of edges. The number of edges associated with every node (V or C) is called node degree. In this paper, we consider the case in which every variable node (check node) has same nodes degree d
v (d
c), which is also referred to as regular degree (
d
v
,
d
c
). Additionally, we denote the check nodes set M
(
v
) as all the check nodes incident to variable node v by edges. Similarly, the set of variable nodes N
(
c
) is denoted as all the variable nodes incident to check node c. In particular, due to the mathematical connection between channel coding and CS, we can analyze the fast recovery algorithm over the measurement graph. Hereinafter, we refer to the recovery process as decoding.


### 2.2. Decoding Algorithm Based on Sparse Measurement Graph

We firstly introduce the principle of the decoding algorithm based on sparse measurement graph through an example. Consider an example consisting of a sparse signalx of length n
=
15 with k
=
4 nonzero elements. Let the 4 nonzero elements of signal be as follows: x
[
1
]
=
2, x
[
4
]
=
1, x
[
8
]
=
4, and x
[
13
]
=
7; let the number of measurements be m
=
9. According to the definition of measurement graph, we have sparse measurement graph, shown in Figure 1.Figure 1
Sparse measurement bipartite graph.In Figure1, it is shown that the check nodes can be classified into three observation nodes.Zero-Ton. A check node does not contain any nonzero elements of signal, for example, nodes 1, 3, 4, and 9 in the right side of Figure 1.Single-Ton. A check node only contains one nonzero element of signal, for example, nodes 5, 6, and 7 in the right side of Figure 1.Multiton. A check node contains more than one nonzero element of signal, for example, nodes 2 and 8 in the right side of Figure 1.Assuming that there exists an “oracle” can decide exactly which check nodes are zero-ton, single-ton, and multiton, and the “oracle” can further decode the corresponding value and index of variable nodes incident to the single-ton. In the above example, the “oracle” can decide that the nodes 5, 6, and 7 are single-ton and decode the value and index of variable nodes 1, 13, and 8, respectively. Then, the “oracle” could subtract variable nodes contributions from other check nodes and form new single-tons; for example, in Figure1 check node 8 subtracts the contribution of the variable node x
[
13
]; then check node 8 becomes a new single-ton.Therefore, with the information of single-ton, the “oracle” repeats the following steps:(1)
Selecting all the edges in sparse measurement graph with single-ton check nodes.
(2)
Removing these edges and the corresponding variable and check nodes connected to these edges.
(3)
Removing the other edges adjacent variable nodes that have been removed in step (2).
(4)
Subtracting the value of variable nodes that have been removed in step (3) from the corresponding check nodes.When all the edges have been removed, the decoding is successful. The decoding algorithm is called “peeling decoding” in traditional erasure channel [23, 27].Luby et al. in [23, 27] analyzed the performance of peeling decoding algorithm; it has been shown that the peeling decoding algorithm terminates successfully with probability of at least 1
-
O
(
k
-
3
/
4
) with good variable degree distribution. However, in the decoding algorithm, the “oracle” can (1) decide the type of check nodes and (2) exactly estimate the value and index of single-ton incident to variable node. In order to get rid of the oracle, Pawar and Ramchandran introduced the DFT matrix to decode the single-ton in [19]; they also proved that the corresponding SWIFT algorithm with m
=
2
k
(
1
+
ε
) measurements could exactly recover the original signal with probability of at least 1
-
O
(
k
-
3
/
4
) in the noiseless setting, where ε
>
0, arbitrarily close to 0.


### 2.3. Measurement Matrix Based on LDPC-DFT

DenoteF
∈
C
2
×
n as the first two rows of n
×
n DFT matrix; that is, (1)
F
=
1
1
1
⋯
1
1
e
-
j
2
π
/
n
e
-
j
4
π
/
n
⋯
e
-
j
2
n
-
1
π
/
n
.Since the matrix F can decide the type of check nodes and decode the value as well as index of corresponding variable nodes, the matrix F is also referred to as “detection matrix.” We design the required measurement matrix via the following definition.Definition 1.
Letm
=
2
R for some positive integers R. Given R
×
n sparse parity-check matrix P of LDPC, denoting p
j
T as jth row of P (1
≤
j
≤
R), and given a detection matrix F
∈
C
2
×
n, then the m
×
n measurement matrix H is designed by(2)
H
=
P
⊙
F
=
p
1
T
⊗
F
⋮
p
R
T
⊗
F
,where ⊙ is row-tensor product and ⊗ is standard Kronecker product.From the definition of Kronecker product, it is shown that the value of every check node (observation) is a 2-length vector, for example, the following check nodesi, also shown in Figure 2:(3)
y
i
=
x
4
1
e
-
j
8
π
/
n
+
x
7
1
e
-
j
14
π
/
n
+
x
15
1
e
-
j
30
π
/
n
.Figure 2
Multiton check node and its observation vectory
i.We use the following criterions to decide the type of check nodes and estimate the value and index of corresponding variable nodes.Zero-Ton. ith check node is a zero-ton if y
i
=
0.Single-Ton. ith check node is a single-ton if y
i
[
1
]
=
y
i
[
2
] and ∠
(
y
i
[
1
]
y
i
[
2
]
†
)
=
2
π
p
/
n, 0
≤
p
≤
n
-
1; its neighbor indexed by (
n
/
2
π
)
∠
(
y
i
[
1
]
y
i
[
2
]
†
) is nonzero with value given by y
i
[
1
].Multiton. ith check node is a multiton if y
i
[
1
]
≠
y
i
[
2
] or ∠
(
y
i
[
1
]
y
i
[
2
]
†
)
≠
2
π
p
/
n.The VB algorithm with decoding successfully claims that the nonzero elements of signal must satisfy continuous distribution [10, 11]. However, the above criterions are identified with probability of one whether nonzero elements of signal obey continuous distribution or not. Hence, the measurement matrix based on LDPC-DFT could be more applicable for various signal types.Theorem 2.
Whether the nonzero elements of original signal obey a continuous distributionf or take values from the finite discrete set, the above criterions of zero-ton, single-ton, and multiton are identified with probability of one.Proof.
Firstly, we prove the case of nonzero elements obeying the continuous distributionf. Here, we only prove the type of zero-ton, which is valid for the other types with no major changes. If the nonzero elements of original signal obey the continuous distribution, for arbitrary a
≠
b, we have Pr
⁡
(
x
[
a
]
=
-
x
[
b
]
)
=
0. For the sparse measurement graph, y
i
=
∑
j
∈
N
(
i
)
x
[
j
], when y
i
=
0; that is, ∑
j
∈
N
(
i
)
x
[
j
]
=
0; by Pr
⁡
(
x
[
a
]
=
-
x
[
b
]
)
=
0, we have Pr
⁡
(
x
[
j
]
=
0
)
=
1, where j
∈
N
(
i
); the decoder can decide the type of check node as zero-ton via the definition of zero-ton.
Then, we consider the case of the nonzero elements of original signal taking values from the finite discrete set. Similarly, we only prove the type of zero-ton. Considering the worst case, fora
≠
b, Pr
⁡
(
x
[
a
]
=
-
x
[
b
]
)
→
1. However the y
i
=
∑
j
∈
N
(
i
)
x
[
j
] is 2-length complex vector; that is, when y
i
=
0, it claims not only y
i
[
1
]
=
0, but also y
i
[
2
]
=
0. Due to the sparse measurement matrix, y
i
=
0 holds, if and only if x
[
j
]
=
0, j
∈
N
(
i
). Hence, the decoder can decide the type of check node as zero-ton via the definition of zero-ton.In the context of analysis of framework and simulation, we adopt the following way to generate the original signal. LetT be the set of nonzero elements of original signal and let α be the density factor, that is, the probability that a signal element belongs to T. For a given α, every element of original signal takes value as follows: every element takes 0 with probability of 1
-
α or the value from the continuous distribution f (discrete sets) with probability of α. In this sense, the sparsity k and density ratio γ
=
k
/
n are random variables. Furthermore, E
[
k
]
=
α
n and E
[
γ
]
=
α, where E
[
·
] is referred to as expected value.


### 2.4. Decoding Algorithm

In the above subsections, we describe an iterative decoding algorithm to decode the sparse signal with the help of “oracle” that is implemented via LDPC-DFT measurement matrix and single-ton criterions. In this subsection, the iterative decoding algorithm is showed by using the step described in Section2.2 (also see pseudocode in Algorithms 1 and 2).Algorithm 1:Short-and-Wide Iterative Fast Transform, SWIFT, algorithm.
(1)
Input: observation vectors y, length of original signal n, measurement matrix H.
(2)
Output: estimation of original signal x
^.
(3)
Initialization: x
^
=
0.
(4)
for each iteration do
(5) for  i
=
1
:
R  do
(6)  denote y
i for observation vector of ith check node
(7)  if  y
i
2
=
=
0  then
(8)   i is zero-ton.
(9)  else
(10)   [flag value location] = SingletonEstimator(y
i)
(11)   if flag then
(12)
y
=
y
-
v
a
l
u
e
⋅
H(:, location), x
^(location) = value
(13)    end if
(14) end if
(15)
end for
(16) end forAlgorithm 2:Single-ton estimator algorithm.
(
1) Input: observation vector y
i.
(2) Output: a boolean flag“single-ton”, estimation of signal: valueand location;
(3) Initialization: flag = “false”.
(4) if  (
n
/
2
π
)
∠
(
y
i
[
1
]
y
i
[
2
]
†
)
∈
0,1
,
…
,
(
n
-
1
)  then
(5)  flag = “true”
(6)  value = y
i
[
1
]
(7)  location = (
n
/
2
π
)
∠
(
y
i
[
1
]
y
i
[
2
]
†
)
(8) end ifFollowing the discussions in [19], it has been proven that the SWIFT decoding algorithm satisfies the criterions with probability of at least 1
-
O
(
k
-
3
/
4
) via the corresponding Theorem  2 in [27]. In this paper, we propose a general framework for the asymptotic analysis of SWIFT algorithm. Using the asymptotic analysis, we can track the evolution of density factor α and the corresponding threshold can be determined for different (
d
v
,
d
c
).


## 2.1. LDPC-Based Measurement Matrix and Measurement Graph

In channel coding, it is well known that the LDPC codes can be defined by the null space of its sparse parity-check matrix; the codes are classified as binary codes and nonbinary codes. In this paper, we only consider the case of binary codes. A sparse parity-check matrix can be represented by a bipartite graph. In a bipartite graph, two sets of nodes are defined as the code symbols and parity-check equations; they are labeled as “variable nodes” and “check nodes,” respectively. There is an edge between the variable nodev and check node c if and only if v appears in parity-check equation c.In CS, when the measurement matrix is sparse parity-check matrix, the measurement also has its own bipartite graph (referred to as “measurement graph”). We denote this measurement graph asG
=
(
V
∪
C
,
∂
), where the set of variable nodes V represents the original signal and the check nodes C represent measurement observations and ∂ is set of edges. The number of edges associated with every node (V or C) is called node degree. In this paper, we consider the case in which every variable node (check node) has same nodes degree d
v (d
c), which is also referred to as regular degree (
d
v
,
d
c
). Additionally, we denote the check nodes set M
(
v
) as all the check nodes incident to variable node v by edges. Similarly, the set of variable nodes N
(
c
) is denoted as all the variable nodes incident to check node c. In particular, due to the mathematical connection between channel coding and CS, we can analyze the fast recovery algorithm over the measurement graph. Hereinafter, we refer to the recovery process as decoding.


## 2.2. Decoding Algorithm Based on Sparse Measurement Graph

We firstly introduce the principle of the decoding algorithm based on sparse measurement graph through an example. Consider an example consisting of a sparse signalx of length n
=
15 with k
=
4 nonzero elements. Let the 4 nonzero elements of signal be as follows: x
[
1
]
=
2, x
[
4
]
=
1, x
[
8
]
=
4, and x
[
13
]
=
7; let the number of measurements be m
=
9. According to the definition of measurement graph, we have sparse measurement graph, shown in Figure 1.Figure 1
Sparse measurement bipartite graph.In Figure1, it is shown that the check nodes can be classified into three observation nodes.Zero-Ton. A check node does not contain any nonzero elements of signal, for example, nodes 1, 3, 4, and 9 in the right side of Figure 1.Single-Ton. A check node only contains one nonzero element of signal, for example, nodes 5, 6, and 7 in the right side of Figure 1.Multiton. A check node contains more than one nonzero element of signal, for example, nodes 2 and 8 in the right side of Figure 1.Assuming that there exists an “oracle” can decide exactly which check nodes are zero-ton, single-ton, and multiton, and the “oracle” can further decode the corresponding value and index of variable nodes incident to the single-ton. In the above example, the “oracle” can decide that the nodes 5, 6, and 7 are single-ton and decode the value and index of variable nodes 1, 13, and 8, respectively. Then, the “oracle” could subtract variable nodes contributions from other check nodes and form new single-tons; for example, in Figure1 check node 8 subtracts the contribution of the variable node x
[
13
]; then check node 8 becomes a new single-ton.Therefore, with the information of single-ton, the “oracle” repeats the following steps:(1)
Selecting all the edges in sparse measurement graph with single-ton check nodes.
(2)
Removing these edges and the corresponding variable and check nodes connected to these edges.
(3)
Removing the other edges adjacent variable nodes that have been removed in step (2).
(4)
Subtracting the value of variable nodes that have been removed in step (3) from the corresponding check nodes.When all the edges have been removed, the decoding is successful. The decoding algorithm is called “peeling decoding” in traditional erasure channel [23, 27].Luby et al. in [23, 27] analyzed the performance of peeling decoding algorithm; it has been shown that the peeling decoding algorithm terminates successfully with probability of at least 1
-
O
(
k
-
3
/
4
) with good variable degree distribution. However, in the decoding algorithm, the “oracle” can (1) decide the type of check nodes and (2) exactly estimate the value and index of single-ton incident to variable node. In order to get rid of the oracle, Pawar and Ramchandran introduced the DFT matrix to decode the single-ton in [19]; they also proved that the corresponding SWIFT algorithm with m
=
2
k
(
1
+
ε
) measurements could exactly recover the original signal with probability of at least 1
-
O
(
k
-
3
/
4
) in the noiseless setting, where ε
>
0, arbitrarily close to 0.


## 2.3. Measurement Matrix Based on LDPC-DFT

DenoteF
∈
C
2
×
n as the first two rows of n
×
n DFT matrix; that is, (1)
F
=
1
1
1
⋯
1
1
e
-
j
2
π
/
n
e
-
j
4
π
/
n
⋯
e
-
j
2
n
-
1
π
/
n
.Since the matrix F can decide the type of check nodes and decode the value as well as index of corresponding variable nodes, the matrix F is also referred to as “detection matrix.” We design the required measurement matrix via the following definition.Definition 1.
Letm
=
2
R for some positive integers R. Given R
×
n sparse parity-check matrix P of LDPC, denoting p
j
T as jth row of P (1
≤
j
≤
R), and given a detection matrix F
∈
C
2
×
n, then the m
×
n measurement matrix H is designed by(2)
H
=
P
⊙
F
=
p
1
T
⊗
F
⋮
p
R
T
⊗
F
,where ⊙ is row-tensor product and ⊗ is standard Kronecker product.From the definition of Kronecker product, it is shown that the value of every check node (observation) is a 2-length vector, for example, the following check nodesi, also shown in Figure 2:(3)
y
i
=
x
4
1
e
-
j
8
π
/
n
+
x
7
1
e
-
j
14
π
/
n
+
x
15
1
e
-
j
30
π
/
n
.Figure 2
Multiton check node and its observation vectory
i.We use the following criterions to decide the type of check nodes and estimate the value and index of corresponding variable nodes.Zero-Ton. ith check node is a zero-ton if y
i
=
0.Single-Ton. ith check node is a single-ton if y
i
[
1
]
=
y
i
[
2
] and ∠
(
y
i
[
1
]
y
i
[
2
]
†
)
=
2
π
p
/
n, 0
≤
p
≤
n
-
1; its neighbor indexed by (
n
/
2
π
)
∠
(
y
i
[
1
]
y
i
[
2
]
†
) is nonzero with value given by y
i
[
1
].Multiton. ith check node is a multiton if y
i
[
1
]
≠
y
i
[
2
] or ∠
(
y
i
[
1
]
y
i
[
2
]
†
)
≠
2
π
p
/
n.The VB algorithm with decoding successfully claims that the nonzero elements of signal must satisfy continuous distribution [10, 11]. However, the above criterions are identified with probability of one whether nonzero elements of signal obey continuous distribution or not. Hence, the measurement matrix based on LDPC-DFT could be more applicable for various signal types.Theorem 2.
Whether the nonzero elements of original signal obey a continuous distributionf or take values from the finite discrete set, the above criterions of zero-ton, single-ton, and multiton are identified with probability of one.Proof.
Firstly, we prove the case of nonzero elements obeying the continuous distributionf. Here, we only prove the type of zero-ton, which is valid for the other types with no major changes. If the nonzero elements of original signal obey the continuous distribution, for arbitrary a
≠
b, we have Pr
⁡
(
x
[
a
]
=
-
x
[
b
]
)
=
0. For the sparse measurement graph, y
i
=
∑
j
∈
N
(
i
)
x
[
j
], when y
i
=
0; that is, ∑
j
∈
N
(
i
)
x
[
j
]
=
0; by Pr
⁡
(
x
[
a
]
=
-
x
[
b
]
)
=
0, we have Pr
⁡
(
x
[
j
]
=
0
)
=
1, where j
∈
N
(
i
); the decoder can decide the type of check node as zero-ton via the definition of zero-ton.
Then, we consider the case of the nonzero elements of original signal taking values from the finite discrete set. Similarly, we only prove the type of zero-ton. Considering the worst case, fora
≠
b, Pr
⁡
(
x
[
a
]
=
-
x
[
b
]
)
→
1. However the y
i
=
∑
j
∈
N
(
i
)
x
[
j
] is 2-length complex vector; that is, when y
i
=
0, it claims not only y
i
[
1
]
=
0, but also y
i
[
2
]
=
0. Due to the sparse measurement matrix, y
i
=
0 holds, if and only if x
[
j
]
=
0, j
∈
N
(
i
). Hence, the decoder can decide the type of check node as zero-ton via the definition of zero-ton.In the context of analysis of framework and simulation, we adopt the following way to generate the original signal. LetT be the set of nonzero elements of original signal and let α be the density factor, that is, the probability that a signal element belongs to T. For a given α, every element of original signal takes value as follows: every element takes 0 with probability of 1
-
α or the value from the continuous distribution f (discrete sets) with probability of α. In this sense, the sparsity k and density ratio γ
=
k
/
n are random variables. Furthermore, E
[
k
]
=
α
n and E
[
γ
]
=
α, where E
[
·
] is referred to as expected value.


## 2.4. Decoding Algorithm

In the above subsections, we describe an iterative decoding algorithm to decode the sparse signal with the help of “oracle” that is implemented via LDPC-DFT measurement matrix and single-ton criterions. In this subsection, the iterative decoding algorithm is showed by using the step described in Section2.2 (also see pseudocode in Algorithms 1 and 2).Algorithm 1:Short-and-Wide Iterative Fast Transform, SWIFT, algorithm.
(1)
Input: observation vectors y, length of original signal n, measurement matrix H.
(2)
Output: estimation of original signal x
^.
(3)
Initialization: x
^
=
0.
(4)
for each iteration do
(5) for  i
=
1
:
R  do
(6)  denote y
i for observation vector of ith check node
(7)  if  y
i
2
=
=
0  then
(8)   i is zero-ton.
(9)  else
(10)   [flag value location] = SingletonEstimator(y
i)
(11)   if flag then
(12)
y
=
y
-
v
a
l
u
e
⋅
H(:, location), x
^(location) = value
(13)    end if
(14) end if
(15)
end for
(16) end forAlgorithm 2:Single-ton estimator algorithm.
(
1) Input: observation vector y
i.
(2) Output: a boolean flag“single-ton”, estimation of signal: valueand location;
(3) Initialization: flag = “false”.
(4) if  (
n
/
2
π
)
∠
(
y
i
[
1
]
y
i
[
2
]
†
)
∈
0,1
,
…
,
(
n
-
1
)  then
(5)  flag = “true”
(6)  value = y
i
[
1
]
(7)  location = (
n
/
2
π
)
∠
(
y
i
[
1
]
y
i
[
2
]
†
)
(8) end ifFollowing the discussions in [19], it has been proven that the SWIFT decoding algorithm satisfies the criterions with probability of at least 1
-
O
(
k
-
3
/
4
) via the corresponding Theorem  2 in [27]. In this paper, we propose a general framework for the asymptotic analysis of SWIFT algorithm. Using the asymptotic analysis, we can track the evolution of density factor α and the corresponding threshold can be determined for different (
d
v
,
d
c
).


## 3. Asymptotic Analysis of Decoding Algorithm

### 3.1. Analysis Model

In this paper, we only consider the regular(
d
v
,
d
c
) measurement bipartite graph. However, the results can be generalized to irregular case.Consider a sparse bipartite graphG
k
m
=
(
V
∗
∪
C
,
∂
∗
), where V
∗
⊂
V is the subset of variable nodes, C is the set of m check nodes, and ∂
∗ is the set of corresponding edges. Since the locations of nonzero elements in signal are random, the graph G
k
m is left-regular, as shown in Figure 1. In the SWIFT decoding algorithm, the criterions employed by the peeling decode algorithm depend on the degree of check nodes. To describe the asymptotic analysis, we classify the set of check nodes C as C
i being the set of check nodes having degree i, 1
≤
i
≤
d
c. Furthermore, the set T of nonzero elements of signal x is classified as T
i being the set variable nodes having i edges connected to the set C
1, 0
≤
i
≤
d
v.Based on the above classification and criterions employed in Section2, in each iteration of SWIFT algorithm, a variable node can be decoded successfully if the following condition holds.Theorem 3.
In each iteration, a variable nodev can be decoded successfully with probability of almost 1 if and only if v
∈
⋃
i
=
1
d
v
T
i.Proof.
Sufficiency. When v
∈
T
1, from the definition of single-ton, it is trivial that the variable node v can be decoded successfully with probability of almost 1. When v
∈
⋃
i
=
2
d
v
T
i, that is, the variable node v being connected to more than one single-ton, since the decoder can decode successfully, with probability of almost 1, the corresponding variable nodes from the single-ton, we can conclude that value of these single-tons must be identical. Hence, this case is identical to the case v
∈
T
1.
Necessity. For the SWIFT algorithm, when a variable node v is decoded successfully, there must at least exist a single-ton check node that connected to the variable node v; that is, v
∈
⋃
i
=
1
d
v
T
i.We remodel the sparse measurement graph via the definition ofC
i as well as T
i and Theorem 3, which allows us to analyze the evolution of C
i and T
i. Let p
C
i
(
l
) denote the set of probability that a check node belongs to C
i and let p
T
i
(
l
)denote the set of probability that a variable node belongs to T
i, where l is the iteration number. Furthermore, we denote α
(
l
) by the probability that a variable node belongs to T
(
l
). Given p
C
i
(
l
), p
T
i
(
l
), and α
(
l
) at iteration l
≥
1, our asymptotic analysis can calculate p
C
i
(
l
+
1
), p
T
i
(
l
+
1
), and α
(
l
+
1
) at next iteration l
+
1. For given initial density factor α, we can track the evolution of α
(
l
) via the analysis approach. Once the probability α
(
l
) decreases monotonically to zero with the iteration number increase, we refer to this case as the decoding algorithm recovering the original signal successfully; while the probability α
(
l
) is bounded away from 0 with any iteration number, we call this case decoding algorithm failure. In what follows, we provide a rigorous calculation of the above sets of probability via combinatorial and probabilistic arguments.


### 3.2. Details of Asymptotic Analysis

DefineS
T
=
⋃
i
=
1
d
v
T
i, S
T
c
=
T
0. From Theorem 3, it is known that a variable node that belongs to S
T can be decoded successfully and a variable node that belongs to S
T
c is left intact. Thus, the probability p
v
(
l
) that a variable node in T
(
l
) is being decoded successfully is(4)
p
v
l
=
∑
T
i
∈
S
T
p
T
i
l
+
1
.Hence, after lth iteration, the probability of variable node v remaining undecoded is(5)
α
l
+
1
=
α
l
1
-
p
v
l
.Once the variable node is decoded successfully, as discussed in SWIFT algorithm, thed
v edges along with the variable node will be removed, which also results in the degree of check nodes being incident to these removed edges. Let p
C
i
j
(
l
) denote the probability that the degree number i of a check node c reduces to number j, where j
≤
i. Based on Theorem 3, when a variable node v
∈
T
i is decoded successfully, i edges along with the set C
1 as well as d
v
-
i edges along with the set C
1
c
=
{
C
2
∪
C
3
∪
⋯
∪
C
d
c
} are removed. To calculate the probability p
C
i
j
(
l
) conveniently, we use the total probability law:(6)
p
C
j
l
+
1
=
∑
i
=
j
d
c
p
C
i
l
p
C
i
j
l
,
j
=
0
,
…
,
d
c
.For the asymptotic analysis, we assume the length of signaln
→
∞ and the designed sparse matrix is random. Hence, both the distribution of i edges between variable node v and the set C
1 and the d
v
-
i edges between variable node v and the set C
1
c can be regarded as uniform distributions. Let p
C
1 and p
C
1
c be the probabilities that an edge is removed given that the edge is incident to a check node in the sets C
1 and C
1
c, respectively. We have(7)
p
C
10
l
=
C
1
1
p
C
1
1
1
-
p
C
1
0
=
p
C
1
,
p
C
11
l
=
1
-
p
C
10
l
,
(8)
p
C
i
j
l
=
C
i
i
-
j
p
C
1
c
i
-
j
1
-
p
C
1
c
j
,
i
=
2
,
…
,
d
c
,
j
=
0
,
…
,
i
.Before calculatingp
C
1 and p
C
1
c, we should introduce a significant conditional probability. Let p
(
l
) denote the probability that a check node incident to an edge e belongs to C
1 given a variable node incident to the edge in T
l; its diagram is shown in Figure 3. Then, the p
(
l
) can be calculated by(9)
p
l
=
Pr
⁡
c
∈
C
1
l
∣
v
∈
T
l
=
Pr
⁡
v
∈
T
l
,
c
∈
C
1
l
Pr
⁡
v
∈
T
l
=
p
C
1
l
d
c
α
l
.Figure 3
Diagram of calculation of conditional probabilityp
(
l
).From the definition ofp
C
1, we have(10)
p
C
1
=
Pr
⁡
v
∈
S
T
l
∣
c
∈
C
1
l
,
v
∈
T
l
=
∑
T
i
l
∈
S
T
l
P
r
v
∈
T
i
l
∣
c
∈
C
1
l
,
v
∈
T
l
=
∑
T
i
l
∈
S
T
l
Pr
⁡
c
∈
C
1
l
∣
v
∈
T
i
l
,
v
∈
T
l
Pr
⁡
v
∈
T
i
l
∣
v
∈
T
l
Pr
⁡
c
∈
C
1
l
∣
v
∈
T
l
=
∑
T
i
l
∈
S
T
l
i
/
d
v
p
T
i
l
p
l
=
d
c
α
l
∑
T
i
l
∈
S
T
l
i
p
T
i
l
d
v
p
C
1
l
.Similarly, the calculation of p
C
1
c can be obtained by (11)
p
C
1
c
=
Pr
⁡
v
∈
S
T
l
∣
c
∈
C
1
c
l
,
v
∈
T
l
=
∑
T
i
l
∈
S
T
l
P
r
v
∈
T
i
l
∣
c
∈
C
1
c
l
,
v
∈
T
l
=
∑
T
i
l
∈
S
T
l
Pr
⁡
c
∈
C
1
c
l
∣
v
∈
T
i
l
,
v
∈
T
l
P
r
v
∈
T
i
l
∣
v
∈
T
l
Pr
⁡
c
∈
C
1
c
l
∣
v
∈
T
l
=
∑
T
i
l
∈
S
T
l
1
-
i
/
d
v
p
T
i
l
1
-
p
l
=
d
v
p
v
l
-
∑
T
i
l
∈
S
T
l
i
p
T
i
l
d
v
1
-
p
C
1
l
/
d
c
α
l
.To sum up, we can calculate the set of probability p
C
i
(
l
+
1
) of a check node in C
i via (6)–(11).Next, thep
T
i
(
l
+
1
) is discussed. When a variable node is decoded successfully, with the corresponding edges removal, it is also shown that these undecoded sets T
(
l
+
1
) should be reclassified into the set T
i
l
+
1. Let p
T
i
j
(
l
) denote the probability that a variable node v
∈
T
i
l changes into v
∈
T
j
(
l
+
1
); from Theorem 3, we have i
=
0. On the other hand, check nodes in the set C
1
c also should be reclassified into the set C
1. Let the set C
1
Δ denote the check nodes that reclassified C
1
c to C
1. Similarly, we assume the length of signal n
→
∞ and the designed sparse matrix is random. We can exploit the following: the distribution of edges incident to the set of check nodes C
1
c and C
1
Δ is uniform. It can be seen that the probability p
T
0
j
(
l
) is (12)
p
T
0
j
l
=
Pr
⁡
v
∈
T
j
l
+
1
∣
v
∈
T
0
l
,
v
∈
T
l
=
C
d
v
j
p
Δ
l
j
1
-
p
Δ
l
d
v
-
j
,
j
=
0
,
…
,
d
v
,where p
Δ
(
l
) is the probability of an edge incident to the set C
1
c moving to the set C
1
Δ; that is, (13)
p
Δ
l
=
P
r
c
∈
C
1
l
∣
v
∈
T
l
,
c
∉
C
11
l
=
1
·
∑
j
=
2
d
c
p
C
j
l
p
C
j
1
l
1
·
∑
j
=
2
d
c
p
C
j
l
p
C
j
1
l
+
∑
i
=
2
d
c
i
p
C
i
l
+
1
.Based on the total probability law,p
T
i
(
l
+
1
) can be expressed as(14)
p
T
i
l
+
1
=
p
T
0
l
p
T
0
i
l
1
-
p
v
l
,
i
=
0
,
…
,
d
v
,where 1
-
p
v
(
l
) is a normalization factor, which makes the probability p
T
i
(
l
+
1
) satisfying standardization of probability; that is, (15)
∑
i
=
0
d
v
p
T
i
l
+
1
=
∑
T
i
∈
S
T
c
∑
j
=
i
d
v
p
T
i
l
p
T
i
j
l
=
∑
T
i
∈
S
T
c
p
T
i
l
=
1
-
p
v
l
.Thus, according to the calculation of (12)–(15), the probability p
T
i
(
l
+
1
) can be obtained.In what follows, we provide a precise summary of the above updated rules.(1) Initialization. Setting the initial value α to α
(
0
), in the random sparse bipartite graph, it can be seen that the probability of a check node that belongs to the set T
i can be given by the following binomial distribution:(16)
p
C
i
0
=
C
d
c
i
α
0
i
1
-
α
0
d
c
-
i
.From Figure 3 and the probability p
(
l
) in (9), the probability p
T
i
(
0
) is given by the following binomial distribution: (17)
p
T
i
0
=
C
d
v
i
p
0
i
1
-
p
0
d
v
-
i
.(2) Calculating
p
C
j
(
l
+
1
). Substituting (7)–(11) into (6), then p
C
j
(
l
+
1
) is calculated.(3) Calculating
p
T
i
(
l
+
1
). Substituting (13)–(15) into (12), then p
T
i
(
l
+
1
) is calculated.(4) Calculating
α
(
l
+
1
). Substituting (4) and the probability p
T
i
(
l
+
1
) in step (3) into (5), α
(
l
+
1
) is calculated.


### 3.3. Comparison of VB Algorithm in the Asymptotic Regime

In this subsection, we compare the above analytical success thresholds of SWIFT algorithm with VB algorithm in the asymptotic regime. In Table1, we have listed the analytical success thresholds of the SWIFT and VB algorithms for different graphs.Table 1
Threshold for different (d
v, d
c) with SWIFT and VB algorithms.
(d
v, d
c)
(3, 6)
(4, 8)
(5, 10)
(6, 12)
(3, 4)
(5, 6)
(5, 7)
(7, 8)
SWIFTα
(
0
)
0.4294
0.3829
0.3411
0.3074
0.6476
0.5504
0.4782
0.4711
VBα
(
0
)
0.2574
0.2394
0.2179
0.1992
0.4488
0.3892
0.3266
0.3335As seen in Table1, for every graph, the SWIFT algorithm has a better performance than the VB algorithm. Overall, it is shown that the oversampling ratio γ
=
k
/
m
=
d
v
/
(
α
(
0
)
d
c
) improves when decreasing both d
v and d
c. Furthermore, when we keep compression ratio constant—that is, d
v
/
d
c is a constant—such as (3, 6), (4, 8), and (5, 10), as shown in Table 1, in general, when decreasing d
v, SWIFT and VB algorithms perform better. Based on the relationship between the threshold and (
d
v
,
d
c
), the sparse measurement matrix with superior performance can be designed.


## 3.1. Analysis Model

In this paper, we only consider the regular(
d
v
,
d
c
) measurement bipartite graph. However, the results can be generalized to irregular case.Consider a sparse bipartite graphG
k
m
=
(
V
∗
∪
C
,
∂
∗
), where V
∗
⊂
V is the subset of variable nodes, C is the set of m check nodes, and ∂
∗ is the set of corresponding edges. Since the locations of nonzero elements in signal are random, the graph G
k
m is left-regular, as shown in Figure 1. In the SWIFT decoding algorithm, the criterions employed by the peeling decode algorithm depend on the degree of check nodes. To describe the asymptotic analysis, we classify the set of check nodes C as C
i being the set of check nodes having degree i, 1
≤
i
≤
d
c. Furthermore, the set T of nonzero elements of signal x is classified as T
i being the set variable nodes having i edges connected to the set C
1, 0
≤
i
≤
d
v.Based on the above classification and criterions employed in Section2, in each iteration of SWIFT algorithm, a variable node can be decoded successfully if the following condition holds.Theorem 3.
In each iteration, a variable nodev can be decoded successfully with probability of almost 1 if and only if v
∈
⋃
i
=
1
d
v
T
i.Proof.
Sufficiency. When v
∈
T
1, from the definition of single-ton, it is trivial that the variable node v can be decoded successfully with probability of almost 1. When v
∈
⋃
i
=
2
d
v
T
i, that is, the variable node v being connected to more than one single-ton, since the decoder can decode successfully, with probability of almost 1, the corresponding variable nodes from the single-ton, we can conclude that value of these single-tons must be identical. Hence, this case is identical to the case v
∈
T
1.
Necessity. For the SWIFT algorithm, when a variable node v is decoded successfully, there must at least exist a single-ton check node that connected to the variable node v; that is, v
∈
⋃
i
=
1
d
v
T
i.We remodel the sparse measurement graph via the definition ofC
i as well as T
i and Theorem 3, which allows us to analyze the evolution of C
i and T
i. Let p
C
i
(
l
) denote the set of probability that a check node belongs to C
i and let p
T
i
(
l
)denote the set of probability that a variable node belongs to T
i, where l is the iteration number. Furthermore, we denote α
(
l
) by the probability that a variable node belongs to T
(
l
). Given p
C
i
(
l
), p
T
i
(
l
), and α
(
l
) at iteration l
≥
1, our asymptotic analysis can calculate p
C
i
(
l
+
1
), p
T
i
(
l
+
1
), and α
(
l
+
1
) at next iteration l
+
1. For given initial density factor α, we can track the evolution of α
(
l
) via the analysis approach. Once the probability α
(
l
) decreases monotonically to zero with the iteration number increase, we refer to this case as the decoding algorithm recovering the original signal successfully; while the probability α
(
l
) is bounded away from 0 with any iteration number, we call this case decoding algorithm failure. In what follows, we provide a rigorous calculation of the above sets of probability via combinatorial and probabilistic arguments.


## 3.2. Details of Asymptotic Analysis

DefineS
T
=
⋃
i
=
1
d
v
T
i, S
T
c
=
T
0. From Theorem 3, it is known that a variable node that belongs to S
T can be decoded successfully and a variable node that belongs to S
T
c is left intact. Thus, the probability p
v
(
l
) that a variable node in T
(
l
) is being decoded successfully is(4)
p
v
l
=
∑
T
i
∈
S
T
p
T
i
l
+
1
.Hence, after lth iteration, the probability of variable node v remaining undecoded is(5)
α
l
+
1
=
α
l
1
-
p
v
l
.Once the variable node is decoded successfully, as discussed in SWIFT algorithm, thed
v edges along with the variable node will be removed, which also results in the degree of check nodes being incident to these removed edges. Let p
C
i
j
(
l
) denote the probability that the degree number i of a check node c reduces to number j, where j
≤
i. Based on Theorem 3, when a variable node v
∈
T
i is decoded successfully, i edges along with the set C
1 as well as d
v
-
i edges along with the set C
1
c
=
{
C
2
∪
C
3
∪
⋯
∪
C
d
c
} are removed. To calculate the probability p
C
i
j
(
l
) conveniently, we use the total probability law:(6)
p
C
j
l
+
1
=
∑
i
=
j
d
c
p
C
i
l
p
C
i
j
l
,
j
=
0
,
…
,
d
c
.For the asymptotic analysis, we assume the length of signaln
→
∞ and the designed sparse matrix is random. Hence, both the distribution of i edges between variable node v and the set C
1 and the d
v
-
i edges between variable node v and the set C
1
c can be regarded as uniform distributions. Let p
C
1 and p
C
1
c be the probabilities that an edge is removed given that the edge is incident to a check node in the sets C
1 and C
1
c, respectively. We have(7)
p
C
10
l
=
C
1
1
p
C
1
1
1
-
p
C
1
0
=
p
C
1
,
p
C
11
l
=
1
-
p
C
10
l
,
(8)
p
C
i
j
l
=
C
i
i
-
j
p
C
1
c
i
-
j
1
-
p
C
1
c
j
,
i
=
2
,
…
,
d
c
,
j
=
0
,
…
,
i
.Before calculatingp
C
1 and p
C
1
c, we should introduce a significant conditional probability. Let p
(
l
) denote the probability that a check node incident to an edge e belongs to C
1 given a variable node incident to the edge in T
l; its diagram is shown in Figure 3. Then, the p
(
l
) can be calculated by(9)
p
l
=
Pr
⁡
c
∈
C
1
l
∣
v
∈
T
l
=
Pr
⁡
v
∈
T
l
,
c
∈
C
1
l
Pr
⁡
v
∈
T
l
=
p
C
1
l
d
c
α
l
.Figure 3
Diagram of calculation of conditional probabilityp
(
l
).From the definition ofp
C
1, we have(10)
p
C
1
=
Pr
⁡
v
∈
S
T
l
∣
c
∈
C
1
l
,
v
∈
T
l
=
∑
T
i
l
∈
S
T
l
P
r
v
∈
T
i
l
∣
c
∈
C
1
l
,
v
∈
T
l
=
∑
T
i
l
∈
S
T
l
Pr
⁡
c
∈
C
1
l
∣
v
∈
T
i
l
,
v
∈
T
l
Pr
⁡
v
∈
T
i
l
∣
v
∈
T
l
Pr
⁡
c
∈
C
1
l
∣
v
∈
T
l
=
∑
T
i
l
∈
S
T
l
i
/
d
v
p
T
i
l
p
l
=
d
c
α
l
∑
T
i
l
∈
S
T
l
i
p
T
i
l
d
v
p
C
1
l
.Similarly, the calculation of p
C
1
c can be obtained by (11)
p
C
1
c
=
Pr
⁡
v
∈
S
T
l
∣
c
∈
C
1
c
l
,
v
∈
T
l
=
∑
T
i
l
∈
S
T
l
P
r
v
∈
T
i
l
∣
c
∈
C
1
c
l
,
v
∈
T
l
=
∑
T
i
l
∈
S
T
l
Pr
⁡
c
∈
C
1
c
l
∣
v
∈
T
i
l
,
v
∈
T
l
P
r
v
∈
T
i
l
∣
v
∈
T
l
Pr
⁡
c
∈
C
1
c
l
∣
v
∈
T
l
=
∑
T
i
l
∈
S
T
l
1
-
i
/
d
v
p
T
i
l
1
-
p
l
=
d
v
p
v
l
-
∑
T
i
l
∈
S
T
l
i
p
T
i
l
d
v
1
-
p
C
1
l
/
d
c
α
l
.To sum up, we can calculate the set of probability p
C
i
(
l
+
1
) of a check node in C
i via (6)–(11).Next, thep
T
i
(
l
+
1
) is discussed. When a variable node is decoded successfully, with the corresponding edges removal, it is also shown that these undecoded sets T
(
l
+
1
) should be reclassified into the set T
i
l
+
1. Let p
T
i
j
(
l
) denote the probability that a variable node v
∈
T
i
l changes into v
∈
T
j
(
l
+
1
); from Theorem 3, we have i
=
0. On the other hand, check nodes in the set C
1
c also should be reclassified into the set C
1. Let the set C
1
Δ denote the check nodes that reclassified C
1
c to C
1. Similarly, we assume the length of signal n
→
∞ and the designed sparse matrix is random. We can exploit the following: the distribution of edges incident to the set of check nodes C
1
c and C
1
Δ is uniform. It can be seen that the probability p
T
0
j
(
l
) is (12)
p
T
0
j
l
=
Pr
⁡
v
∈
T
j
l
+
1
∣
v
∈
T
0
l
,
v
∈
T
l
=
C
d
v
j
p
Δ
l
j
1
-
p
Δ
l
d
v
-
j
,
j
=
0
,
…
,
d
v
,where p
Δ
(
l
) is the probability of an edge incident to the set C
1
c moving to the set C
1
Δ; that is, (13)
p
Δ
l
=
P
r
c
∈
C
1
l
∣
v
∈
T
l
,
c
∉
C
11
l
=
1
·
∑
j
=
2
d
c
p
C
j
l
p
C
j
1
l
1
·
∑
j
=
2
d
c
p
C
j
l
p
C
j
1
l
+
∑
i
=
2
d
c
i
p
C
i
l
+
1
.Based on the total probability law,p
T
i
(
l
+
1
) can be expressed as(14)
p
T
i
l
+
1
=
p
T
0
l
p
T
0
i
l
1
-
p
v
l
,
i
=
0
,
…
,
d
v
,where 1
-
p
v
(
l
) is a normalization factor, which makes the probability p
T
i
(
l
+
1
) satisfying standardization of probability; that is, (15)
∑
i
=
0
d
v
p
T
i
l
+
1
=
∑
T
i
∈
S
T
c
∑
j
=
i
d
v
p
T
i
l
p
T
i
j
l
=
∑
T
i
∈
S
T
c
p
T
i
l
=
1
-
p
v
l
.Thus, according to the calculation of (12)–(15), the probability p
T
i
(
l
+
1
) can be obtained.In what follows, we provide a precise summary of the above updated rules.(1) Initialization. Setting the initial value α to α
(
0
), in the random sparse bipartite graph, it can be seen that the probability of a check node that belongs to the set T
i can be given by the following binomial distribution:(16)
p
C
i
0
=
C
d
c
i
α
0
i
1
-
α
0
d
c
-
i
.From Figure 3 and the probability p
(
l
) in (9), the probability p
T
i
(
0
) is given by the following binomial distribution: (17)
p
T
i
0
=
C
d
v
i
p
0
i
1
-
p
0
d
v
-
i
.(2) Calculating
p
C
j
(
l
+
1
). Substituting (7)–(11) into (6), then p
C
j
(
l
+
1
) is calculated.(3) Calculating
p
T
i
(
l
+
1
). Substituting (13)–(15) into (12), then p
T
i
(
l
+
1
) is calculated.(4) Calculating
α
(
l
+
1
). Substituting (4) and the probability p
T
i
(
l
+
1
) in step (3) into (5), α
(
l
+
1
) is calculated.


## 3.3. Comparison of VB Algorithm in the Asymptotic Regime

In this subsection, we compare the above analytical success thresholds of SWIFT algorithm with VB algorithm in the asymptotic regime. In Table1, we have listed the analytical success thresholds of the SWIFT and VB algorithms for different graphs.Table 1
Threshold for different (d
v, d
c) with SWIFT and VB algorithms.
(d
v, d
c)
(3, 6)
(4, 8)
(5, 10)
(6, 12)
(3, 4)
(5, 6)
(5, 7)
(7, 8)
SWIFTα
(
0
)
0.4294
0.3829
0.3411
0.3074
0.6476
0.5504
0.4782
0.4711
VBα
(
0
)
0.2574
0.2394
0.2179
0.1992
0.4488
0.3892
0.3266
0.3335As seen in Table1, for every graph, the SWIFT algorithm has a better performance than the VB algorithm. Overall, it is shown that the oversampling ratio γ
=
k
/
m
=
d
v
/
(
α
(
0
)
d
c
) improves when decreasing both d
v and d
c. Furthermore, when we keep compression ratio constant—that is, d
v
/
d
c is a constant—such as (3, 6), (4, 8), and (5, 10), as shown in Table 1, in general, when decreasing d
v, SWIFT and VB algorithms perform better. Based on the relationship between the threshold and (
d
v
,
d
c
), the sparse measurement matrix with superior performance can be designed.


## 4. Simulation Results and Analysis

In this section, simulation results are provided for analyzing the performance of the SWIFT decoding algorithm. We also provide asymptotic analysis described in Section3 with n
→
∞. According to the comparison of SWIFT decoding algorithm and asymptotic analysis, it is shown that there is a good agreement between them.


### 4.1. Asymptotic and Finite-Length Results for SWIFT Algorithm

Two scenarios are adopted for verifying Theorem2: (1) nonzero elements obey Gaussian distribution; (2) nonzero elements take value from the discrete set {
±
1
}. The reconstruction signal-to-noise ratio is defined as S
N
R
(
x
)
=
10
·
l
o
g
10
(
x
2
/
x
-
x
^
2
). We declare that recovery is successful if S
N
R
(
x
)
≥
100; for each point, 1000 Monte Carlo trials are performed. In the asymptotic analysis, we declare that the recovery is successful if α
(
l
)
<
1
0
-
8. To calculate the threshold of α, the search step is set to Δ
=
1
0
-
4.In the first experiment,(
8,32
) regular sparse measurement matrix is designed. The length of signal is set to n
=
10000, a signal element belongs to the support set with probability of α, and each nonzero signal element is drawn from the Gaussian distribution (or the discrete set {
±
1
}). The success recovery percentage of SWIFT algorithm versus the initial density factor α is shown in Figure 4. From Figure 4, it can be observed that, with the initial density factor α increasing, the performance of recovery decreases. In the figure, we can also see that the performance of two types of signals is almost identical. In addition, the threshold of the algorithm for the (
8,32
) regular sparse measurement is obtained by the asymptotic analysis, portrayed by dotted line. As shown in Figure 4, the threshold has a good agreement with the simulation curves.Figure 4
Success recovery percentage of SWIFT algorithm versus the initial density factorα; analysis threshold is curved by dotted line.In the second experiment, we verify that the SWIFT only requiresO
(
k
) measurements and O
(
k
) iterative step. In order to examine the measurement cost and run-time, a random sparse matrix with regular degree d
v
=
3 is adopted. Figure 5 illustrates the measurement costs and run-time as a function of the length of signal n. As seen in the figure, the measurement and run-time costs remain almost constant independently of n.Figure 5
Measurement costs and average running time versus length of signaln.
(a)
Measurement costs
(b)
Average running timeTo investigate the level of agreement between the asymptotic analysis and SWIFT algorithm, we provide the evolution ofα
l with iterations l for (
8,32
) regular sparse measurement in Figure 6. In this experiment, two cases of α
(
0
) value are adopted: one above the threshold and another below the threshold. As shown in Figure 6, there is also a good agreement between simulation results and asymptotic analysis for the two cases of α
(
0
).Figure 6
Evolution ofα
l versus iteration number l with (
8,32
) regular sparse measurement.To further show the degree of agreement between the asymptotic analysis and simulation results, we apply SWIFT algorithm to(
3,20
) regular sparse graph with n
=
{
1
×
1
0
3
,
1
×
1
0
4
,
1
×
1
0
5
,
5
×
1
0
5
}. The successful recovery of thresholds α
(
0
) is shown in Table 2. As shown in Table 2, when increasing n, the simulation results are closer to the asymptotic threshold.Table 2
Asymptotic threshold and simulation success thresholds for SWIFT algorithm.
n
1
×
1
0
3
1
×
1
0
4
1
×
1
0
5
5
×
1
0
5
Asymptotic
Threshold
α
(
0
)
=
0.0851
α
(
0
)
=
0.0946
α
(
0
)
=
0.106
α
(
0
)
=
0.1204
α
(
0
)
=
0.1246


### 4.2. Comparison of SWIFT Algorithm and VB Algorithm at Finite-Length

In this subsection, we compare the SWIFT algorithm with the VB algorithm in the noiseless setting. In the VB algorithm, two,(
3,15
) and (
3,72
), regular sparse matrices are designed with signal length n
=
2500,12000, respectively. To have a fair comparison, in the SWIFT algorithm, two, (
3,30
) and (
3,144
), regular sparse matrices are generated with signal length n
=
2500,12000, respectively. Each nonzero signal element is taken from a standard Gaussian distribution. The success recovery percentage of SWIFT and VB algorithms versus the sparsity k is shown in Figure 7. As shown in Figure 7, the SWIFT algorithm performs better than the VB algorithm especially for large signal length, which coincides with the analysis in Section 3.3.Figure 7
Success recovery percentage of SWIFT and VB algorithms versus the sparsityk.


## 4.1. Asymptotic and Finite-Length Results for SWIFT Algorithm

Two scenarios are adopted for verifying Theorem2: (1) nonzero elements obey Gaussian distribution; (2) nonzero elements take value from the discrete set {
±
1
}. The reconstruction signal-to-noise ratio is defined as S
N
R
(
x
)
=
10
·
l
o
g
10
(
x
2
/
x
-
x
^
2
). We declare that recovery is successful if S
N
R
(
x
)
≥
100; for each point, 1000 Monte Carlo trials are performed. In the asymptotic analysis, we declare that the recovery is successful if α
(
l
)
<
1
0
-
8. To calculate the threshold of α, the search step is set to Δ
=
1
0
-
4.In the first experiment,(
8,32
) regular sparse measurement matrix is designed. The length of signal is set to n
=
10000, a signal element belongs to the support set with probability of α, and each nonzero signal element is drawn from the Gaussian distribution (or the discrete set {
±
1
}). The success recovery percentage of SWIFT algorithm versus the initial density factor α is shown in Figure 4. From Figure 4, it can be observed that, with the initial density factor α increasing, the performance of recovery decreases. In the figure, we can also see that the performance of two types of signals is almost identical. In addition, the threshold of the algorithm for the (
8,32
) regular sparse measurement is obtained by the asymptotic analysis, portrayed by dotted line. As shown in Figure 4, the threshold has a good agreement with the simulation curves.Figure 4
Success recovery percentage of SWIFT algorithm versus the initial density factorα; analysis threshold is curved by dotted line.In the second experiment, we verify that the SWIFT only requiresO
(
k
) measurements and O
(
k
) iterative step. In order to examine the measurement cost and run-time, a random sparse matrix with regular degree d
v
=
3 is adopted. Figure 5 illustrates the measurement costs and run-time as a function of the length of signal n. As seen in the figure, the measurement and run-time costs remain almost constant independently of n.Figure 5
Measurement costs and average running time versus length of signaln.
(a)
Measurement costs
(b)
Average running timeTo investigate the level of agreement between the asymptotic analysis and SWIFT algorithm, we provide the evolution ofα
l with iterations l for (
8,32
) regular sparse measurement in Figure 6. In this experiment, two cases of α
(
0
) value are adopted: one above the threshold and another below the threshold. As shown in Figure 6, there is also a good agreement between simulation results and asymptotic analysis for the two cases of α
(
0
).Figure 6
Evolution ofα
l versus iteration number l with (
8,32
) regular sparse measurement.To further show the degree of agreement between the asymptotic analysis and simulation results, we apply SWIFT algorithm to(
3,20
) regular sparse graph with n
=
{
1
×
1
0
3
,
1
×
1
0
4
,
1
×
1
0
5
,
5
×
1
0
5
}. The successful recovery of thresholds α
(
0
) is shown in Table 2. As shown in Table 2, when increasing n, the simulation results are closer to the asymptotic threshold.Table 2
Asymptotic threshold and simulation success thresholds for SWIFT algorithm.
n
1
×
1
0
3
1
×
1
0
4
1
×
1
0
5
5
×
1
0
5
Asymptotic
Threshold
α
(
0
)
=
0.0851
α
(
0
)
=
0.0946
α
(
0
)
=
0.106
α
(
0
)
=
0.1204
α
(
0
)
=
0.1246


## 4.2. Comparison of SWIFT Algorithm and VB Algorithm at Finite-Length

In this subsection, we compare the SWIFT algorithm with the VB algorithm in the noiseless setting. In the VB algorithm, two,(
3,15
) and (
3,72
), regular sparse matrices are designed with signal length n
=
2500,12000, respectively. To have a fair comparison, in the SWIFT algorithm, two, (
3,30
) and (
3,144
), regular sparse matrices are generated with signal length n
=
2500,12000, respectively. Each nonzero signal element is taken from a standard Gaussian distribution. The success recovery percentage of SWIFT and VB algorithms versus the sparsity k is shown in Figure 7. As shown in Figure 7, the SWIFT algorithm performs better than the VB algorithm especially for large signal length, which coincides with the analysis in Section 3.3.Figure 7
Success recovery percentage of SWIFT and VB algorithms versus the sparsityk.


## 5. Conclusion

In this paper, we investigate a new class of LDPC-DFT measurement matrices and their recovery algorithm. These new measurement matrices exploit the sparsity of parity-check matrices of LDPC and the phase of DFT matrices to recover the original signal. In addition, a general framework for the asymptotic analysis of this fast recovery algorithm is proposed. The analysis shows that there exists a threshold on the density factorα
=
k
/
n; if below this threshold, the recovery algorithm is successful; otherwise it will fail. Moreover, it can be found that the threshold is dependent on the parameter of LDPC matrix which provides a basis for us to design the measurement matrices. We also observe that the SWIFT algorithm performs better than other schemes based on LDPC codes.



---

*Source: 6340430-2016-04-10.xml*