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 A x = y {\displaystyle Ax=y} where A {\displaystyle A} is the measurement matrix, x {\displaystyle x} is the original signal to be recovered and y {\displaystyle y} is the compresses known signal. When the matrix A {\displaystyle A} is sparse, one can represent this matrix by a bipartite graph G = ( V l ∪ V r , E ) {\displaystyle G=(V_{l}\cup V_{r},E)} for better understanding.

V l {\displaystyle V_{l}} is the set of variable nodes in G {\displaystyle G} which represents the set of elements of x {\displaystyle x} and also V r {\displaystyle V_{r}} is the set of check nodes corresponding to the set of elements of y {\displaystyle y} . Besides, there is an edge e = ( u , v ) {\displaystyle e=(u,v)} between u ∈ V l {\displaystyle u\in V_{l}} and v ∈ V r {\displaystyle v\in V_{r}} if the corresponding elements in A {\displaystyle A} is non-zero, i.e. A v , u ≠ 0 {\displaystyle A_{v,u}\neq 0} . Moreover, the weight of the edge w ( e ) = A v , u {\displaystyle w(e)=A_{v,u}} . Here is an example of a binary sparse measurement matrix where the weights of the edges are either zero or one.

… excerpt ends here. Continue reading the full article.