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.D. L. Donoho, A. Javanmard, and A. Montanari, “Information-theoretically optimal compressed sensing via spatial coupling and approximate message passing,” in Information Theory Proceedings (ISIT), 2012 IEEE International Symposium on, 2012, pp. 1231–1235. 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.Chandar, Venkat, Devavrat Shah, and Gregory W. Wornell. "A simple message-passing algorithm for compressed sensing." Information Theory Proceedings (ISIT), 2010 IEEE International Symposium on. IEEE, 2010.
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 where is the measurement matrix, is the original signal to be recovered and is the compresses known signal. When the matrix is sparse, one can represent this matrix by a bipartite graph for better understanding.Indyk, Piotr. "Explicit constructions for compressed sensing of sparse signals." Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2008.Gilbert, Anna C., et al. "One sketch for all: fast algorithms for compressed sensing." Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. ACM, 2007.Sarvotham, Shriram, Dror Baron, and Richard G. Baraniuk. "Sudocodes-Fast Measurement and Reconstruction of Sparse Signals." Information Theory, 2006 IEEE International Symposium on. IEEE, 2006. is the set of variable nodes in which represents the set of elements of and also is the set of check nodes corresponding to the set of elements of . Besides, there is an edge between and if the corresponding elements in is non-zero, i.e. . Moreover, the weight of the edge .Y. Eftekhari, A. Heidarzadeh, A. H. Banihashemi, and I. Lambadaris, “Density evolution analysis of node-based verification-based algorithms in compressed sensing,” Information Theory, IEEE Transactions on, vol. 58, no. 10, pp. 6616–6645, 2012. Here is an example of a binary sparse measurement matrix where the weights of the edges are either zero or one.
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 . 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 emanating from variable node contains the value of the check node and an indicator which shows if the variable node is verified or not. Moreover, the messages emanating from check node 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.F. Zhang and H. D. Pfister, “On the iterative decoding of high-rate LDPC codes with applications in compressed sensing,” arXiv preprint arXiv:0903.2232, 2009.
Message passing rules Source:Luby, Michael G., and Michael Mitzenmacher. "Verification-based decoding for packet-based low-density parity-check codes." IEEE Transactions on Information Theory 51.1 (2005): 120-127.
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:
Zero Check Node (ZCN): If there is at least one check node with value zero in the neighborhood of a variable node then this variable node should be verified with value zero Degree 1 Check Node: (D1CN): If there is one or more check nodes with degree 1 in the neighborhood of a variable node, then the variable node should be verified with the value chosen randomly from the value of those degree 1 check nodes. Equal Check Node: (ECN): If there is a single variable node connected to at least two or more check nodes with the same non-zero value then the value of the variable node should be verified with the common value of those check nodes. Besides, every other variable nodes that are partially connected to these check nodes (not all of them) should be verified with value zero.
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 Source:
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 Sources:
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 represents the component of the messages emanating from variable and check nodes. is in fact a variable that keeps the labels of the verified variable nodes. 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 // Initializations 3 // Initializations 4 // Initializations 5 // Initializations 6 While () // Main Loop 7 9 /*============================= Half round 1 of round 1 ============================ */ 10 for every 11 12 13 14 end for 15 /*============================= Half round 2 of round 1 ============================ */ 16 for every 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 24 25 26 27 end for 28 /*============================= Half round 2 of round 2 ============================ */ 29 for every 30 if then 31 32 add v to VN 33 end if 34 end for 35 end while 36 return
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 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 variables in that equation, if some of them in elements are non-zero then the other variable node value should have exactly the negative value of the summation of those 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