  In this paper, we present a probabilistic analysis of iterative node-based
verification-based (NB-VB) recovery algorithms over irregular graphs in the
context of compressed sensing. Verification-based algorithms are particularly
interesting due to their low complexity (linear in the signal dimension $n$).
The analysis predicts the average fraction of unverified signal elements at
each iteration $\ell$ where the average is taken over the ensembles of input
signals and sensing matrices. The analysis is asymptotic ($n \rightarrow
\infty$) and is similar in nature to the well-known density evolution technique
commonly used to analyze iterative decoding algorithms. Compared to the
existing technique for the analysis of NB-VB algorithms, which is based on
numerically solving a large system of coupled differential equations, the
proposed method is much simpler and more accurate. This allows us to design
irregular sensing graphs for such recovery algorithms. The designed irregular
graphs outperform the corresponding regular graphs substantially. For example,
for the same recovery complexity per iteration, we design irregular graphs that
can recover up to about 40% more non-zero signal elements compared to the
regular graphs. Simulation results are also provided which demonstrate that the
proposed asymptotic analysis matches the performance of recovery algorithms for
large but finite values of $n$.
