View source for Verification-based message-passing algorithms in compressed sensing

{{Multiple issues|
{{more footnotes|date=February 2015}}
{{citation style|date=February 2015}}
}}

'''Verification-based message-passing [[algorithms]]''' ('''VB-MPAs''') '''in [[compressed sensing]]''' ('''CS'''), a branch of [[digital signal processing]] that deals with measuring [[Compressed sensing|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.<ref name="donoho2012information">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.</ref> 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.<ref name="donoho2012information"/><ref name="Chandar2010simple">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.</ref>

== 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 <math>Ax = y</math> where <math>A</math> is the measurement matrix, <math>x</math> is the original signal to be recovered and <math>y</math> is the compresses known signal. When the matrix <math>A</math> is sparse, one can represent this matrix by a [[bipartite graph]] <math>G=(V_l\cup V_r,E)</math> for better understanding.<ref name="Chandar2010simple"/><ref>[[Piotr Indyk|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.</ref><ref>[[Anna C. Gilbert|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.</ref><ref name="Sarvotham2006Sudocodes ">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.</ref>
<math>V_l</math> is the set of variable nodes in <math>G</math> which represents the set of elements of <math>x</math> and also <math>V_r</math> is the set of check nodes corresponding to the set of elements of <math>y</math>. Besides, there is an edge <math>e=(u,v)</math> between <math>u\in V_l</math> and <math>v\in V_r</math> if the corresponding elements in <math>A</math> is non-zero, i.e. <math>A_{v,u}\neq 0</math>. Moreover, the weight of the edge <math>w(e)=A_{v,u}</math>.<ref name="Eftekhari2012Density">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.</ref> Here is an example of a binary sparse measurement matrix where the weights of the edges are either zero or one.

[[File:Example1 VB MPA.png|500px|thumbnail|bi-regular bipartite graph corresponding to the measurement matrix A<ref name="Farhangdoust"/>]]

<math>
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]
</math>

The basic idea behind message passing algorithms in CS is to transmit appropriate messages between variable nodes and check nodes in an [[Iterative method|iterative manner]] in order to efficiently find signal <math>x</math>. 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.<ref name="Eftekhari2012Density"/> The messages <math>\mu^{v}(v_i):~V_l \mapsto \mathbb{R}\times \{0,1\}</math> emanating from variable node <math>v_i</math> contains the value of the check node and an indicator which shows if the variable node is verified or not. Moreover, the messages <math>\mu^{c}(c_i):~V_r \mapsto \mathbb{R}\times \mathbb{Z}^+</math> emanating from check node <math>c_i</math> contains the value of the check node and the remaining degree of the check node in the graph.<ref name="Eftekhari2012Density"/><ref name="Farhangdoust">{{cite web|title=Message Passing Algorithms|first1=Seyed Mohammad Ebrhiam|last1=Farhangdoust|url=http://people.scs.carleton.ca/~maheshwa/courses/5703COMP/14Seminars/Message-Passing/submitted/MPA.pdf}}</ref>

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.<ref = Name="Zhang2009Iterative">F. Zhang and H. D. Pfister, “On the iterative decoding of high-rate LDPC codes with applications in compressed sensing,” arXiv preprint [https://arxiv.org/abs/0903.2232 arXiv:0903.2232], 2009.</ref>

== Message passing rules<ref Name="Luby2005Verification">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.</ref> ==
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.<ref name="Eftekhari2012Density"/>

The verification rules are as follows:

* '''Zero Check Node (ZCN):'''<ref = Name="Zhang2009Iterative"/> 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):'''<ref = Name="Zhang2009Iterative"/> 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):'''<ref = Name="Zhang2009Iterative"/> 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.<ref = Name="Zhang2009Iterative"/><ref name="Eftekhari2012Density"/>

== Algorithms ==

There are four algorithms known as VB-MPA's, namely Genie, LM, XH, and SBB.<ref name="Eftekhari2012Density"/> 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<ref name="Eftekhari2012Density"/> ===
Genie algorithm is the [[Benchmark (computing)|benchmark]] in this topic. Firstly, Genie algorithm is assumed to have the knowledge of the [[Support (mathematics)|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<ref name="Eftekhari2012Density"/><ref = Name="Zhang2009Iterative"/> ===
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.<ref name="Eftekhari2012Density"/>

=== XH algorithm<ref name="Eftekhari2012Density"/> ===
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 [[Logical matrix|binary]], then this algorithm cannot be implemented efficiently and the locality of the algorithm will be violated.

=== SBB algorithm<ref name="Eftekhari2012Density"/><ref Name="Luby2005Verification"/> ===
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 <math>\mu_i</math> represents the <math>i^{th}</math> component of the messages emanating from variable and check nodes. <math>VN</math> is in fact a variable that keeps the labels of the verified variable nodes. <math>VN'</math> 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.<ref name="Eftekhari2012Density"/><ref Name="Luby2005Verification"/>

 1  '''function''' VB_MPA(''Measurement Matrix A'', ''Compressed Vector y''):<ref name="Farhangdoust"/>
 2      <math>\mu^c(c) := (y(c),d_c)~~\forall c\in V_r </math>           // Initializations
 3      <math>\mu^v(v) := (0,0)~~\forall v\in V_l </math>                // Initializations
 4      <math>VN := \emptyset</math>                                     // Initializations
 5      <math>VN' := \{-1\}</math>                                       // Initializations
 6      '''While''' '''('''<math>VN' \neq VN</math>''')'''               // Main Loop
 7          <math>VN' := VN</math>
 9          /*============================= Half round 1 of round 1 ============================ */    
 10         '''for''' every <math>c \in V_r</math>
 11             <math>value := y(c) - \sum_{v\in \mathcal{N}(c)}{\mu_2^v(v)\mu_1^v(v)A(c,v)}</math>
 12             <math>degree := d_c - \sum_{v\in \mathcal{N}(c)}{\mu_2^v(v)}</math>
 13             <math>\mu^c(c) := (value,degree)</math>
 14         '''end for'''
 15         /*============================= Half round 2 of round 1 ============================ */
 16         '''for''' every <math>v \in V_r \setminus VN </math>
 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 <math>c \in V_r</math>
 24             <math>value := y(c) - \sum_{v\in \mathcal{N}(c)}{\mu_2^v(v)\mu_1^v(v)A(c,v)}</math>
 25             <math>degree := d_c - \sum_{v\in \mathcal{N}(c)}{\mu_2^v(v)}</math>
 26             <math>\mu^c(c) := (value,degree)</math>
 27         '''end for'''
 28         /*============================= Half round 2 of round 2 ============================ */
 29         '''for''' every <math>v \in V_l \setminus VN</math>
 30             '''if''' <math>\exists c\in \mathcal{N}(v):~\mu_1^c(c)=0</math> '''then'''
 31                 <math>\mu^v(v) := (0,1)</math>
 32                 add v to VN
 33             '''end if'''
 34         '''end for'''
 35     '''end while''' 
 36     '''return''' <math>\mu^v_1(v)~~\forall v\in V_l</math>

[[File:Output HO8M5R.gif|700px|thumbnail|SBB Algorithm<ref name="Farhangdoust"/>]]

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.<ref name="Eftekhari2012Density"/> 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 alarm|false verification]].<ref name="Eftekhari2012Density"/><ref = Name="Zhang2009Iterative"/>

=== 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 <math>d</math> variables in that equation, if some of them in <math>d-1</math> elements are non-zero then the other <math>d^{th}</math> variable node value should have exactly the negative value of the summation of those <math>d-1</math> 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.<ref name="Eftekhari2012Density"/><ref = Name="Zhang2009Iterative"/>

=== 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 [[Sides of an equation|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.<ref name="Eftekhari2012Density"/><ref = Name="Zhang2009Iterative"/>

=== 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 [[Sides of an equation|right hand side]], and if we only have one single [[Variable (mathematics)|unknown variable]] <math>v</math> 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 <math>v'</math> is not zero, then the [[right hand side]] of the equation which contains both <math>v, v'</math> should be <math>x(v') + x(v)</math> (For simplicity assume that the [[Graph theory|edge weights]] are all 1 or zero). Besides, since we know that <math>v</math> is the only unique variable in all of these equations then there should be one equation <math>c</math> in which <math>v</math> exists and <math>v'</math> 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 <math>c</math> should also be <math>x(v) + x(v')</math>. If we remove <math>v'</math> from this equation we should have the summation of some unknown variables to be a non-zero value <math>x(v')</math>. Since the non-zero elements of <math>x</math> are chosen randomly from a [[continuous distribution]] the probability that this summation equals exactly <math>x(v')</math> is zero. Therefore, [[almost surely]] the value of <math>v</math> is zero and all other variables in these equations have value zero.<ref name="Eftekhari2012Density"/><ref = Name="Zhang2009Iterative"/><ref name="Farhangdoust"/>

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 <math>v_1,v_2,...,v_q</math> are the common variable nodes in those equations. If we set <math>v' = v_1+v_2+...+v_q</math> 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]].<ref name="Eftekhari2012Density"/><ref = Name="Zhang2009Iterative"/><ref name="Farhangdoust"/>

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 [[Graph theory|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.<ref name="Eftekhari2012Density"/>

== [[Analysis of algorithms|Run-time analysis]] ==
Every minor loop in the main loop of the algorithm can be executed in [[Parallel computing|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 [[Big O notation|constant time <math>O(1)</math>]]. 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 <math>|V_l|</math>. Therefore, the whole algorithm will be executed in [[Big O notation|<math>O(|V_l|)</math> time]].<ref name="Farhangdoust"/>

==References==
{{Reflist}}

[[Category:Digital signal processing]]
[[Category:Distributed algorithms]]
[[Category:Inter-process communication]]