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. ^[1] 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. ^{[1] [2]}

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 ${\displaystyle Ax=y}$ where ${\displaystyle A}$ is the measurement matrix, ${\displaystyle x}$ is the original signal to be recovered and ${\displaystyle y}$ is the compresses known signal. When the matrix ${\displaystyle A}$ is sparse, one can represent this matrix by a bipartite graph ${\displaystyle G=(V_{l}\cup V_{r},E)}$ for better understanding. ^{[2] [3] [4] [5]} ${\displaystyle V_{l}}$ is the set of variable nodes in ${\displaystyle G}$ which represents the set of elements of ${\displaystyle x}$ and also ${\displaystyle V_{r}}$ is the set of check nodes corresponding to the set of elements of ${\displaystyle y}$. Besides, there is an edge ${\displaystyle e=(u,v)}$ between ${\displaystyle u\in V_{l}}$ and ${\displaystyle v\in V_{r}}$ if the corresponding elements in ${\displaystyle A}$ is non-zero, i.e. ${\displaystyle A_{v,u}\neq 0}$. Moreover, the weight of the edge ${\displaystyle w(e)=A_{v,u}}$. ^[6] Here is an example of a binary sparse measurement matrix where the weights of the edges are either zero or one.

bi-regular bipartite graph corresponding to the measurement matrix A

${\displaystyle A=\left[{\begin{array}{c c c c c c c c c c c c}0&0&1&0&0&0&0&0&1&0&1&0\\0&0&0&1&0&1&0&1&0&0&0&0\\1&0&0&0&0&1&0&0&0&0&1&0\\1&1&1&0&0&0&0&0&0&0&0&0\\0&0&0&1&0&0&1&0&0&0&0&1\\0&0&0&0&1&0&1&0&0&0&0&1\\0&0&0&0&0&0&0&1&1&1&0&0\\0&1&0&0&1&0&0&0&0&1&0&0\end{array}}\right]}$

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 ${\displaystyle x}$. 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. ^[6] The messages ${\displaystyle \mu ^{v}(v_{i}):~V_{l}\mapsto \mathbb {R} \times \{0,1\}}$ emanating from variable node ${\displaystyle v_{i}}$ contains the value of the check node and an indicator which shows if the variable node is verified or not. Moreover, the messages ${\displaystyle \mu ^{c}(c_{i}):~V_{r}\mapsto \mathbb {R} \times \mathbb {Z} ^{+}}$ emanating from check node ${\displaystyle c_{i}}$ contains the value of the check node and the remaining degree of the check node in the graph. ^{[6] [7]}

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. ^[8]

Message passing rules ^[9]

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. ^[6]

The verification rules are as follows:

• Zero Check Node (ZCN): ^[8] 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): ^[8] 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): ^[8] 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. ^{[8] [6]}

Algorithms

There are four algorithms known as VB-MPA's, namely Genie, LM, XH, and SBB. ^[6] 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 ^[6]

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 ^{[6] [8]}

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. ^[6]

XH algorithm ^[6]

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 ^{[6] [9]}

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 ${\displaystyle \mu _{i}}$ represents the ${\displaystyle i^{th}}$ component of the messages emanating from variable and check nodes. ${\displaystyle VN}$ is in fact a variable that keeps the labels of the verified variable nodes. ${\displaystyle VN'}$ 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. ^{[6] [9]}

1  function VB_MPA(Measurement Matrix A, Compressed Vector y): [7]  2      ${\displaystyle \mu ^{c}(c):=(y(c),d_{c})~~\forall c\in V_{r}}$           // Initializations 3      ${\displaystyle \mu ^{v}(v):=(0,0)~~\forall v\in V_{l}}$                // Initializations 4      ${\displaystyle VN:=\emptyset }$                                     // Initializations 5      ${\displaystyle VN':=\{-1\}}$                                       // Initializations 6      While(${\displaystyle VN'\neq VN}$)               // Main Loop 7          ${\displaystyle VN':=VN}$ 9          /*============================= Half round 1 of round 1 ============================ */     10         for every ${\displaystyle c\in V_{r}}$ 11             ${\displaystyle value:=y(c)-\sum _{v\in {\mathcal {N}}(c)}{\mu _{2}^{v}(v)\mu _{1}^{v}(v)A(c,v)}}$ 12             ${\displaystyle degree:=d_{c}-\sum _{v\in {\mathcal {N}}(c)}{\mu _{2}^{v}(v)}}$ 13             ${\displaystyle \mu ^{c}(c):=(value,degree)}$ 14         end for 15         /*============================= Half round 2 of round 1 ============================ */ 16         for every ${\displaystyle v\in V_{r}\setminus VN}$ 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 ${\displaystyle c\in V_{r}}$ 24             ${\displaystyle value:=y(c)-\sum _{v\in {\mathcal {N}}(c)}{\mu _{2}^{v}(v)\mu _{1}^{v}(v)A(c,v)}}$ 25             ${\displaystyle degree:=d_{c}-\sum _{v\in {\mathcal {N}}(c)}{\mu _{2}^{v}(v)}}$ 26             ${\displaystyle \mu ^{c}(c):=(value,degree)}$ 27         end for 28         /*============================= Half round 2 of round 2 ============================ */ 29         for every ${\displaystyle v\in V_{l}\setminus VN}$ 30             if${\displaystyle \exists c\in {\mathcal {N}}(v):~\mu _{1}^{c}(c)=0}$then 31                 ${\displaystyle \mu ^{v}(v):=(0,1)}$ 32                 add v to VN 33             end if 34         end for 35     end while  36     return${\displaystyle \mu _{1}^{v}(v)~~\forall v\in V_{l}}$

SBB Algorithm

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. ^[6] 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. ^{[6] [8]}

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 ${\displaystyle d}$ variables in that equation, if some of them in ${\displaystyle d-1}$ elements are non-zero then the other ${\displaystyle d^{th}}$ variable node value should have exactly the negative value of the summation of those ${\displaystyle d-1}$ 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. ^{[6] [8]}

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. ^{[6] [8]}

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 ${\displaystyle v}$ 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 ${\displaystyle v'}$ is not zero, then the right hand side of the equation which contains both ${\displaystyle v,v'}$ should be ${\displaystyle x(v')+x(v)}$ (For simplicity assume that the edge weights are all 1 or zero). Besides, since we know that ${\displaystyle v}$ is the only unique variable in all of these equations then there should be one equation ${\displaystyle c}$ in which ${\displaystyle v}$ exists and ${\displaystyle v'}$ 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 ${\displaystyle c}$ should also be ${\displaystyle x(v)+x(v')}$. If we remove ${\displaystyle v'}$ from this equation we should have the summation of some unknown variables to be a non-zero value ${\displaystyle x(v')}$. Since the non-zero elements of ${\displaystyle x}$ are chosen randomly from a continuous distribution the probability that this summation equals exactly ${\displaystyle x(v')}$ is zero. Therefore, almost surely the value of ${\displaystyle v}$ is zero and all other variables in these equations have value zero. ^{[6] [8] [7]}

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 ${\displaystyle v_{1},v_{2},...,v_{q}}$ are the common variable nodes in those equations. If we set ${\displaystyle v'=v_{1}+v_{2}+...+v_{q}}$ 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. ^{[6] [8] [7]}

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. ^[6]

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 ${\displaystyle O(1)}$. 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 ${\displaystyle |V_{l}|}$. Therefore, the whole algorithm will be executed in ${\displaystyle O(|V_{l}|)}$ time. ^[7]

References

1. 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.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.
7. Farhangdoust, Seyed Mohammad Ebrhiam. "Message Passing Algorithms" (PDF).
8. 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.
9. 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.