Verification-based message-passing algorithms in compressed sensing

Verification-based message-passing algorithms (VB-MPAs) in compressed sensing (CS), a branch of digital signal processing that deals with measuring sparse signals, are some methods to efficiently solve the recovery problem in compressed sensing. One of the main goal in compressed sensing is the recovery process. Generally speaking, recovery process in compressed sensing is a method by which the original signal is estimated using the knowledge of the compressed signal and the measurement matrix. Mathematically, the recovery process in Compressed Sensing is finding the sparsest possible solution of an under-determined system of linear equations. Based on the nature of the measurement matrix one can employ different reconstruction methods. If the measurement matrix is also sparse, one efficient way is to use Message Passing Algorithms for signal recovery. Although there are message passing approaches that deals with dense matrices, the nature of those algorithms are to some extent different from the algorithms working on sparse matrices.
Overview.
The main problem in recovery process in CS is to find the sparsest possible solution to the following under-determined system of linear equations formula_1 where formula_2 is the measurement matrix, formula_3 is the original signal to be recovered and formula_4 is the compresses known signal. When the matrix formula_2 is sparse, one can represent this matrix by a bipartite graph formula_6 for better understanding.
formula_7 is the set of variable nodes in formula_8 which represents the set of elements of formula_3 and also formula_10 is the set of check nodes corresponding to the set of elements of formula_4. Besides, there is an edge formula_12 between formula_13 and formula_14 if the corresponding elements in formula_2 is non-zero, i.e. formula_16. Moreover, the weight of the edge formula_17. Here is an example of a binary sparse measurement matrix where the weights of the edges are either zero or one.
formula_18
The basic idea behind message passing algorithms in CS is to transmit appropriate messages between variable nodes and check nodes in an iterative manner in order to efficiently find signal formula_3. These messages are different for variable nodes and check nodes. However, the basic nature of the messages for all variable node and check nodes are the same in all of the verification based message passing algorithms. The messages formula_20 emanating from variable node formula_21 contains the value of the check node and an indicator which shows if the variable node is verified or not. Moreover, the messages formula_22 emanating from check node formula_23 contains the value of the check node and the remaining degree of the check node in the graph.
In each iteration, every variable node and check node produce a new message to be transmitted to all of its neighbors based on the messages that they have received from their own neighbors. This local property of the message passing algorithms enables them to be implemented as parallel processing algorithms and makes the time complexity of these algorithm so efficient.
Message passing rules.
The common rule between all verification based message passing algorithms is the fact that once a variable node become verified then this variable node can be removed from the graph and the algorithm can be executed to solve the rest of the graph. Different verification bases message passing algorithms use different combinations of verification rules.
The verification rules are as follows:
The message passing rules given above are the basic and only rules that should be used in any verification based message passing algorithm. It is shown that these simple rules can efficiently recover the original signal provided that certain conditions are satisfied.
Algorithms.
There are four algorithms known as VB-MPA's, namely Genie, LM, XH, and SBB. All of these algorithms use the same strategy for recovery of the original signal; however, they use different combination of the message passing rules to verify variable nodes.
Genie Algorithm.
Genie algorithm is the benchmark in this topic. Firstly, Genie algorithm is assumed to have the knowledge of the support set of the signal, i.e. the set of non-zero elements of the original signal. Using this knowledge, Genie should not care about the zero variable nodes in the graph, and the only task of the Genie algorithm is to recover the values of the non-zero elements of the original signal. Although, Genie does not have any practical aspect, it can be regarded as the benchmark of the problem especially in the sense that this algorithm outperforms other algorithms in this category and one can measure how successful one algorithms is by comparing that to the Genie algorithm.
Since Genie only wants to find the value of the non-zero elements of the signal it is not necessary to employ rules that are responsible for zero valued variable node in this algorithm. Therefore, Genie only uses D1CN as the verification rule.
LM algorithm.
This algorithm unlike the Genie algorithm does not have any knowledge about the support set of signal, and it uses D1CN and ZCN together to solve the recovery process in CS. In fact, ZCN is the rule that attempts to verify the zero valued variable nodes and D1CN is responsible for non-zero valued variable nodes. This usage of this algorithm is when one does not have non-binary matrix. In such cases, employing the third rule violated the locality nature of the algorithms. This issue will be considered in SBB algorithm.
XH algorithm.
This algorithm is the same as LM, but it only uses ECN instead of D1CN for the verification of the non-zero variable nodes. If the non-zero elements of the measurement matrix are binary, then this algorithm cannot be implemented efficiently and the locality of the algorithm will be violated.
SBB algorithm.
The most powerful practical algorithm among all of the verification message passing algorithms is the SBB algorithm that employs all of the verification rules for the recovery of the original signal. In this algorithm, D1CN and ECN are responsible for the verification of the non-zero elements of the signal and ZCN and ECN will verify zero variable nodes.
The pseudo code of the VB-MPAs is as follows. In the following algorithm formula_24 represents the formula_25 component of the messages emanating from variable and check nodes. formula_26 is in fact a variable that keeps the labels of the verified variable nodes. formula_27 is also used to keep the set of verified variable nodes in the previous iteration. By using these two variables one can see if there is any progress in the number of verified variable nodes in the algorithm, and if there is no progress then the algorithm will terminate.
 1 function VB_MPA("Measurement Matrix A", "Compressed Vector y"):
 2 formula_28 // Initializations
 3 formula_29 // Initializations
 4 formula_30 // Initializations
 5 formula_31 // Initializations
 6 While (formula_32) // Main Loop
 7 formula_33
 9 /*============================= Half round 1 of round 1 ============================ */ 
 10 for every formula_34
 11 formula_35
 12 formula_36
 13 formula_37
 14 end for
 15 /*============================= Half round 2 of round 1 ============================ */
 16 for every formula_38
 17 update_rule(v,Algorithm)
 18 If a variable node v is verified then
 19 add v to VN
 20 end if
 21 end for
 22 /*============================= Half round 1 of round 2 ============================ */
 23 for every formula_34
 24 formula_35
 25 formula_36
 26 formula_37
 27 end for
 28 /*============================= Half round 2 of round 2 ============================ */
 29 for every formula_43
 30 if formula_44 then
 31 formula_45
 32 add v to VN
 33 end if
 34 end for
 35 end while 
 36 return formula_46
In all of the algorithms the messages emanating from check nodes are the same; however, since the verification rules are different for different algorithms the messages produced by variable nodes will be different in each algorithm. The algorithm given above works for all of the VB-MPA's, and different algorithms use different rules in half round 2 of round 1 and 2. For instance, Genie algorithm uses D1CN rule in Half round 2 of round 1, and in fact the half round 2 of round 2 which uses ZCN rule is useless in Genie algorithm. LM algorithm uses D1CN in Half round 2 of round 1 and XH algorithm uses ECN rule in this stage instead of D1CN. SBB algorithm also uses both D1CN and ECN rule in the second half round of round 1. All of these rules can be efficiently implemented in update_rule function in the second half round of round 1.
Proof of correctness.
Although there is no guarantee that these algorithms succeed in all of the cases but we can guarantee that if some of the variable nodes become verified during these algorithms then the values of those variable nodes are correct almost surely. In order to show that it is enough to show that all of the verification rules work perfectly and without false verification.
Correctness of ZCN.
The algebraic point of view of ZCN rule is that if in a system of linear equations the right hand side of the equation is zero then almost surely all of the unknowns in that equations are zero. This is due to the fact that the original signal is assumed to be sparse, besides, we also should have the assumption that the non-zero elements of the signals are chosen form a continuous distribution. Suppose that there are formula_47 variables in that equation, if some of them in formula_48 elements are non-zero then the other formula_49 variable node value should have exactly the negative value of the summation of those formula_48 variable nodes. If the non-zero elements of the original signal are chosen from a continuous distribution then the probability of this to occur is zero. Therefore, ZCN rule works perfectly.
Correctness of D1CN.
D1CN says that if a variable node is the only unknown variable in an equation then the value of that variable equals the right hand side of that equation. In fact, an equation with just one unknown variable is a check node with degree one, i.e. a check node with just one unverified variable node in its neighborhood.
Correctness of ECN.
This rule has two parts, the first part deals with non-zero elements of the signal while the second one is responsible for the zero elements of the original signal. For the first part, it says that if we have two or more equations with the same right hand side, and if we only have one single unknown variable formula_51 common in all of those equations then the value of this common variable should be the value of the right hand side of those equations. Besides, it says that all other variables in those equations should be zero. Suppose that one of those variables formula_52 is not zero, then the right hand side of the equation which contains both formula_53 should be formula_54 (For simplicity assume that the edge weights are all 1 or zero). Besides, since we know that formula_51 is the only unique variable in all of these equations then there should be one equation formula_56 in which formula_51 exists and formula_52 does not exist. On the other hand, we know that the right hand side of these equations are the same; therefore, the right hand side of equation formula_56 should also be formula_60. If we remove formula_52 from this equation we should have the summation of some unknown variables to be a non-zero value formula_62. Since the non-zero elements of formula_3 are chosen randomly from a continuous distribution the probability that this summation equals exactly formula_62 is zero. Therefore, almost surely the value of formula_51 is zero and all other variables in these equations have value zero.
There is just one scenario remained for the second part of the ECN rule as most of it has been covered in the first part. This scenario is the one that we have some equations with the same right hand side but there is two or more variable node common in all of those equations. In this case, we can say nothing about those common variable nodes; however, we can say that all the other variable nodes in those equations are zero. The proof of this claim can be achieved by a change of variable in those equations. Suppose that formula_66 are the common variable nodes in those equations. If we set formula_67 then the problem will be changed to the first part where we only have one common variable node in all of those equations. Therefore, with the same reasoning as in the first part we can see that all other variable nodes that are not common in all of those equations can be verified with value zero almost surely.
When the non-zero elements of the measurement matrix are chosen randomly from a continuous distribution, then it can be shown that if one variable node receives equal messages divided by the edge weights from its neighbors then this variable node is the only unique variable connected to all of those check nodes, therefore, the rule can be applied using a local decision approach, and the variable node can verify itself without further knowledge about the other connections of those check nodes. Moreover, the second part of the ECN rule is not necessary to be implemented as the non-zero verified variable node in the ECN rule will be removed from the bipartite graph in the next iteration and ZCN rule will be enough to verify all the zero valued variable nodes remained from those equations with the same right hand side. All in all, when the non-zero elements of the measurement matrix are chosen form a continuous distribution then the SBB and XH algorithm that use ECN rule can be implemented efficiently.
Run-time analysis.
Every minor loop in the main loop of the algorithm can be executed in parallel processors, if we consider each variable and check node as a separate processor. Therefore, every minor loop in the algorithm can be executed in constant time formula_68. Moreover, since the algorithm will terminate when there is no progress in verification of the variable nodes then the if in the worst case in each iteration of the main loop there is only one variable node to be verified, then the maximum number of times that the main loop will be executed is formula_69. Therefore, the whole algorithm will be executed in formula_70 time.