Node-based Verification-based Recovery Algorithms In

Transcript

N o d e-B a sed V erification-B ased R ecovery A lgorith m s in C om pressed Sensing: A sy m p to tic A n alysis and D esign o f Irregular Sensing M atrices (G raphs) by Y aser E ftek hari R o o zb eh a n i, M .S c. A dissertation subm itted to the Faculty of G raduate Studies and Research in partial fulfillment of the requirements for the degree of D o c to r o f P h ilo so p h y in E lectrical an d C om p u ter E n g in eerin g O ttaw a-Carleton Institute for Electrical and Com puter Engineering D epartm ent of Systems and C om puter Engineering Carleton University Ottawa, O ntario September, 2012 © Copyright Yaser Eftekhari Roozbehani, 2012 1+1 Library and Archives Canada Bibliotheque et Archives Canada Published Heritage Branch Direction du Patrimoine de I'edition 395 Wellington Street Ottawa ON K1A0N4 Canada 395, rue Wellington Ottawa ON K1A 0N4 Canada Your file Votre reference ISBN: 978-0-494-93677-1 Our file Notre reference ISBN: 978-0-494-93677-1 NOTICE: AVIS: The author has granted a non­ exclusive license allowing Library and Archives Canada to reproduce, publish, archive, preserve, conserve, communicate to the public by telecommunication or on the Internet, loan, distrbute and sell theses worldwide, for commercial or non­ commercial purposes, in microform, paper, electronic and/or any other formats. L'auteur a accorde une licence non exclusive permettant a la Bibliotheque et Archives Canada de reproduire, publier, archiver, sauvegarder, conserver, transmettre au public par telecommunication ou par I'lnternet, preter, distribuer et vendre des theses partout dans le monde, a des fins commerciales ou autres, sur support microforme, papier, electronique et/ou autres formats. The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. L'auteur conserve la propriete du droit d'auteur et des droits moraux qui protege cette these. Ni la these ni des extraits substantiels de celle-ci ne doivent etre imprimes ou autrement reproduits sans son autorisation. In compliance with the Canadian Privacy Act some supporting forms may have been removed from this thesis. Conform em ent a la loi canadienne sur la protection de la vie privee, quelques formulaires secondaires ont ete enleves de cette these. W hile these forms may be included in the document page count, their removal does not represent any loss of content from the thesis. Bien que ces formulaires aient inclus dans la pagination, il n'y aura aucun contenu manquant. Canada The undersigned hereby recommends to the Faculty of G raduate Studies and Research acceptance of the dissertation N o d e-B a sed V erification -B ased R eco v ery A lg o rith m s in C om p ressed Sensing: A sy m p to tic A n a ly sis and D esig n o f Irregular S en sin g M atrices (G raphs) subm itted by Y aser E ftek hari R o o zb eh a n i, M .S c. in partial fulfillment of the requirem ents for the degree of D o c to r o f P h ilo so p h y in E lectrical an d C om p u ter E n g in eerin g Professor Amir H. Banihashemi, Thesis Supervisor Professor Ioannis Lambadaris, Thesis Co-supervisor Professor Richard Baraniuk, External Examiner Professor Howard Schwartz, Chair, D epartm ent of Systems and C om puter Engineering O ttaw a-Carleton Institute for Electrical and Com puter Engineering D epartm ent of Systems and Com puter Engineering Carleton University September, 2012 A b stra ct In this thesis, we study the asym ptotic behavior of iterative node-based verificationbased (NB-VB) recovery algorithm s over random sparse matrices in the context of compressed sensing. Such algorithm s are particularly interesting due to their low complexity (linear in th e signal dimension n). Let a , here referred to as density factor, be the probability th a t a signal element is non-zero. It is known th a t there exists a success threshold on the density factor, before which the recovery algorithm s are successful, and beyond which they fail with probability one. We propose a m athem atical framework th a t predicts th e average fraction of unver­ ified signal elements at each iteration £ in the asym ptotic regime, where the average is taken over th e ensembles of input signals and sensing matrices as a function of £ as n —>■oo. The asym ptotic analysis is similar in nature to the well-known density evolution technique commonly used to analyze iterative decoding algorithms. To per­ form the analysis, a message-passing interpretation of NB-VB algorithm s is provided. This interpretation lacks the extrinsic nature of standard message-passing algorithm s to which density evolution is usually applied. This requires a num ber of non-trivial modifications in the analysis. We first discuss th e analysis of recovery algorithm s of interest over random regular sensing graphs. Later we generalize the analysis to include random irregular sensing graphs as well. We also discuss concentration re­ sults th a t ensure the performance of the recovery algorithm s applied to any choice of th e input signal over any realization of the sensing m atrix follows the determ inistic results of the analysis closely. We also dem onstrate th a t the proposed asym ptotic analysis m atches the perfor­ mance of recovery algorithms for large b u t finite values of n. Com pared to the sole existing technique for the analysis of NB-VB algorithms, which is based on num eri­ cally solving a large system of coupled differential equations, the proposed analysis is simpler to implement and more accurate. Moreover, we use the proposed analysis in an optim ization loop in order to design irregular sensing m atrices (graphs) th a t outperform previously reported results. The maximum density factor th a t designed irregular graphs can handle exceeds th a t of the regular graphs substantially. I dedicate this dissertation to my wonderful family. Particularly to my understanding and patient wife, Tara, who has given me her fullest support during all these years of research. T able o f C on ten ts A b s tra c t. iii T a b le o f C o n te n ts v L is t o f T a b le s viii L ist o f F ig u re s x N o m e n c la tu r e xii 1 I n tr o d u c tio n 1.1 M o tiv atio n............................................................................................................ 1.2 Basic Notations and D e fin itio n s .................................................................... 1.3 Previous W o r k s .................................................................................................. 1.4 O ur Contributions ............................................................................................ 1.5 Organization of the T h e s i s .............................................................................. 1 1 1 2 5 B i p a r t i t e G r a p h s a n d R e c o v e ry A lg o rith m s 2.1 In tro d u c tio n ......................................................................................................... 2.2 B ipartite Graphs and Tnput Signal ............................................................. 2.3 Verification Based Algorithms and Verification R u l e s .............................. 2.4 False V e rific a tio n ............................................................................................... 8 8 8 10 12 3 V B R e c o v e ry A lg o rith m s as M e ss a g e -P a s sin g A lg o rith m s 3.1 In tro d u c tio n ......................................................................................................... 3.2 Definitions and S e tu p ........................................................................................ 3.3 Message-Passing Description of RecoveryA lg o r ith m s .............................. 3.4 A Short Note on False Verification ............................................................. 14 14 15 18 20 4 A n a ly s is o f N B -V B A lg o r ith m s o v er R e g u la r G r a p h s 4.1 B a c k g ro u n d ......................................................................................................... 4.2 Concentration Results and Convergence to Cycle-Free C a s e .................... 4.3 Analysis of the G e n ie ........................................................................................ 4.4 Framework for t he Analysis of X I I ................................................................. 21 21 22 23 25 2 v 6 4.3 4.6 4.7 4.8 5 6 7 General Framework for the Analysis of LM and SBB ....................... 30 Update: Equations for LM and SBB A lg o r ith m s .......................... Koisy M e a s u re m e n ts ............................................................................. 30 Simulation R e s u l t s ................................................................................ 35 A n a ly sis o f N B -V B A lg o rith m s o v e r I r r e g u la r G r a p h s 3.1 In tro d u c tio n ............................................................................................. 5.2 Asymptotic Analysis F ram ew ork........................................................ 5.3 U pdate Rules for the' SBB A lg o r ith m .............................................. 5.4 Simulation R e s u l t s ................................................................................ 26 48 48 48 51 51 D e sig n o f I r r e g u la r G r a p h s 6.1 In tro d u c tio n ............................................................................................. 58 6.2 Optim ization .................................................................................................... 59 6.3 Running Time and Com putational C om plexity .............................. 6.4 Simulation Results and D is c u ss io n s................................................. 59 58 C o n c lu s io n a n d F u tu r e W o rk 7.1 C o n clu sio n ................................................................................................ 7.2 Future W o rk ............................................................................................. 65 58 65 65 L ist o f R e fe re n c e s 67 A p p e n d ix A A n a ly sis o f N B -V B A lg o r ith m s for R e g u la r G r a p h s A.l A ssu m p tio n s............................................................................................. A.2 G e n ie .......................................................................................................... A.3 X I I .............................................................................................................. A.4 L M .............................................................................................................. A.5 S B B .......................................................................................................... 72 72 73 76 78 83 A p p e n d ix B A n a ly sis o f S B B o v er I r r e g u la r G r a p h s 94 B.l Iteration Z e r o .......................................................................................... B.2 Iterat ion One, III-HR1 (Regrouping cheek nodes insets A /i j( d c) based on the index j ) ....................................................................................... 96 B.3 Iteration One, R1-HR2 (Verification of variable nodes based on ECN and D I C K ) .............................................................................................. 97 B.4 Iteration One. R 2-IIR 1 (Regrouping cheek nodes insets A f i j ( d c) based on t he index i) ................................................................................................. B.5 Iteration One, R2-HR2 (Verification of variable nodes based on ZCN) B .6 Iteration Two. Ill-IIR l (Regrouping cheek nodes in sets A f i j ( d c) based on the index j ) ............................................................................. 103 B.7 Iteration Two, R 1-HR 2 (Verification of variable nodes based on ECN and DICK) ..................................................................................................... vi 94 100 102 104 B .8 Iteration Two. R2-IIR1 (Regrouping cheek nodes in set based on the index i ) ........................................................................................ 107 B.9 Iteration Two, R2-HR.2 (Verification of variable nodes based on ZCN) 110 B.10 Iterations Thre(' and B e y o n d .......................................................................... 110 vii L ist o f T ables 2.1 4.1 4.2 4.3 4.4 1.5 4.6 4.7 4.8 4.9 4.10 4.11 4.12 4.13 4.14 4.15 4.10 5.1 Verification rules adopted in each VB a lg o r ith m ...................................... Probabilities Involved in tin' Analysis of Genie in Table 4.2. Each Entry of the Table is the Probability of the Corresponding Event . . . Density Evolution Analysis of G e n ie .................................................. 26 Density Evolution Analysis of X I I ...................................................... 27 Sets th a t are affected in each half-round of each round a t any iteration of LM and S B B ................................................................................................. Sets Involved in the Analysis of LM and SBB Algorithms ( t > 2) . . Probabilities that Appear in the Update Equations of LM and SBB Algorithms for > 2 (in Addition to the Probabilities of the Set* Described in Table 4.5). Each Entry of the Table is the Probability of the Corresponding Event................................................................................... Density Evolution Analysis of LM - Initialization .................................. Density Evolution Analysis of LM - Recursive Formulas for d > 2 . . 35 Density Evolution Analysis of SBB - In itia liz a tio n ........................ Density Evolution Analysis of SBB - Recursive Formulas forRound 1 . ( > 2 ..................................................................................................................... Density Evolution Analysis of SBB - Recursive Formulas for Round 2. f > 2 ..................................................................................................................... Success Thresholds for different graphs and a lg o r ith m s ......................... Success Thresholds for different graphs and algorithms for fixed com­ passion ratio rc = 0.5 Num ber of iterations required for different recovery algorithm s over different graphs to recover a signal with density ratio equal to the success threshold minus 0.0001 ....................................................................... Num ber of iterations required for different recovery algorithm s over different graphs with fixed compression ratio rc = 0.5, to recover a signal with density ratio equal to the success threshold minus 0.0001 . Success threshold and running time of the analysis of [1] for SBB over a random (3, 6 ) regular graph.......................................................................... Sets th at change in each half-round of each round at any iteration, assuming a variable node of degree dv and a cheek node of degree dc. The degrees dv and dc can be any valid degree according to the distributions A(./;) and p (x ).............................................................................. viii 12 25 28 31 32 33 34 36 37 41 42 43 43 47 50 5.2 Initialization of Param eters for the Analysis of SBB on Irregular G raphs with Inputs: A(.r). p(.r). (V0) 5.3 Recursive Formulas for the Analysis of SBB over Irregular G raphs for f > 2 . First R o u n d ........................................................................................... 5.4 Recursive Formulas for the Analysis of SBB over Irn'gular G raphs for f > 2 . Second R o u n d ........................................................................................ (i.l Two Optimized Degree D istributions with Success Thresholds Higher than 0.3025. The Degree D istributions Yield a Compression Ratio of 0.5............................................................................................................................ 6.2 Number of iterat ions f* for the SBB algorithm over different graphs and different initial density factors cA0). The first column represents the initial density factor, while each row represents the num ber of iterations for various graphs of interest......................................................... 6.3 Optimized Degree Distributions for Compression Ratios (rc) 1/3 and 3 / 4 ......................................................................................................................... 6.4 Optim ized Degree D istributions for Right-Regular Graphs with Aver­ age Variable Degree 4 and 5 and Check Degrees 5. 6 . 7 and 8 . a ) and a*H denote the success threshold for the designed graph and the (dv,d c) regular graph, respectively................................................................................ 6.5 Optimized Degree Distributions for Low Compression Ratios (?y) . . ix 55 56 57 60 61 62 63 64 List o f F igu res 2.1 3.1 3.2 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10 A regular bipartite graph with variable nodes on the left, eheek nodes on the right, variable node degree dv and eheek node degree tlc. Cheek nodes are represented by the sum m ation symbol indieating th at the value of a eheek node is a linear combination of the values of variable nodes connected to it................................................................................ 10 Message-Passing in I1R1 of a typical r o u n d ....................................... 17 Message-Passing in 1IR2 of a typical r o u n d ....................................... 17 Each check node in the set has i connections to the variable nodes in set /C and j connections to the variable nodes in set A .............. 28 The Difference in the Definition of AC, in LM vs. SBB..................... 29 Comparison between SBB. G m inim ization, and modified G minimiza­ tion in term s of MS reconstruction error in the presence of G aus­ sian measurement noise with zero mean and variance o 1 = 0.25 38 (n = 1000, in = 500).................................................................................. Comparison between success ratios of G ; weighted G and SBB (continuous-input/binary-sensing coefficients and binaryinput/continuous-sensing coefficients) for n = 1000, m = 500........ 40 Comparison between the average running times of G, weighted G and SBB for n = 1000. m = 500..................................................................... 40 Success ratio of Genie. XII, LM and SBB algorithms vs. a = for (5,0) graphs with n = {3, 15, 100 and 1000} x It)'1. Analytical thresholds arc; shown by arrows.............................................................. 41 Success threshold vs. compression ratio for LM. XT1, SBB, and Genie algorithm s.................................................................................................... 42 Evolution of vs. iteration number ( for the four recovery algorithm s over a (5,6) graph (finite-length simulations are for n = I05) ........ 44 Evolution of vs. iteration number for SBB over a (5,6) random graph (finite-length simulations are for n = H)4, HP, and 1()6) ...... 45 Fraction of unrecoverable variable nodes vs. the initial density factor for different recovery algorithms over random (5,6) regular b ip artite graphs. The arrows represent the theoretical success thresholds. The straight line represents the function f ( x ) = ./'.................................... 45 x 4.11 Success ratio of SUB vs. a = for graphs wit h n = 10° and (dv.d c) equal to (3.40). (4. 40) and (3 . 4 5 ). Theoretical success thresholds art' shown bv vortical dashed linos......................................................................... 5 .1 Evolution of for the SBB algorithm, obtained by finite-length sim­ ulation. vs. iteration number The evolution is reported for different initial density factors.......................................................................................... 5.2 Evolution of a^K obtained by the theoretical analysis, vs. iteration num ber t (dashed line) and th at of the normalized average unverified non-zero variable nodes vs. /; for n — 1()5 (solid line)................................ 5.3 Verifying the success threshold of SBB for irregular graphs through finite-length sim ulations..................................................................................... A.l A variable node in /Co moves to AC,-................................................................ A.2 Relationship between the sets 1 < / < ]. This simple observation is the key factor in many compression algorithms based on transform coding. In these schemes, a signal is represented in the dom ain in which it has many negligible coefficients. The few large transform coefficients are coded along w ith their location in the transform . This whole process of calculating all transform coefficients and then throw ing away a large quantity of them is very wasteful. In certain applications we can not afford to acquire a vast number of m easurem ents and throw most of them away. The reason could be th a t the number of sensors present is limited, or sampling (sensing) the signal is time consuming, costly or slow. Imaging based on neutron scattering and Magnetic Resonance Imaging (MRI) are considered examples of costly and slow sensing processes, respectively [’A], In these cases, a logical question to ask then would be: is it possible to sense the original signal in an already compressed fashion? As we will see in the sequel, compressed sensing (CS) answers this question in affirmative. 1.2 B asic N o ta tio n s and D efin ition s Compressed sensing was introduced with the idea to represent a signal v E Kn with n, and yet to be able to recover back the original signal v [1,~>]. In th e measuring process, also referred to as encoding , signal elements are m apped to measurements through a linear transform ation represented by the m atrix multiplication c = G v , where th e m atrix G E Mmxn is referred to as the sensing m atrix. This linear m apping can also be characterized by a bipartite graph referred to as the sensing graph. k non-zero elements with measurements c E Mm, where k < m 1 C H A P T E R 1. IN T R O D U C T IO N 2 In the recovery process, also referred to as decoding, based on the knowledge of the measurements and the sensing m atrix, we estim ate the original signal. The decoding process is successful if v is estim ated correctly. Three performance measures namely, density ratio 7 = k /n , compression ratio r c = m /n , and oversampling ratio ra = rn /k are used in order to measure and compare the perform ance of the recovery algorithm s in the context of compressed sensing. For successful decoding clearly we need ra > 1 . It is desirable to have this param e­ ter as small as possible. Indeed, in [(>] the authors proved th a t for sparse signals and in noiseless scenarios ra = 1 is achievable in the asym ptotic case (n —> 0 0 ). This means th a t the highest density ratio th a t an algorithm can possibly handle is 7 * = r c. Au­ thors in [7] have shown th a t if the sensing m atrix consists of i.i.d. Gaussian elements, then a decoder based on the £0 norm can recover the original signal with m = k + \ measurements; i.e., r 0 « 1. To find the solution based on the £0 recovery, however, one has to perform an exhaustive search, which is com putationally too complex [s], 1.3 P reviou s W orks The sensing m atrix in compressed sensing can be either dense or sparse. A sensing m atrix is considered dense if it has few, or none, zero entries. Sparse m atrices, on th e other hand, have few non-zero entries in each row and column. One m ajor difference between these two types of matrices is the encoding complexity associated w ith each class. For sparse matrices, the num ber of operations needed to calculate the measurements is considerably lower th an the one needed for dense matrices. Decoding algorithm s can be classified based on the class of sensing m atrix they use. The decoding algorithms in each class have certain properties in common. (For a comprehensive study on the topic, we refer the interested readers to [?)].) Decoding algorithm s associated w ith dense m atrices have, generally, high complexity (between 0 ( n 2) and 0 ( n 3)) compared to the lower complexity of algorithms utilizing sparse m atrices (between 0 (n ) and 0 ( n 2)). To have a b etter feeling about the complexity and running tim e of these two classes of algorithms, we have included in Fig. 4.5 of Section 4.8 th e comparison between two standard recovery algorithm s for dense m atrices (£1 minimization and weighted £\ minimization) and one algorithm (SBB) for sparse matrices. As can be seen, the decoding algorithm for sparse m atrices is faster by about two orders of m agnitude. Decoding algorithms for dense m atrices are mostly based on linear or convex program ming [1,5, 10, 11], T he reason is th a t random dense matrices satisfy restricted isom etry property (RIP) w ith overwhelming probability [ 12, 14]. The R IP was introduced by Candes and Tao in [l 1] as the main restriction on the sensing m atrix so th a t the recovery based on linear program m ing will be able to successfully recover the signal. Sparse matrices, on the other hand, do not satisfy R IP unless m = Q (k2) [ I-4].1 In fact, many of the decoders based on 1Authors in ['>] extended the definition of RIP and showed that sparse matrices satisfy a gener­ alized RIP constraint. The generalized RIP suffices for the linear programming decoders to succeed C H A P T E R 1. IN T R O D U C T IO N 3 sparse sensing matrices are iterative [ I , - ’, lb -2 7 ]. Although more com putationally complex, decoding algorithms for dense matrices tend to recover signals with larger num ber of non-zero elements (higher density ratio) compared to decoders for sparse matrices. Nevertheless, the high complexity of decoding algorithm s on dense m atrices hinders their application to high-dimensional signal recovery (signals w ith large n). In such cases, using sparse sensing graphs is clearly beneficial. Moreover, in certain compressed sensing applications such as com puter networks [25,2'V-n], channel coding [II], spectrum sensing [31)], and identification of linear operators [31], th e nature of the problem results in a formulation with a sparse sensing graph. Focusing on recovery algorithms based on sparse matrices (or sparse graphs), we can further divide them into two m ajor groups. In one group, we have algorithm s th a t use group testing and similar techniques from estim ation theory [ l b - 1!)]. These are referred to as combinatorial algorithms. In the other group, recovery algorithm s work w ith the b ipartite graph associated with the sensing m atrix by passing messages over the edges of th e graph [ 1 , 2 , 2 0 - 2 7 , 3 2 , 3 3 ] . These are referred to as messagepassing algorithms. Combinatorial algorithms, generally, assume th a t the decoder knows the param eter k [ l b - 10]. These algorithms, have two m ain steps. In th e first step, the algorithm outputs an estim ate which has more non-zero values th an the original signal. In the next step, knowing the param eter k , the estim ate is pruned so th a t it has the same number of non-zero elements as the original signal (i.e., k non-zero elements). Combinatorial algorithms are, in general, more com putationally complex th an message-passing algorithms. For example, the algorithm introduced in [lb] has complexity 0(A;2polylog(n)), which translates to 0 ( n 2polylog(n)) in the regime where k scales linearly with n. Message-passing algorithms, on the other hand, have com putational complexity 0 (n ). For the reasons discussed above, we are interested in low-complexity recovery algorithm s th a t exploit the sparsity of the sensing m atrix. In particular, we are in­ terested in message-passing recovery algorithms. In [32,33], the authors proposed and analyzed a belief propagation (BP) algorithm to recover the non-zero elements of the signal for the scenario where the location of such elements is known in the asym ptotic regime. It was shown in [3 I] th a t if each signal element contributes to infinitely many measurements (subject to certain criteria), then the B P algorithm is asym ptotically optim al in the case of sparse noisy measurements. In [23], the authors proposed a simple message-passing algorithm to reconstruct non-negative signals. This algorithm assumes lower and upper bounds for the values of the signal elements. It then shrinks th e difference between the two bounds through iterations. An anal­ ysis for the same algorithm th a t yields uniform guarantee on signal reconstruction was then provided in [21]. Another approach in message-passing algorithm s is to assume a prior distribution for the values of the signal elements and try to m axi­ mize the a-posteriori distribution of the values of the elements based on the observed in recovering sparse signals. However, the resulting bound on the reconstruction error is weaker compared to the case where the sensing matrix satisfies the original RIP condition. C H A P T E R 1. IN T R O D U C T IO N 4 measurements. In [27], the authors assumed Gaussian m ixture priors. The main problem associated with this approach is th a t the length of the messages passed over th e edges of the graph grows exponentially fast with th e number of iterations. In another work [2 ii], the authors assumed Jeffreys’ priors [d~>] and aimed at recovering th e non-zero elements of the original signal using message-passing algorithms. Then, they applied well-known least-square algorithms, such as LSQR [.'!(>], to estim ate the value of the non-zero signal elements. Moreover, in [2 (i], it was assumed th a t the param eter k is known. In a more recent work, authors in [.'57] applied the approxi­ m ate message-passing (AMP) algorithm proposed in [2 *] for dense sensing matrices to band-diagonal (sparse) matrices. In their approach, th e authors assume th a t the recovery algorithm has access to the distribution of non-zero elements of the signal. Algorithms discussed so far are either restrictive, in the sense th a t they assume some knowledge about the set of non-zero elements of the signal at the decoder, or have a high com putational complexity th a t makes them impractical in applications with large n. In the sequel, we are interested in a sub-class of message-passing algorithm s called Verification-Based (VB) algorithms. An instance of VB algorithm s was first intro­ duced for compressed sensing in [JO] . Later, [J'J, J->] observed th a t this algorithm is essentially identical to th e earlier idea of verification decoding from [•>! )]. This observa­ tion allowed a rigorous analysis of the VB reconstruction for compressed sensing. The class of VB algorithms has certain properties th a t make it perhaps one of the most interesting classes of recovery algorithms in compressed sensing. T he VB algorithm s recover signal elements in iterations. W hen an element is verified, its value is kept unchanged in future iterations. The algorithms in this class have decoding complex­ ity 0 ( n ), which makes them suitable for applications involving recovery of signals w ith large n. Moreover, these algorithm s operate on sparse sensing graphs, which translates to less com putations in the encoding process. Another m ain advantage of VB algorithm s is th a t they are not sensitive to the distribution of non-zero elements of the sensing m atrix as well as the distribution of non-zero elements of the signal, if certain conditions are satisfied. We will elaborate on this topic further in Section 2.4. These properties make the VB algorithm s a suitable choice for low-complexity recovery of sparse signals. The VB algorithms are, however, sensitive to th e presence of noise in the measured data. One can always argue that: i) the noise-free analysis of recovery algorithm s could serve as an upper bound for th e performance of the noisy versions, and ii) noiseless compressed sensing has applications in com puter networks as shown in [27, 2 !)]. Nevertheless, we will comment on using standard thresholding techniques to deal with noisy measurements in Section 4.7. This technique is very effective in th e high signal to noise ratio (SNR) regime (such as th e scenario in [2 >]). An in-depth analysis of the approach, however, is beyond the scope of this thesis. A nother interesting feature of VB algorithms is th a t their perform ance can be analyzed in the asym ptotic case (n —» oo). Assume a probabilistic input model, in which a signal element is non-zero (and takes a value from a certain distribution) with probability a and is zero with probability 1 —a. In the sequel, we refer to param eter C H A P T E R 1. IN T R O D U C T IO N 5 a as th e density factor. Furtherm ore, let denote th e probability th a t a signal element is non-zero and unverified before iteration t over the ensemble of all sensing graphs and inputs of interest. So, = a . If lim ^ o o a ^ = 0, then the algorithm is called successful for the initial density factor a .2 On the other hand, if there exists e > 0 , such th a t lim ^oo > e, then the algorithm is said to fail for the initial density factor a. A uthors in [ 1, 2 J , J I,.SO- 12] have shown th a t for each VB recovery algorithm in the asym ptotic regime as n -> oo and oo, a limiting value exists for a, before which the recovery algorithm is successful and beyond which it is not. We refer to this limit as the success threshold. T he success threshold serves as an asym ptotic m easure of perform ance for VB algorithms. It can also be used to estim ate th e perform ance of these algorithm s for finite b u t large values of n. To this end, researchers have analyzed VB algorithm s in the asym ptotic regime (n —> oo, £ —» oo) in order to find the success threshold associated w ith each VB algorithm. There are two categories of VB algorithms: node-based (N B) and message-based (M B) [I]. The two categories yield different success thresholds and are analyzed using different techniques. Algorithms considered in [22 ,.Tl] are of MB type, while the authors in [I] considered the NB type recovery algorithms. In general, NB algorithms have higher success thresholds and are harder to analyze. We elaborate on th e differences between the two categories and their corresponding analytical tools in Section 2.3. T he focus of this work is on th e analysis of NB algorithms. The analysis of NB-VB algorithm s discussed in [ I] results in a system of coupled differential equations. Due to the lack of closed form solution for th e resulting differ­ ential equations, the authors used numerical m ethods to approxim ate the asym ptotic results. Since th e analysis is only valid for n —> oo, one has to choose very large n for the numerical approximation. This translates to long running tim e and high com putational complexity. The other challenge is th a t numerical errors can affect the accuracy of the results, making it hard to evaluate how close the success threshold reported by this analysis (even for large values of n) is to the real success thresh­ old. In comparison, the analysis proposed in this thesis lends itself to closed form u p d ate equations consisting of only simple operations (addition/subtraction and mul­ tiplication/division). As a result, th e analysis is faster and, more im portantly, more accurate. 1.4 Our C ontributions One of the main goals of this work is to develop a simple and accurate framework for th e asym ptotic analysis (as n —> oo, I —» oo) of NB-VB algorithm s over sparse random sensing graphs and extend it to include recovery algorithm s of sim ilar nature such as th a t of [2], In our analysis, we assume th a t the m easurem ents are noiseless. 2It is easy to prove that the probability of a zero-valued signal element being unverified at iteration i is upper bounded by dCl ° < J(^ . Hence, when a^,:> tends to zero, this probability also tends to zero. C H A P T E R 1. IN T R O D U C T IO N 6 We dem onstrate th a t th e recovery algorithm s can be described by a first order timevarying Markov chain. We thus track the distribution of the states of this Markov chain as well as th e transition probabilities between different states through iterations in th e analysis. We refer to the analysis as density evolution, a terminology used for the analysis of iterative message-passing algorithms of low-density parity-check (LDPC) codes [ I•’>]. We however note th a t the analysis presented here fundam entally differs from th e conventional density evolution where the message passing is extrinsic [ K’]. The com putational complexity of the proposed analysis increases linearly with the num ber of iterations. The calculation of transition probabilities includes simple m athem atical operations, more specifically addition and m ultiplication, as opposed to solving complex systems of coupled differential equations, as is the case in [I], To be more precise, in [I], the variables involved in the equations are th e expected values of certain random variables, such as the normalized number of edges of certain type. These random variables determ ine the statu s of the decoder. In our analysis, we calculate the probabilities of events involving similar or related random variables, an d /o r their densities. As part of our asym ptotic analysis, we also discuss concentration results which certify th a t the performance of a recovery algorithm for a random choice of the input signal and th e sensing m atrix is very close to w hat is predicted by the density evolution results at the lim it of n —>oo. Using the proposed analysis, we can determ ine the distribution of the decoder states at any desired iteration. By tracking the distribution of th e decoder states with iterations, we then find the success threshold of different NB-VB algorithms. The analysis is presented first for random regular sensing graphs and then generalized to include random irregular graphs as well. Moreover, using the proposed density evolution analysis, we perform a comprehensive study and comparison of performance of different VB recovery algorithms over a variety of sparse graphs. We also use the analysis for irregular graphs as the core in an optim ization setup to study and find optim al sensing graphs under certain constraints such as fixed compression ratio and fixed maximum degrees in the sensing graph. Our simulations show th a t th e behavior of VB algorithms, when applied to signals with large lengths (in the order of 105), are in good agreement with the asym ptotic analytical results. They also dem onstrate th a t th e success threshold associated w ith irregular graphs can be substantially higher than the one for regular graphs. 1.5 O rganization o f th e T hesis The rest of the thesis is organized as follows. In C hapter 2, we introduce the class of bip artite graphs and input signals of interest in this thesis. We also provide a detailed description of VB algorithms along w ith the verification rules for each VB algorithm in this chapter. Also in this chapter, we discuss the im portant notion of false verification and its probability for VB algorithms. A message-passing interpretation C H A P T E R 1. IN T R O D U C T IO N 7 of the recovery algorithm s is presented in C hapter 4. T he analysis framework will be introduced in C hapters 4 and 5 for regular and irregular graphs, respectively. We propose a simple modification of VB algorithm s to deal with noisy m easurem ents in C hapter 4. Simulation results for regular and irregular graphs will be presented in Sections 4.8 and 5.4, respectively. In C hapter 6 , we will discuss the design of irregular graphs th a t are optim al under certain constraints. We conclude in C hapter 7 with some guidelines for further research. Appendices A and B are devoted to the derivation of the transition probabilities for the regular and irregular graphs, respectively. C hapter 2 B ip a r tite G raphs and R ecovery A lg o rith m s 2.1 In trod u ction As discussed in the previous chapter, the focus of this work is on sparse sensing graphs and probabilistic input signals. In this chapter, we describe regular and irregular bipartite graphs, their random construction and the model used for th e input signal. We then introduce the role of bipartite graphs in compressed sensing. Afterwards, we elaborate on verification-based algorithms, their history and their usage as recovery algorithm s in the context of compressed sensing. We will discuss th e verification rules employed by VB algorithms as well as false verification concept in VB algorithm s. 2.2 B ip a rtite G raphs and Input Signal A bipartite graph (or bigraph ) Q{ V U C, E ) is defined as a graph whose set of vertices V U C is divided into two disjoint sets V and C, so th a t every edge in the set of edges E connects a vertex in V to one in C. Consider a bigraph Q{V U C , E ) w ith | Vj = n and |Cj = m . Corresponding to each such graph, a biadjacency m a trix A (Q ) of size m x n i s formed as follows: the entry ai3 is 1 if there exists an edge £ E connecting the vertex c* £ C to the vertex Vj £ V; and is 0 , otherwise. In general, a bigraph can be irregular and weighted. In a bigraph, a node in V (C ) has degree i if it is neighbor (connected) to i nodes in C (V). Let A* £ M+ and Pi £ R + denote th e fraction of nodes in V and C with degree i, respectively. The polynomials X(x) = \ x l and p(x) = J T piX1 are referred to as degree distributions corresponding to nodes in V and C, respectively. Clearly, A(l) = p (l) = 1. For m athem atical convenience, we define dv := JV iXt and dc := Y ljJ P j and we refer to them as th e average variable degree and the average check degree, respectively. For given A(x), p(x) and n, let Qn(X(x), p(x)) (Qn(X, p) for short) denote the ensemble of all irregular bigraphs with degree distributions A(x) and p(x) and |Vj = n, |Cj = m = Tl/dyj d(.. 8 C H A P T E R 2. B IP A R T IT E G R A P H S A N D R E C O V E R Y A L G O R IT H M S 9 Biregular graphs (or regular bigraphs) are considered special cases of irregular bigraphs as follows. Let dv and dc be two positive integers. Consider a bigraph Q (V U C , E ) so th a t each vertex in V (C ) is incident to dv (dc) vertices in C (V). Clearly, ndv — m d c. We refer to this bigraph as an (n, dv, dc)-biregular graph. The biadjacenecy m atrix A( Q) associated to an (n, dvi dc)-biregular graph has dc non-zero entries in each row and dv non-zero entries in each column. For given param eters dv, dc and n (to = ndv/d c), let Gn{dv,d c) denote the ensemble of all (n, dv, dc)-biregular graphs. Moreover, a regular or irregular bipartite weighted graph (or weighted bigraph) G'{V U C, E , W ( E ) ) is a generalization of the bigraph G (V UC, E) in the sense th a t a weight W i j : = W (e^) G R \{0} is associated with each edge ei3 G E . The biadjacency m atrix A(G ') corresponding to the weighted bigraph Q' is acquired from the biadja­ cency m atrix A( G) of the underlying bigraph Q by replacing non-zero ai3 values in A{Q ) w ith Wi j . Let us assume an arbitrary, b u t fixed, labeling scheme for vertex sets V and C over the ensemble of graphs of interest. Further, let W be a m atrix of size m x n o f weights w drawn i.i.d. according to a distribution f ( w) , and W™Xn be the ensemble of all such matrices. Now for any bigraph Q {V U C , E) (g Gn {dv, dc) for biregular graphs and G Qn(X, p) for irregular bigraphs) and any weight m atrix W G W Jlxn, we form the corresponding weighted bigraph G'(V U C\ E , W ( E ) ) as follows. To every edge ei3 G E, 1 < i < ra, 1 < j < n, connecting ith vertex from C and j th vertex from V, we assign the weight W (e i3) = ; i.e., the weight in row i and column j of the weight m atrix W. Thus, we construct the ensemble of all (n, A, p)-weighted irregular bigraph, denoted by Gf ( \ , p) , by freely combining elements in Gn{ \,p ) and VV™Xn. Similarly, we construct the ensemble of all (n, dv, dc)-weighted biregular graphs, denoted by Gf ( dv, dc), by freely combining elements in Gn{dv, dc) and W Jlxn. Thus far, we have described the ensemble of graphs th a t are of interest in this work. In w hat follows, we describe the ensemble of inputs of interest. Let a G [0,1] be a fixed real num ber and v be a vector of length n with elements Vi drawn i.i.d. according to a probability distribution function defined as follows: the element is zero w ith probability 1 — a , or follows a distribution g with probability a (i.e., PVi{v) = ag(v) + (1 —a)5(u), where 5 is the Dirac delta function). We denote the ensemble of all such vectors by ( a ) .1 In compressed sensing, each measurement is a linear combination of the signal elements. W ith a slight abuse of notation, we use c* and V j for both the label and the value of the ith measurement and the j t h signal element, respectively. We denote by c and v, th e column vectors of the measurements cys (1 < i < ra), and the signal elements Vj's (1 < j < n), respectively. The underlying system of linear combinations can then be represented by the m atrix m ultiplication c = Gv . In the sequel, the 1It is worth noting that the expected fraction of non-zero elements in such a vector is a . Using the Chernoff bound, it can be shown that the actual fraction of non-zero elements in a randomly chosen vector from this ensemble is tightly concentrated around its expected value (a) with high probability. C H A P T E R 2. B IP A R T IT E G R A P H S A N D R E C O V E R Y A L G O R IT H M S 10 sensing m atrix G is the biadjacency m atrix of a weighted bigraph Q{V UC, E , W ( E ) ) draw n uniformly a t random from the ensemble of interest (biregular or irregular). Henceforth, we refer to the graph Q as the sensing graph. Moreover, the signal vector v is drawn uniformly at random from the ensemble Vg(a). The sets of signal elements and measurements are respectively m apped to th e vertex sets V and C (|U | = n, \C\ = m). The coefficient of the j th signal element (vj E V) in the linear com bination associated with th e ith measurement c* E C , the entry <7^ in G , is th e entry of the biadjacency m atrix A( Q) of Q. Figure 2.1 pictorially represents the relation between signal elements, measurements and the sensing graph. Tl m Variable Nodes Figure 2 . 1 : A regular bipartite graph with variable nodes on the left, check nodes on the right, variable node degree dv and check node degree dc. Check nodes are represented by th e sum m ation symbol indicating th a t the value of a check node is a linear combination of the values of variable nodes connected to it. In the context of coding, a linear code can be represented by a bigraph, where the two sets of nodes represent the code symbols, and the linear parity-check constraints th a t the symbols have to satisfy [II], Following the terminology frequently used in the context of coding, we refer to the sets V and C as th e variable nodes and check nodes, respectively. We will interchangeably use the term s variable nodes and signal elements as well as check nodes and measurements. 2.3 V erification B ased A lgorithm s and V erification R ules Luby and M itzenmacher [:i!i] proposed and analyzed two iterative algorithm s over bigraphs for packet-based error correction in the context of channel coding. In these algorithms, a variable node can be in one of the two states: “verified” or “unverified” . Under certain circumstances, a variable node is verified and a value is assigned to it. This node then contributes to the verification of other variable nodes. The decoding process continues until either the entire set of unverified variable nodes is verified, or th e process makes no further progress while there are still some unverified variables. C H A P T E R 2. B IP A R T IT E G R A P H S A N D R E C O V E R Y A L G O R IT H M S 11 Due to the verification nature of th e process, the two algorithm s in [:’>!»] are called verification-based (VB) algorithms. If the assigned value to a variable node at a certain iteration is different from its true value, a false verification has occurred. In Section 2.4, we discuss sufficient conditions for VB algorithms so th a t th e probability of false verification is zero. In w hat follows, we describe four recovery algorithms th at can be classified as VB algorithms. T he first algorithm, here referred to as “Genie” , is a benchm ark VB algorithm in which the support set of the signal is known a t the decoder. We use the Genie algorithm and its analysis to m otivate and explain the analytical framework. The success threshold associated with this algorithm serves as an upper bound for th e performance of other VB algorithm s .2 In other recovery algorithms, the decoder has no information about the support set. The next two decoders considered here, are the two m ain VB decoding algorithm s in th e context of compressed sensing. T he first algorithm is referred to as LM, to stand for Luby and M itzenmacher [ !!)]. The same algorithm is called LM l in [2 2 ], The second main VB algorithm is the algorithm introduced in [20], which is the same as the second algorithm discussed in [22 ]; LM2. We refer to this algorithm as SBB, for Sarvotham, Baron and Baraniuk. The algorithm in [2 ], here referred to as XH, for Xu and Hassibi, also falls into the category of VB algorithms, and can also be analyzed using the proposed framework. This algorithm serves as th e fourth and last VB algorithm considered in this thesis. In the VB algorithms, the check node values are initialized with th e measurements. W hen a variable node is verified a t an iteration, its verified value is subtracted from the value of its neighboring check nodes. The variable node, then, is removed from th e sensing bigraph along with all its adjacent edges. Hence, all the neighboring check nodes of the verified variable node face a reduction in their degree. In the next iteration, some variable nodes may be verified based on th e degree a n d /o r the value of their neighboring check nodes. The rules based on which the variable nodes are verified at each iteration are called verification rules and are as follows: • Zero Check Node (ZCN): If a check node has a zero value, all its neighboring variable nodes are verified w ith a zero value. • Degree One Check Node (D1CN): If a check node has degree 1 in a graph, its unique neighboring variable node is verified with th e value of th e check node. • Equal Check Nodes (ECN): Suppose we have N check nodes with the same non-zero value, then 1) all variable nodes neighboring a subset of these N check nodes (not all of them ) are verified with the value zero; 2 ) if there exists a unique variable node neighboring all N check nodes, then it is verified w ith the common value of th e check nodes. 2The Genie algorithm is essentially the same as the peeling algorithm over the erasure channel proposed in [!*>]. In particular, the two algorithms have the same threshold. C H A P T E R 2. B IP A R T IT E G R A P H S A N D R E C O V E R Y A L G O R IT H M S 12 Verification rules ZCN and ECN are responsible for verifying variable nodes not in the support set. Since, the Genie algorithm has the complete knowledge of the support set, it has no need to apply these two rules. Hence, D1CN is th e only rule used by th e Genie. O ther VB algorithms, each uses a combination of verification rules in order to verify and resolve unverified variable nodes. Assuming zero probability for false verification, the order in which the rules axe applied does not affect the overall performance of the algorithm; it will only change the order in which variable nodes are verified. Verification rules adopted by different algorithms are sum m arized in Table 2 . 1. Table 2.1: Verification rules adopted in each VB algorithm Genie ZCN D1CN ECN Not Needed / Not Needed LM / / X SBB / / / XH / X / Based on Table 2 . 1, SBB applies the union of all rules to verify variable nodes. Therefore, this algorithm is expected to have the highest success threshold amongst th e practical VB algorithms discussed here. This is verified in Section 4.8. The ECN rule as stated above can not be easily captured in the analysis. As indi­ cated in [10], the ECN rule can be modified to Modified Equal Check Nodes (MECN) as follows w ithout affecting th e asym ptotic behavior of th e recovery algorithms: Modified Equal Check Nodes (MECN): Suppose we have N check nodes w ith the same non-zero value. Then if there exists a unique variable node neighbor to all such check nodes, it is verified w ith the common value of the check nodes. In this case, all other variable nodes connected to those check nodes are verified as zero. 2.4 False V erification Let K denote th e set of non-zero variable nodes in the signal; the support set. Also, let V(c) denote the set of variable nodes neighbor to a check node c. Now, consider th e following facts: ( 1 ) Let C be an arbitrary subset of check nodes. If all the check nodes in C are neighbor to the same subset of nodes in 1C, then all these check nodes have the same value. ( 2 ) Any check node with no neighbor in K- has a zero value. C H A P T E R 2. B IP A R T IT E G R A P H S A N D R E C O V E R Y A L G O R IT H M S 13 Verification rules ZCN and ECN in VB algorithms are designed based on the following assumptions: (1') Let C' be any arbitrary subset of check nodes w ith the same value. T hen all these check nodes are neighbor to the same subset of 1C. (2') None of the variable nodes neighbor to a zero valued check node belongs to the set 1C. It is w orth noting th a t the assum ptions (1;) and (2') are the converses of the facts (1) and (2), respectively. To any choice of distributions / and g for non-zero weights of the sensing graph and non-zero signal elements, respectively, corresponds a certain probability th at the converses fail to hold. Those distributions which make the converses hold tru e with probability 1 (almost surely), are of interest in this thesis. In the following theorem, we give an example of distributions th at make the statem ents ( 1') and ( 2 ') hold true almost surely. T h e o r e m 1. Let q and Cj be two distinct check nodes and Vi and Vj be their corresponding set of neighboring variable nodes in 1C; i.e., Vi = V (q) D K and V, = V(c.j) fl 1C. Suppose that at least one o f the distributions f or g described before is continuous. Then the statem ents (V) and (21), described above, are correct with probability one fo r Ci and Cj. The continuity of / or g is a sufficient condition to have the probability of false verification equal to zero. A similar statem ent can be found in [20,22,23, 10, I i]. In th e rest of the thesis, we assume th a t the statem ents ( 1') and (2 ') are correct with probability one and consequently, the probability of false verification for a variable node in any iteration of the VB algorithm s is zero. Using the union bound, one can see th a t th e probability of false verification in any iteration and also in th e whole recovery algorithm is zero. C hapter 3 V B R ecovery A lg o rith m s as M essa g e-P a ssin g A lg o rith m s 3.1 Introd u ction T he verification process in VB algorithms can be seen as a message-passing procedure. In general, a variable node sends its current state (either verified or unverified) to its neighboring check nodes along with its value (if verified). A check node processes the received messages and subsequently sends some messages to its neighboring variable nodes. Each unverified variable node decides on its next state, either verified or unverified, based on the received messages from check nodes. The process of passing messages between variable nodes and check nodes continues until all variable nodes are verified, or no variable node changes its state. In message-passing algorithms, a node can take two approaches in order to produce a message based on the set of received messages. In the first approach, th e outgoing message is a function of all received messages. In this case, all messages leaving a node at a certain iteration are the same. In the second approach, the message passed from node a to node b in the bigraph, is a function of all the received messages by node a except the received message from node b. Therefore, the outgoing messages of a node at a certain iteration may be different, depending on the received messages. In the context of VB algorithms, the first approach is known as node-based (NB), while the second approach is called message-based (M B) [ I , - i ].1 So, for a NB-VB algorithm , the state of a variable node is reported identically by all its outgoing messages, while in an MB-VB algorithm, different states may be reported by different outgoing messages of a variable node. As noted in [I], th e authors in [;->?)] defined the two VB algorithms using th e NB representation b u t analyzed them using the MB representation. In [l], the authors proved th a t for one of the VB algorithms, the NB and MB versions perform the same, b ut for the other VB algorithm, the NB version outperforms the MB one. In 1In the context of iterative decoding algorithms, NB and MB approaches are known as nonextrinsic and extrinsic message-passing, respectively [ h i ] . 14 C H A P T E R 3. V B R E C O V E R Y A L G O R IT H M S A S M ESSA G E-PA SSIN G A L G O R IT H M S 15 compressed sensing, this implies th a t NB versions, in general, have higher success thresholds; i.e., can successfully recover signals w ith larger density factors [_’ !]. A well-known m ethod to analyze iterative message-passing algorithm s in coding theory is density evolution [ I I n density evolution, the distribution of messages is tracked with the iteration number. T he evolution of the message distributions w ith iterations will then reveal im portant properties of the decoding algorithm such as decoding threshold and convergence speed [!■!]. T he derivation of the message distribution however, requires the independence among the incoming messages to a node. T he analysis is thus only applicable to extrinsic message-passing algorithm s (MB decoders). To analyze NB algorithms, Zhang and Pfister [I] derived a system of coupled differential equations. For (dv, dc) regular bigraphs, the num ber of differential equations are 0 ( d v + d%) and 0(d% + d2c) for the LM1-NB and LM2-NB algorithm s, respectively. It is difficult, if not impossible, to find a closed form solution for the system of differential equations even for small values of dv and dc.2 Numerical m ethods were thus used in [ I] to solve the system of differential equations and consequently evaluate th e performance of NB algorithms. This process however is susceptible to numerical errors. In addition, it is hard to know how the obtained threshold for a given finite value of n compares with the exact threshold, which applies in the asym ptotic regime of n —> oo. In practice, the numerical results are highly dependent on th e selected, large but still finite, value of n. In our work, we analyze NB-VB algorithms in the regime where n —» oo. Our analysis has an iterative fashion, as will be clear in Chapters 4 and 5, w ith lowcomplexity update rules, which are far less complex than the one used in [ 1]. More­ over, our proposed analysis is applicable to parallel versions of th e algorithm s and leads to 0 { d v + d%) calculations per iteration. 3.2 D efin ition s and Setu p Each NB-VB algorithm works in iterations through exchanging messages between th e check nodes and the variable nodes along the edges in the graph. Any message sent from a variable node to its neighboring check nodes belongs to an alphabet set M. : {0,1} x R. The first coordinate of such a message is a statu s flag, sometimes referred to as “recovery flag” , taking binary values. The flag indicates th e verification statu s of th e variable node. If this flag is 0 , then the variable node is not verified. If, on th e other hand, the flag is 1, then the variable node has been verified. In this case, th e second coordinate, which is a real number, is interpreted as the verified value of th e variable node. Similarly, any message sent from a check node to all its neighboring variable nodes belongs to an alphabet set O : Z + x R . T he first coordinate of such a message indicates th e num ber of unverified variable nodes neighbor to the check node. The first coordinate is in fact the degree of the check node in the subgraph induced by 2The number of differential equations for LM1-NB over a (3,6) bigraph is 30. C H A P T E R 3. VB R E C O V E R Y A L G O R IT H M S A S M ESSA G E-PA SSIN G A L G O R IT H M S 16 th e unverified variable nodes. The second coordinate indicates th e current value of th e check node, i.e., the result of the linear combination of the unverified neighboring variable nodes. The edges, in NB-MP algorithms, do not simply forward messages from check nodes to variable nodes and vice versa. Instead, based on the traveling direction of th e message, edges multiply or divide the second coordinate of the message by their associated weight. More specifically, if the message is sent from a variable node to a check node, its second coordinate is multiplied by the weight. T he second coordinate of the message is divided by the weight, if the message is sent from a check node to a variable node. So, although messages generated by a node (either variable node or check node) are sent identically over all adjacent edges, the fact th a t the edges may have different weights will result in different messages being received a t the destination nodes. All such messages are independent if the weights associated with th e corresponding edges are independent. Any iteration I > 1 in NB-VB algorithms, consists of two rounds, denoted by R1 and R2, each with two half-rounds, denoted by HR1 and HR2. In the R1-HR1 and R2-HR1, every check node processes all its received messages from the previous round together w ith its associated measurement and sends out a message from the alphabet O to all its neighboring variable nodes. In the R1-HR2 and R2-HR2, each (unverified) variable node decides on its next state by processing all its received messages. W hatever the decision, th e variable node sends back a message, from the alphabet A4, to all its neighboring check nodes. So, a round starts w ith check nodes processing the received messages from neighboring variable nodes, proceeds w ith the transm ission of messages from check nodes to variable nodes, continues by variable nodes processing the received messages from neighboring check nodes, and ends with th e transm ission of messages from variable nodes to check nodes. T he two rounds in each iteration follow the same general structure. They only differ in the processing carried out in the variable nodes. In Figures 3.1 and 3.2, we have shown the snap shots of message passing between a variable node of degree 3 and a check node of degree 4. The snap shots represent th e two half-rounds (HRI and HR2) of a generic round of recovery. Let : O dv —> A4 and : O dv —>■ M , I e N, represent the m appings used at any unverified variable node of degree dv to m ap the incoming messages to th e outgoing message in the first and the second round of iteration t, respectively. Obviously, due to th e verification-based nature of the algorithms, when a variable node becomes verified at an iteration, its outgoing message rem ains unchanged, ir­ respective of its incoming messages. In contrast to the variable nodes, the m apping function used in check nodes is identical for both the first and th e second round of each iteration. Every check node has an associated received measurement; a random variable taking values in K. So, we use the notation : R x A4dc —» O, I 6 N, to denote the m apping function used in all check nodes of degree dc at iteration I. For C H A P T E R 3. V B R E C O V E R Y A L G O R IT H M S A S M ESSA G E-PA SSIN G A L G O R IT H M S 17 o e O (a) Variable Node to Check (b) Check Node Processing (c) Check Node to Variable Node Node Figure 3.1: Message-Passing in HR1 of a typical round o\ o ,e O o-l € O m € M. (a) Check Node to Variable (b) Variable Node Processing (c) Variable Node to Check Node Node Figure 3.2: Message-Passing in HR2 of a typical round the sake of completeness, let $1°^ = : O dv —»• M. and : M —> O represent the m appings used, respectively in all variable nodes of degree dv and all check nodes at iteration 0. This iteration consists of only one round. For the VB algorithm s under consideration, th e mapping functions in the variable nodes and check nodes are not a function of the iteration number. Therefore, we omit the superscript (I) henceforth. In w hat follows, we describe VB algorithm s of Section 2.3 as message-passing algorithm s with the general structure explained above .3 3It is worth mentioning that the message-passing description of SBB and XH algorithms (in particular, presented in Sections '■>:>.-I and 3.d. I, are only valid for the cases in which the non-zero weights of the sensing graph are drawn from an uncountable or countably infinite alphabet set. If the elements of the sensing matrix are drawn from a finite alphabet set, such as binary 0 and 1, the outgoing messages from a check node should also include the list of all unverified variable nodes neighbor to the check node. The mapping function in the variable nodes should also change in order to use the extra information in the incoming messages. Please also see Footnote 5 in Section ;s.:u. C H A P T E R 3. VB R E C O V E R Y A L G O R IT H M S A S M ESSAG E-PASSIN G A L G O R I T H M S 18 3.3 M essage-P assing D escrip tion o f R ecovery A l­ gorithm s To describe the four VB recovery algorithms using the message-passing approach, we need to define th e mappings and <3>c. M apping $1^ embeds the verification rules D1CN and ECN, while the mapping embeds the ZCN rule. To make the description of mappings „ and 1 , the mapping function at any check node c; (of degree dc) is as follows: $ c(c i,m i, • • • , m dc) dc dc i= 1 i= 1 = (dc - where, c, in th e above equation is the measurement associated w ith the check node q, and r r i i — (si,u>j) is the message received along the ith edge. The m apping functions are algorithm dependent and are discussed for each VB algorithm separately next. The decoder stops at an iteration £, £ > 1, if the algorithm makes no further progress, i.e., the set of verified variable nodes are the same for th e two consecutive iterations £ — 1 and £. Equivalently,the algorithm stops if the messages sent from variable nodes to check nodes, and also from check nodes to variable nodes, are the same for two consecutive iterations £ and £ — 1. At this point, if th e decoder is able to verify all the variable nodes, then the decoding is called successful. Otherwise, the decoder will declare a failure. 3.3.1 G en ie In this algorithm, each iteration consists of only one round, in which one verification rule (D lC N ) is applied to all variable nodes. For variable nodes not in the support set, the outgoing message in all iterations is fixed and equals m = ( 1 , 0 ). For any variable node (of degree dv) in the support set, the m apping C H A P T E R 3. V B R E C O V E R Y A L G O R IT H M S A S M ESSA G E-PA SSIN G A L G O R IT H M S ! 9 $ „ (o i, • • • , o dv) is defined based on the following rules. • Rule 1 : If among all received messages (from the neighboring check nodes), there exists only one message, say Oj,i £ [dc], such th at o* = (l,f» ),£ i ^ then $ „ (o j, • • • , o dv) = (l,£ i). In this case, the variable node is verified with the value £j. • Rule 2: If multiple messages exist in the form (1,£) (any £ £ M), then choose one at random , say Oj = (l,£ i),£ i £ R, and set $ „ ( o i,- -- , o ^ ) = (1,&). In this case, th e variable node is verified with th e value £t. • Rule 3: If none of th e above happens, then <&„(oi,--- , o ^ ) = (0,0). In this case, th e variable node is still unverified. For any unverified variable node, the mappings and are defined according to th e following sets of rules, for LM, SBB and XH, respectively. 3 .3 .2 LM • ^ ( o i , • • • , o dv): Apply Rules 1 - 3 of Genie. • $ [ 2)(o i,--- , o dv): — Rule 4: If there exists at least one message Oj such th a t o* = (di, 0) (for j / q\ any dj £ Z ), then (o i,--- , o dv) = (1,0). In this case, the variable node is verified w ith the value equal to 0 . — Rule 5: If no incoming message exists in the form (di, 0) (for any di £ Z +), /o'N then (o i,--* , o ^ ) = (0,0). In this case, the variable node is still unverified. 3 .3 .3 SBB • ^ ( O i , - - - , o dv):4 — Apply Rule 1 of Genie. — If there exist N messages (2 < N < dv) o {l = (d ° i N = (diN,€iN)i such th a t Cu = 62 = • *• = o i2 = (dja,£ia), • • •, then ^ ( o i , ■■■ ,o dv) = 4The original recovery algorithm introduced in [21 j] has a computational complexity of 0 ( m -log m) (which translates to 0 ( n ■logn) for biregular graphs of fixed degrees). It is easy to prove that the message-passing description provided here does not change the recovery capability of the algorithm but results in the reduction of decoding complexity from 0 ( n ■logn) to O(n). C H A P T E R 3. VB R E C O V E R Y A L G O R IT H M S A S M ESSA G E-PA SSIN G A L G O R IT H M S 20 ( lj& J . In this case, the variable node is verified with th e common value Sll- 5 — If a variable node is verified to different values according to verification rules above, then choose one at random and generate the outgoing message accordingly. — Apply Rule 3 of Genie. • i2^(oi, • • • , OdJ: Apply Rules 4 and 5 of LM. 3 .3 .4 • XH - ,o dJ : — If there exist M messages (\d v/2 \ < M < dv) o ix = ( d ^ , ^ ) , o i2 = (di2j ^12)5 jCim)> such th a t £t2 ••• then ^ ( o i , • • • ,Odv) = (1, & J. In this case, the variable node is verified with the common value — If a variable node is verified to different values according to the verification rule above, i.e., if two groups of messages both at least of size d „ /2 satisfy the above condition, then choose one a t random and generate th e outgoing message accordingly. — Apply Rule 3 of Genie. • $ l 2^(oi, • • • , Oav): Apply Rules 4 and 5 of LM. 3.4 A Short N o te on False V erification In th e above description of recovery algorithms, there may be cases where a variable node can be verified to different values by different rules. Using th e same assum ption m ade in Section 2.4, it is easy to see th a t the probability of this event is equal to zero. In such cases, wehave thus assumed th a t th e variable node is verified by one of th e rules selected randomly. Clearly, the probability of false verification as a result of such selections is zero. 5We note that the message received by the variable node equals the message sent from the check node divided by the weight of the connecting edge. Therefore, receiving N messages with the same value would imply that, almost surely, the unverified variable node under consideration is the unique non-zero variable node neighbor to the N check nodes. Other unverified variable nodes neighbor to these N check nodes do not belong to the support set and should be verified with a value equal to zero. This, however, happens in the next round. C hapter 4 A n aly sis o f N B -V B A lgorith m s over R egu lar G raphs 4.1 Background In this chapter, we first show th a t (i) the performance of a realization of th e sensing graph, w ith a certain selection of the edge weights for the recovery of a realization of th e input signal concentrates around the average performance of the ensemble (where the average is taken over all the elements in the ensemble G f(dv, dc) x V” (a), for given probability distribution functions / , g, and given constant param eters dv,d c and a), as n tends to infinity, and (ii) the average performance of the ensemble, as n goes to infinity, converges to the performance of the cycle-free case defined as follows. Let N%e be the neighborhood of node v of depth 2£, i.e., the subgraph consisting of th e variable node v and all those nodes th a t are connected to v with any path of length less th an or equal to 2£. We say th a t we are working under the cycle-free assum ption when for a fixed £, and for every v, AQe is tree-like .3 Following the concentration results, we first present th e asym ptotic analysis of the Genie algorithm .2 The analysis provides us with the average ensemble performance for th e asym ptotic case of n —>■ oo. We then generalize the concepts used in the analysis of Genie and analyze XH, LM and SBB algorithms. 1These concentration results were established as a joint work with Anoosheh Heidarzadeh, another Ph.D. student, and are presented here for the sake of completeness. The author has contributed in the derivation of the upper bound presented in Equation (1.1). 2An analysis of the Genie algorithm (peeling decoder) over the erasure channel is given in [ 11], Unlike the approach adopted in this work, the analysis of [ l ">] is based on modeling the progress of iterative decoding with a set of differential equations. 21 C H A P T E R 4. A N A L Y S IS OF N B -V B A L G O R IT H M S O V E R R E G U L A R GRAPHS22 4.2 C oncen tration R esu lts and C onvergence to C ycle-Free C ase Consider a weighted graph selected at random from G f(dv, dc). Also consider an input signal vector v chosen randomly from Vg(a). Suppose th a t a VB algorithm is applied to th e measurem ent vector c = Gv to recover v iteratively, where G is the biadjacency m atrix of the chosen weighted graph. For this scenario, let (3^ (:= fiW (G , w , v )) be th e fraction of unverified non-zero variable nodes at the beginning of iteration £, i.e., th e fraction of variable to check node messages passed along the edges of the chosen weighted graph w ith unverified statu s (sent by non-zero variable nodes); further, let E[/3^] denote the expected value of where the expectation is taken over the ensembles Gf{dv,d c) and V” (o;). Now, consider the corresponding cycle-free case, and let be th e expected num ber of messages with unverified statu s passed along an edge em anating from a non-zero variable node with a tree-like neighborhood of depth at least 2£ at the £th iteration. Here, again, the expectation is taken over the ensembles of input signals and weighted graphs. In the subsequent subsection, we will show how can be calculated. It should be clear th a t a ^ , being defined as th e “average” over the ensemble of weighted graphs and input vectors, is the same as th e “probability” th a t a message from a non-zero variable node w ith a tree-like neighborhood of depth at least 2£, at the £th iteration, carries an unverified status. In this section, we use the interpretation of as an average. The interpretation of as a probability will be used in the analysis section. In the following, we will show th a t over all realizations, with high probability, does not deviate much from E[/?(^], and E[/3^], itself, is not far from a ^ \ as n tends to infinity. T h eo rem 2. Over the probability space of all weighted graphs G f(dv, dc), and all signal inputs V g(a), fo r a fixed £, letting /3 ^ and be defined as above, fo r each o f the N B -V B algorithms discussed in this paper, there exist positive constants p{dv,d c,£) and 7 (dv, dc, £), such that (i) fo r any e > 0 , P r [|/3W - E [£ w ]| > e/2] < 2 e '£2n//i, (4.1) and (ii) fo r any e > 0 , and n > 2 7 /e, |E[/3W] < e /2. (4.2) Note th a t combining (4.1) and (4.2), the following holds: for any e > 0, and n > 2 7 /e, Pr - a w | > e] < 2e~^nltl. Our m ethod of proof for Theorem 2 is similar to th a t of [!-'»], though due to the differences in the nature of the problems (channel coding vs. compressed sensing) and the difference in the update equations at the graph nodes, some argum ents are C H A P T E R 4. A N A L Y S IS OF N B -V B A L G O R IT H M S O V E R R E G U L A R GRAPHS23 revised and some new components are added to the proof. We refer th e reader to [ 17] for the details of the proof. 4.3 A nalysis o f th e G enie In th e Genie algorithm, the support set is known. Therefore, th e set of all variable nodes can be partitioned into two sets: verified 1Z and unverified /C. At iteration zero, variable nodes in th e support set are unverified, and the zero-valued variable nodes belong to the verified set. In future iterations, during the verification process, variable nodes are moved from set JC to set 1Z. We use notations /C ^ and 7 Z ^ to denote th e set of unverified and verified variable nodes at (the beginning of) iteration £, respectively. We also use the superscript £ to indicate the iteration num ber for all th e other sets in this section in the same way. O ur goal in the analysis is to track the evolution of the subgraph induced by the variable nodes in /C^. This is th e subgraph th a t is actively involved in th e message-passing process. In the following, when we refer to the degree of a check node, we implicitly mean the degree of the check node in this subgraph. To make this explicit, we may use the term /C-degree. Similarly, th e term 7£-degree may be used. Clearly, the sum of the /C-degree and th e 7£-degree of each check node is dc. Each iteration of the Genie algorithm consists of only one round (two half-rounds, HR1 and HR2). At a generic iteration £, in the HR1, check nodes process the received messages from variable nodes sent at iteration £ —1 and generate outgoing messages to be delivered to variable nodes. We partition the check nodes based on their /C-degree. The set of check nodes with /C-degree i after the (processing in the) HR1 of iteration £, is represented by J\T^'l\ A check node w ith /C-degree j before H R 1 may have a degree i < j after H R 1 . In HR2, the variable nodes process the incoming messages and generate outgoing messages accordingly. Variable nodes, are also partitioned based on the num ber of neighboring check nodes of /C-degree 1. The unverified variable nodes with i neighboring check nodes of /C-degree 1 after the (processing in the) HR2 of iteration £ are represented by IC\e,2\ Note th a t the grouping of check nodes remains unchanged during the HR2 of the same iteration. In a similar way, the grouping of variable nodes remains unchanged during the HR1 of the next iteration. In the HR1 of iteration zero, every check node sends its corresponding m easure­ m ent value along with its degree, dc. In HR2, variable nodes in T Z ^ retu rn a verified message with a value equal to 0 , while variable nodes in /C ^ return a message w ith the statu s bit equal to zero. At iteration 0, the set /Cq0,2^ includes all unverified variable nodes /C ^ . In the HR1 of iteration 1, an outgoing message of a check node has th e following two properties: 1) the second coordinate of the message is still equal to the m easure­ m ent value for the check node since no variable node from the support set was verified at iteration 0, and 2 ) the first coordinate of the message, which is the /C-degree of th e check node, is less than or equal to dc since the variable nodes not in the support C H A P T E R 4. A N A L Y S IS OF NB- V B A L G O R IT H M S O V E R R E G U L A R G RAPHS24 set ( I Z ^ = 7Z(°)) have been revealed at iteration 0 , thus reducing th e num ber of unverified variable nodes connected to the check nodes. We use the notation A t o refer to th e subset of check nodes th a t are moved to A T h e arrow points downward in th e notation to emphasize th a t j < i. Note th a t for iteration 1 , i = dc. In the HR2 of iteration 1, after receiving the messages from check nodes, variable /q 2} /i 2^ (£} nodes in JC0 are partitioned into the sets /C) ,0 < j < dv. We denote by th e set of variable nodes in joining the set K^f'2\ In this case, j > i, hence th e use of th e arrow pointing up. Based on the verification rule for the Genie, at any iteration I if an unverified variable node is neighbor to a t least one check node in the set A i t will be verified. So, variable nodes in the set U jli A^1,2^ are verified at th e end of iteration 1. Therefore, the new sets IZ^ and to be used at iteration 2 are calculated as follows. 1Z{2) = | J A ^ ’2) U n {1\ /C(2) = JC{o'2). j =i T he message passing and verification processes continue in next iterations in th e same fashion discussed above. In summary, in a generic iteration I, we have the following relationships: dc A r u) = i K i . < = 3=0 n (e+l) = | J £(*.2) u 3 =1 n (t)^ 0 . y r = U ^ S ’ 0 < j < , d c, £ « + 1) = £(<,2) = Q £ (€ -1)^ i=j /C f2)==/c<£, 0 < j < d, j =0 By tracking th e set K, ^ w ith iterations, we can decide on the success or failure of the algorithm. If the size of the set shrinks to zero as I —> oo, then th e algorithm is successful. On the other hand, if there exists an e > 0 such th a t |/C ^ | > e, W > 1, then the algorithm fails. The success or failure of the algorithm depends on the param eters of the graph (dv and dc) as well as the initial size of the support set |/C ^ |. Based on the concentration results, to analyze the Genie in the asym ptotic case, we track th e probability th a t a variable node belongs to the set K Hence, we focus on a tree-like graph with random weights and a random input signal. Let P % '\0 < i < dc, denote the probability th a t a check node belongs to the set A/’/*,1\ Furtherm ore, let 0 < j < dv, denote the probability th a t an unverified (non­ zero) variable node belongs to the set ICf’2\ In Table 4.1, we have summ arized the terminologies used in the analysis of Genie, and in Table 4.2, we have presented the step-by-step procedure to update th e probabilities P ^ \ P^ ’2 , and a ^ , for £ > 1 , in term s of probabilities P%~l'l\ and P^~1,2^- The derivation details can be found C H A P T E R 4. A N A L Y S IS OF NB- V B A L G O R IT H M S O V E R R E G U L A R GRAPHS25 Table 4.1: Probabilities Involved in the Analysis of Genie in Table 4.2. Each E ntry of th e Table is th e Probability of the Corresponding Event. P r o b a b ility D efin itio n oS^ variable nodes is unverified at the beginning of iteration £. Pjtf u check node has /C-degree j before and /C-degree i, i < j , after HR1 of iteration £. check node has /C-degree i after the H R l of iteration £. P ^’^ unverified variable node has i neighboring check nodes of /C-degree 1 after HR2 of iteration £. p(t+1} edge connected to a variable node in /C ^ is also connected to a check node in A /^ ’1^. A^ edge connecting a check node in the set A/j<-1,1\ j > 2 , and an unverified variable node, carries a verified message to the check node in H R l of iteration £. in P a rt A.2 of th e appendix. 4.4 Fram ework for th e A n alysis o f X H The analysis of th e Genie and XH algorithm s are very similar and differ in a few u pdate rules. The XH algorithm consists of two rounds. However, since the D1CN verification rule is not present, it suffices to track the evolution of the support set in th e analysis. Prom this perspective, the analysis of the Genie and XH algorithm s are th e same. The only difference lies in th e set of variable nodes verified in each iteration. The set of verified variable nodes at iteration £ for the Genie algorithm follows n {t+1) = \ j ) c f 2)o n {t). i =i For the XH algorithm, this set is: n (e+D = II i=r«W21 HW) u C H A P T E R 4. A N A L Y S IS OF N B -V B A L G O R IT H M S O V ER R E G U L A R GRAPHS26 Table 4.2: Density Evolution Analysis of Genie I n p u ts : dv, dc, a^0) I n itia liz a tio n qX1) _ ^(o) Pm = (1 _ a (D) d c - l p A£^O2) = ( i - p (2)) J' R e c u rs iv e F o rm u la s fo r I > 2 1) 2) AW = l - ( l - p W ) = dv - l P” 4l = 0 . P ^ „ = l r Z , = ( A ) (A m y ~ ‘ (1 - ^ ) ‘ . 3) 4) 5) 6) p (Z ) = T . U pZ h ' )pZ , ' aW = a (<_1)pj£” 1,2) Nl a W dc = (*>) (p(<+*))J ( l - 2 < j < i c, o< i < j o < i< d c = } o ) ‘ (1 - “ (0)) * " i • am = am »< i < 4 p w = (l - i) p& 2> = (i - Pm t R e c u rs iv e F o rm u la s fo r £ > 2 r A/},ft A i -* A j )Cj iJl 21 The set JC\’ ’ in th e LM algorithm represents the set of unverified variable nodes in the support set with i neighboring check nodes in the set JVj T he definition of set for the SBB algorithm is different. Let JVt^ := UjLo 1A /^'7*1’^ . W ith (£ R1 21 this notation, the set fC\ ’ ’ in the SBB algorithm is defined as the set of unverified variable nodes in the support set with i neighboring check nodes in the set . These sets are shown in Fig. 4.2 for the two algorithms. In Theorems 3 and 4 below, we characterize the verification of unverified non-zero variable nodes in the set Kf® in each iteration £ for the two algorithms LM and SBB, respectively. The proofs are rather straightforward and follow from the verification rules for LM and SBB, respectively. T h e o re m 3. In the first round o f any iteration £ in the LM algorithm, a non-zero variable node v 6 Kf® is verified i f and only if it belongs to the set ( J ^ x C H A P T E R 4. A N A L Y S IS OF NB- VB A L G O R IT H M S O V ER R E G U L A R G RAPHS29 No /Cn 1,0 ,0 i N No Ki fCi -i 1 < , i —r Na, (a) LM (b) SBB Figure 4.2: The Difference in the Definition of K-i in LM vs. SBB. T h e o re m 4. In the first round o f any iteration I in the SB B algorithm, a non-zero variable node v E is verified i f and only if it belongs to the set Ui^2 IC\e’Rl’2^ U jC{*,R1'2\ where the set consists o f all variable nodes in the set )C^'R1’2^ con­ nected to the set Af^QR1,1^• In LM and SBB algorithms, unverified variable nodes with zero values are verified in R2. Note th a t a check node is zero-valued if it belongs to the set 0< j < dc. Therefore, for th e verification of zero-valued variable nodes in th e second round of iteration Z, we partition the set of variable nodes in A^) into subsets A ^ , 0 < i < dv, w ith th e following definition: a variable node in the set A-^ has i neighboring check nodes in the set { ljj= i A/"ojfl2,1\ (Jj= i A/qj**1’1^ , i.e., the set of check nodes which became zero-valued after H R l of R2. In Theorem 5 below, we characterize the verification of unverified zero-valued variable nodes in th e set A ^ a t R2-HR2 in each iteration I of LM and SBB algorithms. T h e o re m 5. In the second half-round o f the second round of any iteration Z in the L M and S B B algorithms a zero-valued variable node v E A ^ is verified i f and only if it belongs to the set U fli A t-^. We denote by A f ^ f p the set of check nodes th a t are moved from A /^-1’^2’1^ to l’^ in R1-HR1 of iteration Z. Similarly, the set of check nodes th a t are moved from K T ' 1] in R2-HR1 of iteration Z is denoted by A / ^ j ^ . Since variable nodes in K. and A are verified through iterations, we always have j < i and hence the use of notation i j . Moreover, in SBB, we denote the set of variable nodes th a t are moved from 1>2^ to jn fQ_HR 2 of iteration Z by K.^’R1\ The sets th a t fully describe the state of the decoder a t the beginning of iteration Z are: 1Z®, A ^ , Af}j~l'R2,1\ /C^-1’^ 1’2^, and por the analysis, we track the probability th a t a node (variable node or check node) belongs to a certain set at each half-round, round, or iteration. We use the notation a ^ to denote the probability th a t a variable node belongs to the set KS1^. For the rest of th e sets, C H A P T E R 4. A N A L Y S IS OF NB- V B A L G O R IT H M S O V ER R E G U L A R GRAPHS30 we use the standard notation of probabilities th a t was applied in the analysis of the Genie algorithm. For instance, we denote the probability that a check node belongs to the set by In the analysis, th e goal is to find the recursive equations th a t relate th e proba­ bilities of different sets for consecutive iterations. As we shall see, the analysis of the decoding process for LM and SBB results in a system of coupled recursive update equations. Moreover, we show th at the update equations at iteration t are functions of probabilities at iteration I —1. Hence, the complexity of the analysis scales linearly w ith the num ber of iterations. In the following subsection, we present the update equations for LM and SBB algorithms. T he derivation of formulas are discussed in detail in P arts A.4 and A .5 of the appendix for th e two algorithms, respectively. 4.6 U p d a te E quations for LM and S B B A lg o ­ rithm s We have summarized the sets involved in the analysis of LM and SBB algorithm s in Table 4.5. The step-by-step analysis of the algorithm s are presented in Tables 4.7, 4.8, 4.9, 4.10 and 4.1 1, where the update equations are identified by th e round and the half-round they correspond to. T he update equations in these tables involve the probabilities of the sets described in Table 1.5, as well as some other probabilities, defined in Table 4.6. 4.7 N o isy M easurem ents We adopt the following model for the case where the measurements are noisy [ 18]: c = G v + n. In this new model, v and G are the original signal and the sensing m atrix, respectively. The new term, n , represents the noise vector added to the noiseless m easurem ents G v , resulting in the noisy measurement vector c. Elements of the noise vector are assumed to be i.i.d. Gaussian random variables with mean 0 and variance 2) S ets In volved in B o th A n a ly ses K {t) unverified non-zero VNs at th e beginning of iteration £. AW unverified zero-valued VNs at the beginning of iteration ^~(£,ri,2) VNs in the support set with i neighboring CNs in th e set X after R1-HR1. For LM, X = A/’i ioH1,1) and for SBB, X = Af[t] := A (e,R2,2) £. V N s w ith . n e ig h b o r in g C N s in th e s e t | ( J ^ 1 ^ ef A f ^ f 1,1] . 2 ' 1]\ ( J ^ A f ^ j m ,1 )} i.e., the set of CNs which became zero-valued after R2-HR1. CNs with /C-degree i and A-degree j after R l-H R l. j^f(i,R2,\) CNs with /C-degree i and A-degree j after R2-HR1. CNs th a t are moved from Af}tl^ 1'R2'1'>to A fij’m '^ in R l-H R l. A f^ j^ CNs th a t are moved from A f ^ R1'^ to J \f^ R2'l'>in R2-HR1. S ets Involved in th e A n a ly sis o f S B B O n ly variable nodes moved from j = o, 1 , into i < j < dv. j^-(e,Ri,2,+) VNs in /C^.’f ^ not verified a t iteration £, R1-HR2. ^-{e,Ri,2,c) VNs in /C^’f 1^ not verified a t iteration £, R1-HR2. j^(e,R\XC) CNs moved from jV/ffc- 1’K2,1’+\ as p art of A f ^ f ^ a t iteration £, R l-H R l. CNg moyed from ^ ( /- i,« ! ,i>c )) ,LS p art of A /i‘£ p a t iteration £, R l-H R l. A Iaj^J R W ) CNs moved into the set Af\tf t2,l'>from all the other sets jV}i’R1'^ at iteration £, R2-HR1. A f ' f f 2'1'0 union of sets A ^ ’R2’C’F) and A f[* f2'+'F\ 1 < i < dc - 1 . j^(i,R 2,+,F) CNs of A-degree i w ith a neighboring VN in /C^’f ^ . Af&R 2,+,o) CNs of A-degree %w ith a neighboring VN in /C^.’F1\ j^(t,R 2,c,F) c n s of A-degree i, 0 < i < dc — 1, with a neighboring VN in tC ^Rl\ j^(e,R 2,c,o) c n s of A-degree z,0 < i < dc — 1, with a neighboring VN in /C ^F1\ are not verified, and consequently, no check node will have a reduced degree in the subgraph induced by unverified variable nodes. Therefore, the D1CN rule will also be ineffective. In the context of message-passing algorithms, there are generally two approaches to deal w ith noisy measurements. In the first approach, the original formulation of th e problem is changed so th a t the noise is taken into consideration [2<>, 27, 22- C H A P T E R 4. A N A L Y S IS OF NB- V B A L G O R IT H M S O V E R R E G U LA R GRAPHS32 Table 4.6: Probabilities th a t A ppear in the U pdate Equations of LM and SBB Algo­ rithm s for £ > 2 (in Addition to the Probabilities of the Sets Described in Table 1.5). Each E ntry of the Table is the Probability of the Corresponding Event. P r o b . In volved in B o th A n a ly se s message from a VN in A M to a CN indicates an unverified statu s in R l-H R l of iteration I. BM LM: edge adjacent to a VN in K.M is connected to a CN of degree 1 i.e., a CN in A/jfjf1’1, after R l-H R l of iteration £. SBB: edge em anating from a VN in K,M and not connected to a CN in UfcH)1 Af1(*,’R1’1’C‘>, is adjacent to a CN in (JfclV Arj^ R1,1’+-1. message from a VN in K.M to a CN (at iteration £, R2-HR1) indicates an unverified status. D {e) message from a CN to a VN in A M (at iteration £, R2-HR2) indicates a zero-valued check node. P ro b . In volved in th e A n a ly sis o f S B B O nly yj\* jn /c T f d is verified at iteration £, R1-HR2. yjsj jn js verjge(j at iteration £, R1-HR2. N (e'm i VN in K.M remains unverified at iteration £. p{i,Ri) edge is adjacent to a CN in the set AfM given it is adjacent to a VN in K.M. ■'51, i1*]. In the other approach, the algorithms are changed in order to cope with th e presence of noise in the measurements [2 ] . The first approach generally results in lower reconstruction noise. In particular, it is shown in [ >1] th a t the belief propagation algorithm is asymptotically optim al in the case of sparse noisy m easurem ents. The downside to th e algorithms th a t are based on the first approach, however, is th a t they are generally more complex, may require unbounded message size and would be susceptible to approximation errors. The authors in [2 ] instead equipped their VB algorithm with some thresholding techniques and proved th a t if the original signal is sparse enough, they are able to recover the location and the sign of th e non-zero signal elements successfully. In w hat follows, we propose a similar thresholding technique to deal w ith the noisy measurements. Thresholding is a common technique in detection theory to deal w ith noisy mea­ surem ents [5n]. We apply this technique to VB algorithms by defining two thresholds £i and e2- We use ei to convert small noisy measurements to zero; i.e., any mea­ surem ent c, such th a t |c| < ei, is set to zero. We use e2 as the acceptable tolerance C H A P T E R 4. A N A L Y S IS OF N B -V B A L G O R IT H M S O V E R R E G U L A R GRAPHS33 Table 4.7: Density Evolution Analysis of LM - Initialization I n p u ts : dv, dc, f , 0 ) ( l - (1 - a (0)) dc Apply the update equations of R2-HR2 for £ = 1 for the equality of two noisy measurements; i.e., we consider two m easurem ents c\ and C2 equal if |ci —C2 I < €2- In this case, we assign ci and C2 a new common value equal to (ci + c2)/2. While the scope of this work is not to optim ize thresholds t\ and C2i our goal is to dem onstrate the potential of thresholding in desensitizing the VB algorithm s to the measurement noise. We explain this through an example and by comparing the performance of the SBB algorithm equipped w ith thresholding and two m ethods based on G minimization in the case where the measurements are noisy. Consider a signal of dimension n = 1000. We let the size of the support set, k , to increase from 10 to 150 in steps of 10. For each such support size k, we pick k out of the n elements randomly, and assign to each element an even integer uniformly distributed in the range [—1000 , 1000 ], independent of the value of the other non­ zero elements. In the case of the SBB algorithm, the signal is m easured through a (3, 6 ) unweighted bigraph. In the case of G-based algorithms, we use sensing m atrices consisting of orthonorm al columns with Standard Gaussian elements [ l>]. In all cases, th e num ber of measurements, m , is fixed at 500. Each m easurem ent is independently contam inated with a Gaussian noise of mean 0 and variance equal to a 2 — 0.25. For th e SBB, we set both thresholds e\ and 62 equal to 1.99. Since the value of non-zero signal elements are drawn from a finite alphabet and since the graph is unweighted, false alarm may occur with non-zero probability in the recovery process. In our simulations, we consider a recovery algorithm “successful” if it can fully recover th e support set. The first £1-based recovery algorithm is the G regularization m ethod introduced in [In]. For the second algorithm, we empower the G regularization algorithm w ith the knowledge of th e size of the support set. The algorithm thus keeps the k com ponents th a t are the largest in m agnitude and converts the rest to zero. To sim ulate the two C H A P T E R 4. A N A L Y S IS OF NB- VB A L G O R IT H M S O V E R R E G U L A R GRAPHS34 Table 4.8: Density Evolution Analysis of LM - Recursive Formulas for I > 2 pW 1) HRl R1 2) ^ n bw 2) A = 0 3) } HR2 AW = (A(t)Y ( X“ A(t)) k~j , l < i < d c, 0 < k < d c - i , 0 < j < k 3) = ctW ^1 - 2) < “ 1 = 1. « - » . 2 < i < dc, 0 < j < i, 3) PW ^ = ^ p W R^ ) p W ^ k, i=j dc—1 HRl R2 0 < j< d c- i U) = £ 7^ 1,K2’1)j;S S ! ’ k=j pd.Ki.P = M -° a Wdc = f t ) ( B ^ y (i - B W )dv- \ 1) 0 ) ( D W y (1 _ 3) P{l +l) = p f p (l f 2'2) i=1 HR2 , 0 < i < dv fi-based decoders, we use the L1MAGIC package available in [31]. As the measure of performance, we consider the mean square error (MSE) between th e original and the recovered signal. For each value of k, we perform sim ulations until we obtain 100 “successful” recovery instances. The results for th e three algorithm s are reported in Fig. 4.3, where for each algorithm , MSE averaged over all sim ulated cases for a given value of k is shown. As can be seen, th e SBB recovery algorithm significantly (by about two orders of m agnitude) outperforms both £i-based algorithms. C H A P T E R 4. A N A L Y S IS OF NB- V B A L G O R IT H M S O V ER R E G U L A R GRAPHS35 Table 4.9: Density Evolution Analysis of SBB - Initialization Inp u ts: dv, dc, , 1'» = (I -« < ")) ( l - (1 H t) ~ « <0T T 0 < i < dc = (V ) ( A m Y (1 - . 1 <<<«*». 1 (> + P ^ 1,2)) ( l _ 5 ( D ) * ’- 2 ( i _ / ( i , * b ) p(1.^2) 1 A/14.0 ,0 ’ q A/14,1 ,0 p£;“ J = (1 - B '1))4-- 1 , P / K = (D (C(1)) ‘ ( ‘ _ ° m Y k ■ 2 S i < 4 , (1„R2,1,+) 5 (D ) * - 1 a - B<1))*’. * “ '2> = 2 < i < d v, a (2) = a ( D # ( i , * D (1 - p (l,R 2 ) f ^ m ) ) B (1) ( 1 - 0 < j < dc - 1 0 2 HR1 » 2) (1 - A ^ ) k- ‘ , l < i < d c, 0 < k < d e - i , 0 < j < k = (J) dc—1 6> M ,3 - 2s fc=j dc-l ~ 2s P* i,k p^ ,n P P ^ M) = J S U- 2 < i < 4, dc ~ 0 < j < dc k=j dc-l p(/,m,i,+/c) HR2 1) /«.-Ri.+/c) = Z_^ ? jg(<) = ]= ( t7 ) ( W i,+ ) + ^ i p ( £ R1H " ' ( ! - B(e)) dv~ 1 3 0 J\T(i,Rl) __ p ^ -1 ,^ 1 ,2 ) /p (^ i2 1 ) , p (€ ,fll) /Co I /^ofo Z^oti ' + p g r i -in -a)p g ^ ) ( i - / ^ 2) (<,jn,i,+) j=0 p ( j ,i e i , i ,+ / c ) p^ 1 __ '/ ) «(<+!)= a W A ffW D«-l,fll,2)p («,J*l) v ( e , m , 2) _ D c? ^oto A/V,Ri) r)(*,/U,2,+) _ 1 - / (*’'R1’+ ) ,n(*-l>R1.2)-n(«>Rl) *4 ~ „(<,fll,2,C) K1 “ NVRL Ko R ^ oti 1 _ f ^ t 'R1’C'i n {e -l,R l,2 )n (^R 1) jV(*.Ri) (€,K1,2) _ (<,*1,2,+) RjCi — DCi + (e,Rl,2,C) » (e,Rl,2) _ n *7Cj ~ U' 9 ^ ^ j __________ n -» oo. This includes the success threshold of different VB algorithm s over differ­ ent biregular graphs. The comparison of asym ptotic and finite-length results shows th a t there is a good agreement between the two for moderately large block lengths (n > 10 5). In all simulations, a signal element belongs to the support set w ith probability unless otherwise specified. Also, each non-zero signal element (variable) is drawn according to a standard Gaussian distribution. The biregular graphs are constructed random ly with no parallel edges and all the edge weights are equal to one. In each set of simulations, th e sensing graph is fixed and each simulation point is generated by C H A P T E R 4. A N A L Y S IS OF N B -V B A L G O R IT H M S O V E R R E G U L A R GRAPHS37 Table 4.11: Density Evolution Analysis of SBB - Recursive Formulas for Round 2, I > 2 dc - 1 p ( 0 « ,i ,+ ) , p (e,m ,i,c) HRl 1) p(('RV = ] T i =o Ml'j Ot^dr El) ( d y ( e - i , m , 2 ) (e.Ri) + 1 - p(t,Rl) p ( i - \ , R \ , 2 ) v (t,R l) ( ACltl K l d y V - J ( l _ f(£,Rl,C)j . i —k ^ < i < d c, 0 < k < i , 0 < j < d c i jj(i,Rl,l,+)v (i—1 , R 1 , 2 ) n(t)\dv- l D > Kg_________D AC0 ^ - pXi,i y*{£,R2,C,0) VA/i . d c - 1 ft <' ? <"" /7 U S * S Uc - 1 1 piCm ~j(£,Rltl,C?) - 0 < * < 7"ACi jj(£,R2,+,0) _ „(£,R1,1,+) r,(<,R2,+,/r) PMi,i “ M,» ~ PNx,i > n (e,R2,C,F) _ n (t,Rl,l,C)n (e,Rl) pMi,i J 1 \ d y a v l Afi,, dy 1 _ P ( t ,R l ) P Z uZ = G) (Cit)) (1 „( e ,R 2 ,+ ,F ) _ 1\ K-ot1 \ jj(£,R2,C,F) #-> ~ 'V , . , )U S I S 1 dc ~ t dc z) V (£,R2,\) _ „(£,R1,1) PMo,3 - PMo,3 n (e,R 2,C ,0) + M ,j n (£,R 2 ,+ ,0) + 'X j ^ i («,R2,1,+) _ ^ n ( £ , R l , l ) n (i,R 2 ) + / A ., n ^ ^ , P/tfuoj’ U S j <)“' " . 0 < i < 4 2) p f averaging over 1000 random instances of the input signal, unless specified otherwise. We repeated each simulation w ith different random ly generated graphs (with the same variable and check node degrees), and observed th a t the results were alm ost identical for every graph. Each simulation is run until the algorithm makes no further progress. In this case, if the signal is recovered perfectly, the recovery is called successful, otherwise a failure is declared. C H A P T E R 4. A N A L Y S IS OF N B -V B A L G O R IT H M S O V E R R E G U L A R GRAPHS38 — Modified L1 — Original L1 -e-SBB 100 150 Figure 4.3: Comparison between SBB, I\ minimization, and modified £\ minim ization in term s of MS reconstruction error in the presence of Gaussian m easurem ent noise w ith zero mean and variance a 2 = 0.25 (n = 1000, m — 500). For the analytical results, based on the fact th a t is a non-increasing function of iteration num ber £, we considerth e following stopping criteria: 1. < 10- 7, 2. > 10-7 and | a ^ — < 10 -8 . If th e analysis is stopped based on th e first stopping criterion, th e algorithm is con­ sidered successful. If, on the other hand, it is stopped based on the second criterion, the algorithm is considered unsuccessful and a failure is declared. To calculate the success threshold, a binary search is performed until the separation between the start and the end of the search region is less than 10 ~5. 4.8 .1 C om parison o f S B B and ^i-based algorith m s at fin ite len g th To m otivate th e use of recovery algorithm s over sparse graphs, as th e first set of simulation results, we present the comparison between th e SBB algorithm and two benchm ark £i~based algorithms, £\ m inimization [5] and iterative weighted mini­ mization [52]. The setup is as follows. For SBB, we choose a random (3 , 6 ) biregular sensing graph with 1000 variable nodes and 500 check nodes. T he sensing m atrix used for th e two £i-based algorithms consists of 500 rows and 1000 columns. The elements are initially i.i.d. standard Gaussian random variables. Then the rows are made orthonorm al. The cost functions used in £\ and weighted i\ minimization algorithm s are ||u ||i := |uj| and || W v ||i := ]>T respectively, where v is the original signal of interest w ith elements v i5 and W is a diagonal m atrix with positive diagonal elements Wi C H A P T E R 4. A N A L Y S IS OF N B -V B A L G O R IT H M S O V ER R E G U L A R G RAPH S39 representing the weights. Weighted t\ minimization is an iterative algorithm in which th e weights at iteration t (wj^) are updated according to w® = l / ( |u j t-1^| + e ), where is th e estim ate of the signal element Vi at iteration t — 1. T he weighted is not very sensitive to the param eter e as noted in [52]. We found e = 0.1 is a good choice based on our simulations. Regarding the maximum number of iterations for th e weighted minimization algorithm, it is shown in [-72] th a t as this param eter increases, b etter results are achieved, w ith the cost of longer running time. The improvement gained by increasing the num ber of iterations beyond 6 however, is negligible [72]. Therefore, in our simulations, we choose a conservative maximum num ber of iterations equal to 10. As l \ and weighted l \ minimization algorithm s o utput an estim ate which is very close to the original signal, b u t not exactly the same, we declare a success for these two algorithms if th e difference between every original signal element and its corresponding estim ate is less th an 10"2. Lastly, we use the L 1 MAGIC package in [ * > l ] as the optim ization engine for sim ulating £\ and weighted £\ minimization algorithms. To have a fair comparison, the same signal vectors are used for all the algorithms. We also choose the size of the support set deterministically, and let th e size range from 10 to 300. For each support size, 100 instances of the signal vector are generated. Each signal vector is then measured according to the corresponding sensing mechanism for each class of algorithms. The success or failure of the recovery algorithm s over the resulting measurements are then averaged over the 100 instances, and plotted in Figure 4.4. In Figure 4.5 the average running time, in seconds, is plotted for the three algorithms. The algorithms were implemented in MATLAB and were run on a com puter with an AMD Phenom 9650 Quad-Core 2.3 GHz processor, 3 GB RAM and a Windows 7 operating system. As can be seen, the SBB algorithm recovers signals w ith more non-zero elements at a speed which is about 2 orders of m agnitude faster compared to th a t of the i \ algorithms. To dem onstrate th a t the recovery performance of NB-VB algorithms is insensitive to the distribution of non-zero signal elements and th a t of non-zero elements of the sensing m atrix, as long as at least one distribution is continuous, we perform the same experiments, this time by selecting the non-zero signal elements independently from the binary set { —1 , 1 } and by choosing the non-zero elements of th e sensing m atrix independently from a standard Gaussian distribution. The results for SBB in this case are also presented in Fig. 4.4. As can be seen, they are close to th e results where the non-zero input signals are Gaussian and the sensing m atrix elements are binary. 4.8.2 A sy m p to tic and fin ite-len g th resu lts for N B -V B algo­ rith m s For the next experiment, we apply Genie, XH, SBB and LM algorithm s to four randomly constructed (5,6) regular graphs with n — {3, 15,100,1000} x 103. The C H A P T E R 4. A N A L Y S IS OF NB- VB A L G O R IT H M S O V E R R E G U L A R G RAPHS40 0.9 0.8 0.7 g 0.6 8 0.5 a 04 0.3 0.2 -e-Li —SBB -•’Weighted L1 -W-SBBBinary Input 100 150 170 200 2$0 ° Figure 4.4: Comparison between success ratios of weighted I\ and SBB (continuous-input/binary-sensing coefficients and binary-input/continuous-sensing coefficients) for n — 1000, m = 500. ♦L1 — SBB ♦ W eig h ted L1 ®10 .-3 100 150 200 250 300 Figure 4.5: Comparison between the average running tim es of t \ , weighted i\ and SBB for n = 1000, m = 500. success ratio of the algorithms versus the initial density factor a — are shown in Figure 4.6. From the figure, we can see th at, for all algorithms, by increasing n, the transition p art of the curves becomes sharper such th a t the curves for n = 106 practically look like a step function. In th e figure, we have also shown th e success threshold of the algorithms for (5 , 6 ) graphs, obtained based on the proposed analysis, by arrows. As can be seen, the thresholds match very well with the waterfall region of the simulation curves. In Table 4.12, we have listed the analytical success thresholds of the iterative recovery algorithms for graphs with different dv and dc values. T he result for XH algorithm on (3,4) graphs, and more generally for graphs w ith dv = 3, is missing as the C H A P T E R 4. A N A L Y S IS OF NB- VB A L G O R IT H M S O V E R R E G U L A R G R A P H S 4 1 -*-n = 3,000 —n = 15,000 -- n = 100,000 —n = 1,000,000 to 0.6 Genie 5 0.5 0 Figure 4.6: Success ratio of Genie, XH, LM and SBB algorithm s vs. a = a:^0^ for (5,6) graphs w ith n = (3,15,100 and 1000} x 103. Analytical thresholds are shown by arrows. algorithm performs poorly on such graphs .3 For every graph, the Genie algorithm has th e best performance. This is followed by SBB, LM and XH algorithms, respectively. Careful inspection of the results in Table 4.12 indicates th a t the oversampling ratio r° ~ adt improves consistently by decreasing both dv and dc values. In fact, among th e results presented in Table 4.12, the application of th e Genie and SBB to (3,4) graphs results in the lowest oversampling ratio of « 1.16 and « 1.67, respectively. Table 4.12: Success Thresholds for different graphs and algorithm s (dv, rfc) (3,4) (5,6) (5,7) (5,8) (7,8) Genie 0.6474 0.5509 0.4786 0.4224 0.4708 SBB 0.4488 0.3892 0.3266 0.2806 0.3335 LM 0.3440 0.2871 0.2305 0.1907 0.2385 XH - 0.1846 0.1552 0.1339 0.1435 In Table 4.13, we have listed the analytical success thresholds of the iterative VB recovery algorithm s for graphs with compression ratio dv/ d c = 0.5 and different dv and dc values. In general, as we decrease dv, algorithm s perform b etter in term s 3The reason is that for dv = 3, a variable node is verified with the common value of \dv/2] = 2 check nodes. However, if two non-zero variable nodes share the same two check nodes (a cycle of length 4 exists in the graph), then a false verification may occur. C H A P T E R 4. A N A L Y S IS OF NB- VB A L G O R IT H M S O V E R R E G U L A R GRAPHS42 of recovery capability .4 This also implies th a t for a fixed compression ratio, the oversampling ratio improves by decreasing dv and dc. Table 4.13: Success Thresholds for different graphs and algorithms for fixed compres­ sion ratio r c = 0.5 ([dv, dc) (3,6) (4,8) (5,10) (6 , 12 ) (7,14) Genie 0.4294 0.3834 0.3415 0.3074 0.2797 SBB 0.2574 0.2394 0.2179 0.1992 0.1835 LM 0.1702 0.1555 0.1391 0.1253 0.1140 XH - 0.1875 0.1050 0.1170 0.0791 We have also presented the success thresholds of NB-VB algorithm s versus the compression ratio for different dv values in Fig. 4.7. T he same trends as discussed above can also be seen in this figure in addition to the expected result th a t the success threshold in general increases w ith the increase in the compression ratio. The relative rate of this increase for each algorithm in relation with the other algorithm s follows th e same trend as the relative performances, i.e., Genie has the highest rate followed by SBB, LM and XH, respectively. In Tables 4.14 and 4.15, we have listed the num ber - i-----------1 — .. 1--1 i........ ..... r..............r..............i" 0-7f—I— ^Genie — :—zd = 3 i........... ----------1-----------------------------— <—~ — v ......... — -.-Genie ... ¥V Genie dV= 7 0.6- — Geniedy -0-LMdv -©-LM dy = 3 2 0.5- -e-LM -e-LMddv = 77 o ^ v .• _ ^_ -b -SBB dV= 3 . • 'X ' ©.SBB dy = 7 - -x-XH dy = 4 -h-XH dy = 7 w o. ^ 0. 13 — __* n <>' - 0.1 i 0.2 — *— * i i i i 0.3 0.4 0.5 0.6 Compression Ratio (d (dy/dc) Id ) i 0.7 i 0.8 0. 0.9 Figure 4.7: Success threshold vs. compression ratio for LM, XH, SBB, and Genie algorithms. 4These results are consistent with the results observed for the Belief Propagation (BP) decoding of binary LDPC codes based on biregular graphs. C H A P T E R 4. A N A L Y S IS OF N B -V B A L G O R IT H M S O V ER R E G U L A R GRAPHS43 of iterations required for different recovery algorithms to recover signals w ith density factor equal to the success thresholds reported in Tables 4,12 and 4.14 minus 0.0001, respectively. These results, which are obtained by the asym ptotic analysis are in close agreement w ith finite-length simulation results a t block lengths of about 105. These results indicate th a t with a few exceptions, the b etter performance comes a t the expense of a larger number of iterations. In particular, among the practical recovery algorithms, SBB requires the largest num ber of iterations for convergence. Table 4.14: Num ber of iterations required for different recovery algorithm s over dif­ ferent graphs to recover a signal with density ratio equal to the success threshold minus 0.0001 (dv, dc) (3,4) (5,6) (5,7) (5,8) (7,8) Genie 106 66 66 62 55 SBB 655 178 165 200 344 LM 258 139 103 126 108 XH - 63 58 54 41 Table 4.15: Num ber of iterations required for different recovery algorithm s over dif­ ferent graphs w ith fixed compression ratio rc = 0.5, to recover a signal w ith density ratio equal to th e success threshold minus 0.0001 (3,6) (4,8) (5,10) ( 6 , 12 ) (7,14) Genie 93 69 57 50 46 SBB 247 167 172 163 127 LM 142 94 136 97 55 XH - 64 48 38 32 (dv, dc) To further investigate the degree of agreement between our theoretical asym ptotic analysis and finite-length simulation results, we have presented in Fig. 4.8 the evo­ lution of with iterations £ for Genie, LM, SBB, and XH over a (5 , 6 ) graph. For each algorithm, two values of are selected: one above and one below the success threshold presented in Table 4.12. The theoretical results are shown by solid lines C H A P T E R 4. A N A L Y S IS OF N B -V B A L G O R IT H M S O V E R R E G U L A R G RAPHS44 while sim ulations for n — 105 are presented with dotted lines. As one can see, the two sets of results are in close agreement particularly for the cases where is above the threshold and for smaller values of I. G enie XH 0.2 0.15 0.4 a a 0.2 0.05 40 Iteration ( t ) 0.2 a 0.1 40 Iteration ( I ) LM Theoretical Below Threshold Theoretical Above Threshold Simulation Below Threshold Simulation Above Threshold SBB 0.4 0.3 0.2 0.1 10 25 Figure 4.8: Evolution of vs. iteration num ber £ for the four recovery algorithm s over a (5,6) graph (finite-length simulations are for n = 105). To dem onstrate th a t the simulation results converge to the asym ptotic analytical results as n grows, in Fig. 4.9, we have added th e simulation curves for n = 104 and 106 to th e SBB curves in Fig. 4.8. As can be seen, the larger the value of n, the closer the simulation results to the analytical ones. In particular, the curves for n = 106 practically coincide with the analytical results. Next, for different values of a (0\ we estim ate the average fraction of unverified non-zero variable nodes using the analysis, and denote the value of a t the tim e th a t the analysis stops (because one of the stopping criteria is m et) as aSatop\ These values are plotted vs. the corresponding values of q (0' in Fig. 4.10 for the four VB recovery algorithms over the (5 , 6 ) sensing graphs. In the same figure, we have also given the corresponding sim ulation results for two randomly selected (5 , 6 ) sensing graphs w ith n — 105 and 106. T he simulation results for both lengths closely m atch the analytical results, with those of n = 106 being practically identical to the analytical results. We have indicated the success threshold of the algorithm s by arrows. From th e figure, it can also be seen th a t as increases and tends to one, the curves tend to the asym ptote aSstop) — q4°). The results presented in Tables 4.12 and 4.18 are for sensing graphs w ith compres­ sion ratio at least 0.5. We have also investigated the application of NB-VB algorithm s C H A P T E R 4. A N A L Y S IS OF NB- VB A L G O R IT H M S O V E R R E G U L A R GRAPHS45 0.4 0.35 0.3 0.25 0.15 0.05 ♦Simulation BelowThreshold, n = 104 ♦Simulation Below Threshold, n = 10^ ♦Simulation Below Threshold, n - 1C^ —Theory BelowThreshold ♦Simulation Above Threshold, n = 10* ♦Simulation Above Threshold, n » 1CP ♦Simulation Above Threshold, n » 1if •--TheoryAbove Threshold_______ 25 Iteration ( £) Figure 4.9: Evolution of vs. iteration number for SBB over a (5,6) random graph (finite-length simulations are for n = 104, 10 5, and 10 6). Genie XH 0.25 0.5 0.2 ■s 0.15 Z. 0.3 02 0.1 0.1 0.05 0.6 0.2 LM 0.3 SBB 05 0.3 5 0.3 025 'a 0.2 03 0.1 0 .0 5 03 0.3 5 0.4 0 .4 5 05 Figure 4.10: Fraction of unrecoverable variable nodes vs. the initial density factor for different recovery algorithms over random (5,6) regular bipartite graphs. T he arrows represent th e theoretical success thresholds. The straight line represents the function f { x ) = x. to graphs w ith lower compression ratios. For example, simulation results on the suc­ cess ratio of SBB over random graphs w ith n = 105 and (dv, dc) equal to (3, 30), (4,40) and (3,45) are presented in Fig. 4.1 1. These graphs have compression ratios equal to 1/10, 1/10 and 1/15, respectively, and their success thresholds for SBB are 0.0338, 0.0380 and 0.0209, respectively. These thresholds are shown in Fig. 4.11 by vertical dashed lines, and they each m atch the waterfall region of the corresponding finite-length simulation curve. As expected, the lower compression ratio corresponds C H A P T E R 4. A N A L Y S IS OF N B -V B A L G O R IT H M S O V E R R E G U L A R GRAPHS46 to smaller density factors for the signals th a t can be recovered using these graphs. In Fig. 4.7, this corresponds to the tails of the curves close to the origin. 4 .8 .3 C om parison o f S B B and t\ recovery in th e a sy m p to tic regim e o f n —> o o Strong and weak thresholds [V i] are im portant measures of the perform ance of th e P.\ recovery. In particular, the weak threshold is the largest undersampling ratio k / m for which the l\ recovery and £q recovery are equivalent w ith overwhelming probability in the uniform selection of the sensing m atrix for most input signals as n —» oo. As another way of comparing the NB-VB recovery algorithms and l \ recovery, we compare th e success threshold of the former divided by the compression ratio m / n , with the weak threshold of the latter. Consider two scenarios with compression ratios m / n equal to 0.5 and 0.75. The weak threshold of £\ recovery for these cases is 0.3848 and 0.5327, respectively [54], The corresponding values for SBB over (3, 6 ) and (3, 4) graphs are 0.5148 and 0.5984, respectively. In both cases, the values for SBB are larger, and indicate th e superiority of SBB. 0.8 is 0.6 0.4 0.2 0.015 0.02 a 0.03 0.035 0 0 0 0 6 Figure 4.11: Success ratio of SBB vs. a — cd°) for graphs with n = 105 and (dv,d c) equal to (3,30), (4,40) and (3,45). Theoretical success thresholds are shown by vertical dashed lines. 4 .8 .4 C om parison w ith th e a sy m p to tic resu lts o f [1] As the last experiment, we compare the running tim e and th e accuracy of th e proposed asym ptotic analysis against those of the differential equation approach presented in [I]. For comparison, a biregular (3,6) graph and the SBB algorithm are chosen. The binary search for the success threshold starts w ith the interval [0.2,0.3] and ends C H A P T E R 4. A N A L Y S IS OF N B -V B A L G O R IT H M S O V E R R E G U L A R GRAPH S47 when the separation between the sta rt and the end of th e search region in less than 10~5. The analysis is implemented in MATLAB and executed on the same com puter described before. Using the proposed analysis, we obtain the success threshold of 0.2574 in 23.1 seconds. Table 4.16 summarizes the results of running the analysis of [ I] on th e same machine for different values of n. The reported thresholds increase w ith the increase in n. For n = 105, the running tim e is roughly 100 tim es th a t of our proposed m ethod. Moreover, and more im portantly, the obtained threshold of 0.2591 is only in agreement with the threshold of 0.2574, obtained by th e proposed m ethod, up to two decimal points. In fact, experiments similar to those reported in Fig. 4.8 reveal th a t the accuracy of the threshold obtained by the m ethod of [i] is lower th an our results. In particular, our simulations show th at the SBB algorithm over (3,6) graphs with n = 105 fails for = 0.259, which would imply th a t the threshold 0.2591 is only accurate up to two decimal points. Table 4.16: Success threshold and running tim e of the analysis of [I] for SBB over a random (3, 6 ) regular graph. n Success Threshold Running Tim e (seconds) 100 1,000 10,000 20,000 50,000 1 00,000 0.2465 0.2577 0.2589 0.2590 0.2590 0.2591 1.1 9.9 103.9 220.6 647.4 2044.1 C hapter 5 A n a ly sis o f N B -V B A lg o rith m s over Irregular G raphs 5.1 Introduction T he m ain focus of this chapter is on the analysis of NB-VB recovery algorithm s for compressed sensing w ith irregular sensing graphs. Our results are derived in the asym ptotic regime (n —» oo). In this regime, the input model is as in C hapter 4, i.e., a signal element is zero w ith probability 1 — a or takes a value from a continuous distribution w ith probability a. In this chapter, we extend the analysis presented in C hapter 4 to irregular graphs. O ur simulations show th a t for a given compression ratio m /n , irregular graphs can provide up to 40% larger success thresholds compared to regular graphs. Ju st like th e analysis in C hapter 4, the proposed analysis is developed for noiseless measure­ ments and its com putational complexity increases only linearly w ith the num ber of iterations. Moreover, the analysis is simple to perform, requiring only additions and multiplications. T he SBB algorithm performs the best among all known VB algorithm s in the context of compressed sensing [1,40, 11], Hence, the analysis of SBB over irregular graphs is the focus in this chapter. The proposed analytical framework is, however, general and applicable to the analysis of other NB-VB algorithms over irregular graphs as well. 5.2 A sy m p to tic A n alysis Fram ework Let the probability distributions / and g , the degree distributions A and p, and the density factor a be fixed. It can be shown th a t the fraction of unverified non-zero variable nodes at each iteration £ of the SBB algorithm ( a ^ ) over a realization of th e sensing graph Q G £7"(A, p) and a realization of th e input signal V G V” (a) concentrates around the average of taken over all th e elements in th e ensemble 48 C H A P T E R 5. A N A L Y S IS OF NB- V B A L G O R IT H M S O V E R IR R E G U L A R G RAPHS49 Q j ( \,p ) x Vg(a), as n tends to infinity .1 T he determ inistic analysis presented here is to track the evolution of this average as n goes to infinity. In the language of coding, th e analysis is similar to the density evolution analysis of iterative decoding algorithm s for irregular LDPC code ensembles, w ith the main difference being th a t the NB-VB algorithm s do not conform to the principle of extrinsic message passing which significantly simplifies the density evolution analysis in the context of coding. The analysis of the SBB algorithm over irregular bigraphs tracks the fraction of zero and non-zero unverified variable nodes through iterations. This m athem atical framework for th e analysis is similar to the one presented in Chapter 1 (and previously used in [ 10, II]), however with two extra variables dv and dc which represent the degree of a variable and a check node, respectively. These variables take different values for irregular graphs while for a regular graph they each have a fixed value. This makes the derivations more tedious. Henceforth, we denote by dVtiaax and dCimax th e highest variable and check degree in the distributions X(x) and p(x), respectively. Nevertheless, the same notations will be used throughout this chapter. For instance, at th e beginning of each iteration £, the analysis partitions the set of all variable nodes into three (disjoint) sets: unverified non-zero variable nodes (/C ^), unverified zero­ valued variable nodes ( A ^ ) , and all variable nodes recovered up to iteration £ (7Z ^ ) . Should the fraction of variable nodes in the set tend to zero as iterations proceed, th e fraction of variable nodes in the set A w will also tend to zero and consequently the analysis declares a successful recovery [In]. Each iteration in the SBB algorithm is divided into two rounds (R ), each consisting of two half-rounds (H R). In the first and second rounds, verified variable nodes belong to the sets /C ^ and A ^ , respectively. The configuration of the sets at the end of each processing is specified using th e superscript ( £ ,R x ,y ), where £, x e { 1 , 2 } and y G {1,2} denote the iteration, the round and the half-round numbers, respectively. We partition the set of all check nodes with the same degree (say dc) into sets A f i j ( d c), 0 < i < dc, 0 < j < dc — i, where i and j indicate the num ber of neighboring variable nodes in th e sets and A ^ , respectively. Let JC^(dv) and A ^ ( d v) denote the set of all non-zero and zero-valued unverified variable nodes with the same degree dv, respectively. Then, the set K .^ ( d v) is further (p\ divided into subsets K\ (dv), 0 < i < dv, where i denotes the num ber of neighboring check nodes in th e set (Jdc A f l j R1'l\ d c). Also, we divide the set A ^ ( d v) into subsets A ^ ( d „ ),0 < i < dv, with the following definition: a variable node (f\ in A \ (dv) has i neighboring check nodes which became zero-valued after H R 1 of R 2 ; check nodes in the set j|J dc U j l i (dc) \ (Jdc U ^ i ^ o j H1,1)(rfc)}. Table 5.1 summarizes the sets affected in each half-round of each round at any iteration. The formulation in the table assumes a variable node of degree dv and a check node of C H A P T E R 5. A N A L Y S IS OF N B -V B A L G O R IT H M S O V E R IR R E G U L A R G RAPHS50 Table 5.1: Sets th a t change in each half-round of each round at any iteration, assuming a variable node of degree dv and a check node of degree dc. The degrees dv and dc can be any valid degree according to the distributions X(x) and p(x). R2 R1 HR1 •^fc,i(^c) ^ A/fc)j(d c) HR2 JCi(dv) —>JCj(dv) HR1 Afitk(dc) y Afj,k(dc) HR2 A i(dv) —> A j(d v) degree dc. This table is indeed the generalization of Table 4.4. Theorems (i and 7 below, characterize the verification of unverified non-zero (JC^) and zero-valued ( A ^ ) variable nodes at HR2-R1 and HR2-R2 in each iteration I of th e SBB algorithm, respectively. The theorems are generalized version of Theorem s 4 and 5. T he proofs of the theorem s are rather straightforward and follow from the verification rules and therefore omitted. T h e o re m 6 . In the first round of any iteration I, a non-zero variable node of degree d is verified if and only i f it belongs to the set Uf =2 ^ f ’Rl’2\ d ) U (d), where the set JC^’m,2\ d ) consists o f all variable nodes in the set JC^’R1'2\ d ) connected to the set U d e - ^ o ^ V c ) . T h e o re m 7. In the second round o f any iteration t, a zero-valued variable node of degree d is verified i f and only if it belongs to the set U?=i (d) ■ The sets A w , A /g“ 1,H2,2)(dc), and A f ~ 1,jR2,2)( 4 ) , (1 < dc < dc,max and 1 < dv < d„,max) fully describe the state of the algorithm at the beginning of iteration I. The probability th a t a variable node belongs to the set is Following th e notation introduced in C hapter 4, for any other set Z , we use the notation P%' ,v^ to denote the probability th a t a node belongs to the set Z^i,Rx’y\ The asym ptotic analysis tracks the probability th a t a node (variable node or check node) belongs to a certain set at each half-round, round, or iteration. T he recovery is successful if and only if the probability tends to zero, as I tends to infinity. As we shall see, the analysis is based on the derivation of recursive equations th a t relate the probabilities described above for two consecutive iterations. The complexity of the analysis thus scales linearly with the number of iterations. In the following section, we present such recursions for the SBB algorithm. The derivation of formulas are discussed in detail in Appendix B. 1These concentration results have been proved in detail for regular graphs in [ 1. ]. Similar results apply to the irregular sensing graphs with minor changes, and are therefore not presented here. C H A P T E R 5. A N A L Y S IS OF NB- VB A L G O R IT H M S O V E R IR R E G U L A R G R A P H S 5 1 5.3 U p d a te R ules for th e SB B A lgorith m The step-by-step analysis of the algorithm are presented in Tables 5.2, 5.3, and 5.4 at th e end of this section, where the update equations are identified by the round and th e half-round they correspond to. The update equations in these tables involve the probabilities of the sets described in Table 4.5, as well as some other probabilities, defined in Table 4.0, generalized so th a t they include the variable and check degrees as well. It is worth comparing the update equations of Tables 5.2, 5.3, and 5.4, for ir­ regular graphs, with their counterparts in Tables 4.9, 4.10, and 4.11, for regular graphs. Generally speaking, the update equations for irregular graphs can be seen as a generalized version of their regular counterparts in two ways: some are generalized by including the node (variable or check) degree, and some are generalized through weighted combination of their regular counterparts, where weights are functions of th e degree distributions X(x) and p(x). 5.4 Sim ulation R esu lts To verify th e asym ptotic results obtained based on the analysis of this chapter, we perform some finite-length simulations for large values of n. The input signal in all simulations follows the probabilistic model described in Section 2 .2 . Also, each non­ zero signal element is drawn from a standard Gaussian distribution (zero-mean with variance one). The graphs are constructed randomly w ith no parallel edges and all edge weights are chosen to be 1. Each simulation point is generated by averaging over 100 random instances of the input signal. The graphs used in our finite-length simulations include variable nodes of degree 2 . The presence of such variable nodes, in finite length simulations, m ight introduce graphical structures th a t prohibit some variable nodes from being verified [1, 15]. Based on our extensive simulations, the number of such unverified variable nodes does not scale w ith the increase of n. So for simulation purposes, we construct the graphs randomly and report the average (over 100 simulation instances) fraction of unverified variable nodes, instead of the success/failure ratio. For the analytical results, based on the fact th a t is a non-increasing function of iteration number £, we consider the following stopping criteria: 1 . Success: < 10~7. 2. Failure: > 10-7 and | a ^ — < 10~8. To calculate the success threshold, a binary search of initial density factors is performed within a certain range including the threshold. The search continues until th e search region is smaller than 10 ~5. C H A P T E R 5. A N A L Y S IS OF NB- V B A L G O R IT H M S O V E R IR R E G U L A R GRAPHS52 Simulation results in this section are divided into two parts. In the first p art, we discuss the accuracy of our analysis compared to th a t of [1]. In th e second p art, we present sim ulation results confirming the accuracy of our asym ptotic analysis over graphs w ith different compression ratio. 5.4.1 P a r ti: C om parison w ith [1] A uthors in [ I] have reported the following degree distribution as an optim ized degree distribution for th e case where all the check nodes have th e same degree (also called right-regular graph), the highest variable degree is 12 , the average variable degree is 3.5 and the compression ratio is 0.5: A(x) = 0.5201a:2+0.182x3+0.09055x4+0.10575x6+0.1007x9+0.00092:12, p(x) = x 7. In [l], the threshold for this case is reported as 0.303. Based on our analysis, we obtain th e threshold of 0.3025 for this ensemble. We have simulated the evolution of for the SBB algorithm vs. iteration number over the reported graph (n = 105) for initial density factors 0.3024,0.3026, and 0.3029. As can be seen in Fig. 5.1, tends to zero only for the first initial density factor and is bounded away from zero for th e other two values. This means th a t the threshold of 0.303 is indeed larger than the success threshold of this ensemble. 0.35 W = 0.3024 = 0.3026 W = 0.3029 0.3 0.25 0.2 0.15 0.1 0.05 100 150 200 250 300 350 I te ra r a tio n N u m b e r (£) Figure 5.1: Evolution of for the SBB algorithm, obtained by finite-length simu­ lation, vs. iteration number I. The evolution is reported for different initial density factors. C H A P T E R 5. A N A L Y S IS OF N B -V B A L G O R IT H M S O V E R IR R E G U L A R G RAPH S53 5.4.2 P art 2: A ccu racy o f th e P ro p o sed A n alysis To investigate th e degree of agreement between our asym ptotic analysis and finitelength simulations, we have presented in Fig. 5.2 the evolution of (for the theoretical results) and the average unverified non-zero variable nodes normalized by n (for th e finite-length results) w ith iterations I for the SBB algorithm . The sensing graph in this case is randomly constructed w ith the degree distribution A(x) = 0.52a;2 + 0.2426a:3 -I- 0.0417a;4 + 0.1957a:8 and p{x) = x 7. This degree dis­ tribution is optimized for a compression ratio of 0.5. The details of the optim ization are further descrribed in Section 6.4.1. T he success threshold associated with this degree distribution is 0.3066. For the simulation, two values of are selected: one above the success threshold (0.307 > 0.3066) and one below it (0.306 < 0.3066). The theoretical results and simulations for n = 105 are shown by dashed lines and solid lines, respectively. As one can see, the sets of results are in close agreement particularly for the cases where is above the threshold and for smaller values of L 0.35 — Simulation Below Threshold -♦-Sim ulation Above Threshold - - - Analysis Below Threshold -♦-Analysis Above Threshold 0.25 0.15 0.05 100 150 200 250 Iteration Number (£) 300 350 400 Figure 5.2: Evolution of a ^ , obtained by the theoretical analysis, vs. iteration num ber I (dashed line) and th a t of the normalized average unverified non-zero variable nodes vs. I for n = 105 (solid line). For th e last simulation, we select the following two degree distribution pairs: Xi(x) = 0.62a:2 + 0.2457a:3 + 0.0619a;6 + 0.0724a:9, px(a:) = a;4 X2(x) = 0.52a;2 + 0.1673a:3 + 0.1054a;4 + 0.2073a;5, p2(x) = x 9 C H A P T E R 5. A N A L Y S IS OF NB- VB A L G O R IT H M S O V E R I R R E G U L A R GRAPHS54 For each degree distribution, we construct three random graphs w ith n = 104, n — 5 x 104, and n — 105 variable nodes. The degree distributions yield compression ratios of 3 /4 and 1/3, and have success thresholds of 0.5390 and 0.1619 under the SBB algorithm , respectively. We run the SBB algorithm over these graphs for different initial density factors. Figure 5.3, plots the average number of unverified variable nodes normalized by n vs. the initial density factor. In this simulation, we impose no lim itation on the number of iterations and the unverified variable nodes are counted when th e algorithm makes no further progress. Clearly, if the recovery algorithm has successfully recovered all variable nodes at this point, the num ber of unverified variable nodes is zero. In each case, the success threshold is dem onstrated by a vertical line on th e figure. The diagonal line represents the function y(x) = x, which serves as the asym ptote for the cases where the initial density factor tends to 1 . As can be seen, th e finite-length results are in good agreement with the theoretical thresholds. Also, as th e dimension n increases, the curves become sharper around the success threshold. a Figure 5.3: Verifying the success threshold of SBB for irregular graphs through finitelength simulations. C H A P T E R 5. A N A L Y S IS OF NB- VB A L G O R IT H M S O V ER IR R E G U L A R G RAPHS55 Table 5.2: Initialization of Param eters for the Analysis of SBB on Irregular G raphs w ith Inputs: X(x), p (x ), . d c ,m ax E w (' - “<0))i"1• ° m =j A(1) =j =' ( t ) (“ <0,) ‘ (i W P i )W = ( l - o ,,|) ( l - B |D |) ‘ , J = 0, • • • . dc - i. < i= l, (l) — j = 0, • ■• . dc - .i. a< » =a<°>. d c .m a x E B - o vy-1. i = 1 , ■• • , . - ’( d c ^ ' L ( d o ) , - E « = o~‘- •• ,d e. . (V) ('4<1))i (! - = ^ ,m a x 1 E ^ d = l d = 1 f ( h R l) ’ d c ,m ax d - 1 v E ^ r. ’w E d = l A T (l,f il) ( d ) = (J _ B ( l ) y d B (l) + (J _ p( 1,m,2)( = ( l ~ g (1)) d p( 1,m,2)r ^ ^ ^0 W AT(l,«l)(d) ’ Kl W p (l,R l,2)^ = Q 2 < i < d . d u ,m a x CP) = 1 - j= 0 ^ ( a (2) = a (l) ( 1 - ^ ) (1 - B ^ r 1 N ^ RV{d) <^ri,max ------ ^ ----------------------------------_ J = L _ -----------------------------------(i _ /(i,* P ) « v ,m 4 x t u v ,m a jc t ' E E« - *)WX-”*w E E« t= l j = 1 i= l pM « j( d=) = G) (C ' T “ * t 1 ~ C (1)) \ j= l 2 < > < d c, 0 < k < i , 0 < j < d c-i. d v ,m & x E vf'i-g^w < " J ( d=) = s d r ; pm “> c) =■1 - C W ’ E <« • - p kT V d c). i —2 dc z. dc.max i—k d—1 E ^E ^rw ° m = . Z ' r i , ■ E /xE E iC M ____________ d = l t —0 j = l ______________________ ' C H A P T E R 5. A N A L Y S IS OF N B -V B A L G O R IT H M S O V E R I R R E G U L A R GRAPHS56 Table 5.3: Recursive Formulas for the Analysis of SBB over Irregular G raphs for £ > 2, F irst Round - dv,max HR1 1) = j- £ 2) 3) dA„(l - d = l v , 1 < i < dc, 0 < j < d c - i , Q < k < j . = (fc) (^4W) fc (! “ dc- 1 P # £ 1,1,+ )( d c ) 1^ = rfc < ^ .m a x , 0 < fc < dc - 1. 1 < dc < dc,m ax , 0 < fc < d c - 1. j= k P % ™ ' 1 ,C )( d c ) = £ p J 5 r j ,H2’1 , C ) ( d c ) ^ i ( 4 ) , j= k dc i 1 < ^ < <4 ,m ax , 2 < i < dc, 0 < k < dc - i. j —k ^c,max d—1 HR2 1) flW = £ £ * # g £ A+,( - / <,,“ '+)) • pgm'2,C)(d)=jV(J1)(d)pgr1,,g,a)wpg^l)w(i P‘i f'-2)(d) = 0, 6) J - 2. ■■■,d. = a ^ N ^ l,R1^(d). ■ « M 'c , w C H A P T E R 5. A N A L Y S IS OF NB- VB A L G O R IT H M S O V E R IR R E G U L A R G RAPH S57 Table 5.4: Recursive Formulas for the Analysis of SBB over Irregular G raphs for I > 2, Second Round HR1 1) C«> = 1 - 1 . 1 ,------ * --------------------- - (1 - /('■“ '+)) \r- ' v ' ' , . .v. E i=i i= l j= l .m a x d v .m a x E (i - E ( l _ y(<,Hl,C7) j _ d v ,m a x i d v , m ax E £ «- w i E £ («- i= i 7=1 2) P ^ 2] ( 4 ) = (D (C 'W) i_fc( l - C ' W) fc> l < d c < d c m 0 < k < i, »=i 7=1 2 < i < d c, 0 < j < dc — i. d v ,m a x P ^ ' l'+)(dc) n (£ ,R 2 ,+ ,F ) ( j "MA»*< \ E d = l „(f,.R2,+,0) M,« f p ^ 1'RX'2){ d ) P ^ l \ d ) d—1 t“cj — j»>v,max “ u ,m a x oa E ]T Ada ^ i 0 + (* - i ) 7 ^ - 1’m , 2)(^ )p £ ^ 1)( ^ ) *=1 *.(£,^1,1,+) “ % ,i „(f,.R2,+,F) “ di^max „(*,i*21CIF ) , J *vM A da d V K l ^(f.iil.l.C )^ N - p Mii (rfc) 2 ^ W ^C m W d=1 E p ^ ' c ' ° \ d c) = p ^ ! x c \ d c) - p % p ’F\ d c). 3) P$™'X\ d c) = 2 < k - ptfrrnxoyj = pi‘W.c,F){de) + p(«,«2,+,F)(4)i p ^ 2’i!( 4 ) = +Y C 1’^ ) o < j < d c - 1. 1< J < 4 - 1. + p & ? 'c '0 )( 4 ) + p ^ 2'+'0 )( 4 ) 1G ‘‘'''I M r ’^ l !d- h 0 < j < d c - 1. i=2 d c ,,m m aa x e HR2 1) D& d —1 ^ E ^ r ’w = — — -----------<*c, m a x d d —t . E ^ i=0 E E ^ 'V ) d= 1 J= 1 2) P%f2'2,(d) = (f)(D«>)‘ ( 1 -£ > WG ‘ , 3) P ^+1) (d) = /'a IiIII'a "2'2' (d) ■ 0 , T )]. It would be interesting to examine the application of differential evolution to the design of irregular sensing graphs in the context of compressed sensing. As p art of such study, one would need to prove th a t certain param eters in the recovery algorithm rem ain alm ost unchanged when the input param eters to the recovery algorithm changed slightly. W hen using irregular sensing graphs, we observed th a t for a fixed compression ratio, increasing the average variable degree increases the success threshold as well. However, this is achieved at the expense of higher recovery complexity. Two interest­ ing research paths emerge here: first to find the highest success threshold th a t can be achieved for a fixed compression ratio using irregular graphs as sensing graphs and NB-VB algorithm s as the recovery algorithm when the average variable degree (and consequently the average check degree) is allowed to go to infinity. In this context, the issue of th e design of the sequences of irregular graphs th a t can achieve th e ultim ate performance is also interesting. Second to look at the trade-off between th e running tim e, recovery complexity and the success threshold in the context of irregular graph design. In this case, new measures need to be devised th a t capture this trade-off and allow the design of optim al degree distributions. The verification rules in the NB-VB algorithm s are devised for th e noiseless mea­ surements. Using thresholding techniques presented in this work, NB-VB algorithm s can be applied to noisy measurements if th e power of noise in the m easurem ents is much less th an th e signal power (very high SNR regime). In order to make NB-VB algorithm s more robust against the noise in the measurements one way is to design verification rules th a t can explicitly cope w ith the noisy measurements. Even in the case of high SNR, one interesting research p ath would be to find th e optim al value for the thresholds t\ and e2 introduced in Section 4.7 as functions of density factor, SNR, and possibly other design param eters, such as the compression ratio. It would also be interesting to formulate some practical application scenarios so th a t they can be solved by the application of NB-VB recovery algorithm s. L ist o f R eferen ces [1] F. Zhang and H. D. Pfister, “Analysis of verification-based decoding on th e qary symm etric channel for large q,” IE E E Trans. Inform. Theory, vol. 57 (10), pp. 6754-6770, 2011. [2] W. Xu and B. Hassibi, “Efficient compressive sensing with determ inistic guar­ antees using expander graphs,” in Proc. Inform ation Theory Workshop (I T W ), pp. 414-419, September 2007. [3] E. J. Candes and M. B. Wakin, “An introduction to compressive sampling,” IE E E Signal Processing Magazine, vol. 25, pp. 21-30, March 2008. [41 D. Donoho, “Compressed sensing,” IE E E Trans. Inform. Theory, vol. 52 (4), pp. 1289-1306, April 2006. [5] E. Candes, J. Romberg, and T. Tao, “Robust uncertainty principles: E xact sig­ nal reconstruction from highly incomplete frequency inform ation,” IE E E Trans. Inform. Theory, vol. 52 (2), pp. 489-509, February 2006. [6 ] Y. Wu and S. Verdu, “Fundam ental limits of almost lossless analog compression,” in Proc. IEE E Int. Symp. Inform ation Theory (ISIT ), pp. 359 - 363, 2009. [7] R. G. Baraniuk, “Compressive sensing,” IE E E Signal Processing Magazine, vol. 24, pp. 118-124, July 2007. [8 ] J. Tropp, Topics in Sparse Approximation. PhD thesis, University of Texas at Austin, 2004. [9] R. Berinde, A. G ilbert, P. Indyk, and K. Strauss, “Combining geom etry and combinatorics: A unified approach to sparse signal recovery,” in f6 th Annual Allerton Conference on Communication, Control, and Computing, pp. 798-805, Septem ber 2008. [10] J. Tropp and A. Gilbert, “Signal recovery from random m easurem ents via or­ thogonal m atching pursuit,” IE E E Trans. Inform. Theory, vol. 53 (12), pp. 46554666, December 2007. [11] D. Needell and R. Vershynin, “Uniform uncertainty principle and signal recov­ ery via regularized orthogonal m atching pursuit,” Foundations o f Computational Mathematics, vol. 9 (3), pp. 317-334, June 2009. [12] S. Mendelson, A. Pajor, and N. Tomczak-Jaegermann, “Uniform uncertainty principle for Bernoulli and sub-Gaussian ensembles,” Constructive Approxim a­ tion, vol. 28 (3), pp. 277-289, December 2008. 66 67 [13] R. Baraniuk, M. Davenport, R. DeVore, and M. Wakin, “A simple proof of the restricted isometry property for random m atrices,” Constructive Approximation, Springer New York, vol. 28, pp. 253-263, December 2008. [14] E. Candes and T. Tao, “Decoding by linear program ming,” IE E E Trans. Inform. Theory, vol. 51 (12), pp. 4203 4215, Dec. 2005. [15] V. C handar, “A negative result concerning explicit matrices with the restricted isom etry property,” tech. rep., 2008. [16] G. Cormode and M. M uthukrishnan, “Combinatorial algorithm s for com­ pressed sensing,” in Proc. Structural Inform ation and Communication Complex­ ity (SIROCCO), pp. 280-294, 2006. [17] P. Indyk, “Explicit constructions for compressed sensing of sparse signals,” in Proc. Symp. on Discrete Algorithms (SODA), pp. 30-33, 2008. [18] A. C. G ilbert, M. J. Strauss, J. A. Tropp, and R. Vershynin, “Algorithmic linear dimension reduction in the £i norm for sparse vectors,” in f f t h Annual Allerton Conference on Communication, Control, and Computing, 2006. [19] A. C. G ilbert, M. J. Strauss, J. A. Tropp, and R. Vershynin, “One sketch for all: Fast algorithm s for compressed sensing,” in Proc. 39th A C M Sym posium on Theory of Computing (STOC), pp. 237-246, 2007. [20] S. Sarvotham , D. Baron, and R. Baraniuk, “Sudocodes - fast m easurem ent and reconstruction of sparse signals,” in Proc. IE E E Int. Symp. Inform ation Theory (ISIT ), pp. 2804-2808, July 2006. [21] V. Chandar, D. Shah, and G. W. Wornell, “A simple message-passing algorithm for compressed sensing,” in Proc. IE E E Int. Symp. Information Theory (ISIT ), pp. 1968-1972, June 2010. [22] F. Zhang and H. D. Pfister, “On the iterative decoding of high rate LD PC codes w ith applications in compressed sensing,” Submitted to IE E E Trans. Inform. Theory. [23] F. Zhang and H. D. Pfister, “Compressed sensing and linear codes over real num bers,” in Proc. Inform ation Theory and Applications Workshop, pp. 558561, February 2008. [24] F. Zhang and H. D. Pfister, “List-message passing achieves capacity on th e q-ary symm etric channel for large q,” in IE E E Global Telecom. Conf. ( GLOBECOM ), pp. 283-287, November 2007. [25] Y. Lu, A. M ontanari, B. Prabhakar, S. Dharm apurikar, and A. K abbani, “Counter braids: A novel counter architecture for per-flow m easurem ent,” in Proc. Int. Conf. on Measurement and Modeling o f Computer Sys. A C M SIGM ETRIC S, pp. 121-132, June 2008. [26] M. Akcakaya, J. Park, and V. Tarokh, “Low density frames for compressive sensing,” in Proc. IE E E Int. Conf. Acoustics, Speech, and Signal Processing (IC ASSP ), pp. 3642-3645, March 2010. 68 [27] D. Baron, S. Savotham, and R. G. Baraniuk, “Bayesian compressive sensing via belief propagation,” IE E E Transactions on Signal Processing, vol. 58 (1), pp. 269-280, January 2010. [28] A. Abdelkefi, Y. Jiang, W. Wang, and A. K vittem , “Robust traffic anom aly detection with principal component pursuit,” in Proc. 6th A C M Int. Conf. on emerging Networking Experim ents and Technologies (C oN E X T) Student Work­ shop, 2010 . [29] Y. Lu, A. M ontanari, and B. Prabhakar, “Counter braids: A sym ptotic optim ality of the message passing decoding algorithm ,” in 46th Annual Allerton Conference on Communication, Control, and Computing, pp. 209 216, Septem ber 2008. [30] J. Meng, W . Yin, H. Li, E. Houssain, and Z. Han, “Collaborative spectrum sensing from sparse observations using m atrix completion for cognitive radio net­ works,” in Proc. IE E E Int. Conf. Acoustics, Speech, and Signal Proc. (IC ASSP ), pp. 3114 - 3117, March 2010. [31] R. Heckel and H. Bolcskei, “Compressive identification of linear operators,” in Proc. IE E E Int. Symp. Inform. Theory (ISIT ), pp. 1412-1416, August 2011. [32] A. M ontanari and D. Tse, “Analysis of belief propagation for non-linear prob­ lems: The example of CDMA (or: How to prove tanaka’s form ula),” in Proc. Inform ation Theory Workshop (IT W ), pp. 160-164, March 2006. [33] D. Guo and C.-C. Wang, “M ultiuser detection of sparsely spread CD M A,” IE E E Journal on Selected Areas in Communications, vol. 26 (3), pp. 421-431, April 2008. [34] D. Guo, D. Baron, and S. Shamai, “A single-letter characterization of optim al noisy compressed sensing,” in 47th Annual Allerton Conference on Com munica­ tion, Control, and Computing, pp. 52-59, O ctober 2009. [35] C. P. Robert, The Bayesian Choise: A Decision Theoretic Motivation. SpringerVerlag, 1994. [36] C. C. Paige and M. A. Saunders, “LSQR: Sparse linear equations and least squares problems,” A C M Transactions on Mathematical Software (TO M S), vol. 8 , pp. 195-209, June 1982. [37] D. Donoho, A. Javanm ard, and A. M ontanari, “Inform ation-theoretically opti­ mal compressed sensing via spatial coupling and approximate message passing,” in Proc. IE E E Int. Symp. Inform. Theory (ISIT ), 2012. [38] D. Donoho, A. Maleki, and A. M ontanari, “Message passing algorithm s for com­ pressed sensing,” Proc. o f the National Academy o f Sciences (P N A S), vol. 106 (45), pp. 18914-18919, 2009. [39] M. Luby and M. Mitzenmacher, “Verification-based decoding for packet-based low-density parity-check codes,” IE E E Trans. Inform. Theory, vol. 51 (1), pp. 120-127, January 2005. 69 [40] Y. Eftekhari, A. Heidarzadeh, A. H. Banihashemi, and I. Lam badaris, “Den­ sity evolution analysis of node-based verification-based algorithms in compressed sensing,” IE E E Trans. Inform. Theory, vol. 58 (10), pp. 6616-6645, O ctober 2012 . [41] Y. Eftekhari, A. Heidarzadeh, A. H. Banihashemi, and I. Lam badaris, “A n effi­ cient approach toward the asymptotic analysis of node-based verification-based algorithm s in compressed sensing,” in Proc. IE E E Int. Symp. Inform. Theory (ISIT ), 2011. [42] Y. Eftekhari, A. H. Banihashemi, and I. Lambadaris, “Analysis and design of irregular graphs for node-based verification-based algorithms in compressed sens­ ing,” in Proc. IE E E Int. Symp. Inform. Theory (ISIT ), 2012. [43] T. J. Richardson and R. L. Urbanke, “The capacity of low-density parity-check codes under message-passing decoding,” IE E E Trans. Inform. Theory, vol. 47 (2), pp. 599-618, February 2001. [44] D. J. MacKay, Inform ation Theory, Inference, and Learning Algorithms. Cam ­ bridge University Press, 2003. [45] M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. A. Spielman, “Efficient erasure correcting codes,” IE E E Trans. Inform. Theory, vol. 47 (2), pp. 569-584, February 2001. [46] C. Berrou and A. Glavieux, “Near optimum error correcting coding and decoding: turbo-codes,” IEE E Trans. Comm., vol. 44 (10), pp. 1261-1271, O ctober 1996. [47] Y. Eftekhari, A. Heidarzadeh, A. H. Banihashemi, and I. Lam badaris, “Den­ sity evolution analysis of node-based verification-based algorithms in compressed sensing,” Tech. Rep. SCE-11-07, Carleton University, 2011. [48] E. Candes, J. Romberg, and T. Tao, “Stable signal recovery from incomplete and inaccurate m easurements,” Communications on Pure M athematics, vol. 59, pp. 1207-1223, August 2006. [49] M. Bayati and A. M ontanari, “The dynamics of message passing on dense graphs, with applications to compressed sensing,” IE E E Trans. Inform. Theory, vol. 57 (2), pp. 764-785, February 2011. [50] H. L. V. Trees, Detection, Estimation, and Modulation Theory, Part I. John Wiley & Sons, 2001. [51] E. Candes and J. Romberg, “Llm agic,” in Available online at: http://w w w stat.stanford.edu/ candes/llm agic/, October 2005. [52] E. Candes, M. Wakin, and S. Boyd, “Enhancing sparsity by reweighted 11 min­ imization,” The Journal o f Fourier Analysis and Applications, vol. 14, pp. 877905, December 2008. [53] D. Donoho and J. Tanner, “Thresholds for th e recovery of sparse solutions via 11 m inim ization,” in Proc. fOth Annual Conference on Information Sciences and System s (CISS), pp. 202-206, March 2006. 70 [54] H. Saeedi and A. H. Banihashemi, “System atic design of low-density parity-check code ensembles for binary erasure channels,” IE E E Trans. Comm., vol. 58 (1), pp. 118—127, 2010 . [55] H. Saeedi and A. H. Banihashemi, “On the design of irregular LD PC code ensem­ bles for BIAWGN channels,” IE E E Trans. Comm., vol. 58 (5), pp. 1376-1382, 2010 . [56] H. Saeedi and A. H. Banihashemi, “New sequences of capacity achieving LDPC code ensembles over the binary erasure channel,” IE E E Trans. Inform. Theory, vol. 56 (12), pp. 6332-6346, 2010. [57] K. Price and R. Storn, “Differential evolution a simple and efficient heuristic for global optim ization over continuous spaces,” Journal of Global O ptim ization, vol. 11, p. 341359, 1997. [58] A. Shokrollahi and R. Storn, “Design of efficient erasure codes w ith differential evolution,” in Proc. IE E E Int. Symp. Inform ation Theory (ISIT ), pp. 5-5, June 2000 . [59] T. J. Richardson, M. A. Shokrollahi, and R. L. Urbanke, “Design of capacityapproaching irregular low-density parity-check codes,” IE E E Trans. Inform. Theory, vol. 47, pp. 619 - 637, 2001. A p p e n d ix A A n a ly sis o f N B -V B A lgorith m s for R egu lar G raphs A .l A ssum ptions In our analysis, we often use two assumptions: “uniformity assum ption” and “inde­ pendence assum ption” . Both assumptions are natural consequences of the random ­ ness of th e graph and the input as well as the asym ptotic nature of the analysis. The uniformity assum ption states th a t all the possible choices w ithin the constraints imposed by th e event under consideration are equally likely. As an example, consider th e Genie algorithm and the case, where an edge is connected to a variable node with i connections to check nodes with /C-degree 1 , and thus dv — i connections to the check nodes w ith other values of fC-degree. Now, suppose th at we are interested in calculating the probability th a t the other end of such an edge is connected to a check node of /C-degree 1. The uniformity assum ption implies th a t this probability is equal to i / d v. The independence assumption, on the other hand, states th a t all the edges of a certain type, carry independent messages. In our analysis such messages are often identically distributed as well. As an example, consider a check node w ith JC-degree j and suppose th a t th e probability th a t this node receives a verified message along each of th e j edges is p. Then the independence assum ption implies th a t the number of verified messages th a t this node receives has a binomial distribution. One should note th a t th e independence assum ption here is different from the sim ilar assum ption made for the density evolution analysis of MB algorithms. The latter requires the extrinsic nature of message passing and implies th a t all th e messages, each originating from non-overlapping leaves on a tree-like neighborhood of an edge are independent. The former however does not require the message passing to be extrinsic and is a consequence of the random perm utation of edges between the variable nodes and the check nodes. 71 A P P E N D IX A. A N A L Y S IS OF N B -V B A L G O R IT H M S FO R R E G U L A R GRAPHS72 A .2 Genie For th e analysis, we assume to have the probabilities a^e\ P are interested in deriving the same probabilities for iteration I. A .2.1 and P^~1,2\ and U p d a te eq u ation s for £ -H R l, i > 2 (C a lcu la tio n o f W hen a variable node is verified in HR2 of an iteration, th e dv edges adjacent to the variable node carry the recovery message to the neighboring check nodes. These check nodes thus face a reduction in their AC-degree. We denote by Pj^jU the probability th a t the AC-degree of a check node is reduced from j to i < j after HR1 of iteration £. This happens if out of j edges em anating from the check node and incident to the set of unverified variable nodes KSl\ j — %of them now carry a message from their variable nodes indicating th at they have been verified. On the other side of the graph, when a variable node in ACj*~1,2^ (1 < i < dv) is verified, by definition, out of dv check nodes receiving the recovery message, i have AC-degree 1 and dv —i have AC-degrees larger th a n 1. For each verified variable node, th e set of i check nodes of degree 1 are distributed uniformly w ith respect to th e set of all check nodes of degree 1. Based on the operation of the Genie algorithm , it is easy to see th at p 'Z , = 0 a n d = 1■ Furtherm ore, one may assume th a t the remaining dv — i edges carrying a verified message are uniformly connected to the check nodes w ith AC-degrees larger th a n 1. Based on this assum ption, we derive P$jU for j > 1 . Once these probabilities are found, the new distribution of check node degrees P^ probability law: o < i P m 1’ = can be derived using the total < d c. j=i To find th e probability Pj^fjU, 2 < j < dc, we need the conditional probability th a t an edge connecting a check node in the set 2 < j < dc, and an unverified variable node, carries a verified message to the check node in the first half-round of (t\ iteration I. We denote this conditional probability by P^>i- Assuming this probability is known, for 2 < j < dc and 0 < i < j we have: (£) The probability P can be com puted as follows. In th e following, se is the statu s bit of the message sent from v to c over the edge e = (n, c), and pW is defined as the A P P E N D IX A . A N A L Y S IS OF NB- V B A L G O R IT H M S FO R R E G U L A R GRAPHS73 probability of an edge e being adjacent to a check node c G A f^ 1’1^ conditioned on the fact th a t it is adjacent to a variable node v G KSl~l\ P dh = P r [se = l|c € A/jf_1,1), v G t C ^ ] 3=2 j = 2 i—1 = V S ' 1 -------- _ — U j- 2 Pr[c G L f c i - A / J V e £ (£_1)] * ( i - Pr[c 6 S ' p ^ — p ( £) |„ e ack-D] |>*T'2) - E i^ r 1,2’ 1 - P(t) ( l - Pr[c G A/j(<_1,1) |i> G 1 —p £< ~ ~ 1 , 2 )' — ____ !£° 1- p W where, G^f-i,2)]) rg-1* ! x Pr(„ € K (a i\ —i _ 1 - p W { ’ can be calculated as: p (t) \v ._ p r|c ^ g /C(<_1)] _ Pr[u G /C^_ p |c G A /^-1,1^] Pr[c GA/’i <~1,p] Prju G — x n^~^A) dc A .2.2 M a(e~ P (f—i i'i = Pm ’ } a(e~Vdr (A.2) U p d a te eq u ations for ^-H R 2, £ > 2 (C a lcu la tio n o f pj£’2^ and a ^ +1^) In th e second half-round, variable nodes receive messages from their neighboring check nodes. According to the verification rule in the Genie algorithm , the only unverified variable nodes are those in the set /C^~1,2\ Variable nodes in this set have no connection to check nodes in the set A b u t dv connections to the sets {Af% 1,1\ • • • , A/’j*-1,1^}. Suppose v G X q ~1,2\ In this case, if j out of dv adjacent check nodes of v in {A/^- , • • • ,A f^ ~ 1'1^} move to Affe,1\ v will move from K,q ~1,T> to 1C*j'2\ This is shown in Figure A.I. We define the probability Pjc^.. as the probability of a variable node v G JCq ~1,2^ A P P E N D IX A. A N A L Y S IS OF N B -V B A L G O R IT H M S FOR R E G U L A R GRAPHS74 i-2 Figure A .l: A variable node in /Co moves to IC j. moving to fC)e'2\ We thus have: d v - j , o< j < dv, (A-3) where /£P x’ J 2}is defined as the probability th a t an edge adjacent to a variable node v E K0 carries a message indicating th a t the adjacent check node c has a degree equal to 1, i.e., c E A f f ' 1^. The probability P ^ is calculated as follows: P{xe) = Pr[c € A/’1(£,1)|u E /C?~1,2)] Pr[c E A/x*’1^] Pr[t> E /Co<_1’2^|c E A/x*’1^] ( O ) x — PMi d, W a p (e,i) Mi a^dc (A.4) where is given in (A.2 ). In th e Genie algorithm, the probability of a variable node in the set being verified is calculated as Therefore, the probability of a variable node v rem aining unverified, i.e., v E KSt+1\ is: d>\) a (‘+1> = 1 - $ > £ 2) = a (e¥ * f . i= 1 A .2.3 In itia l prob abilities for th e G enie algorith m (£ = 0 and 1 = 1) Assuming an initial density factor of 1 —cd°) fraction of the edges from variable nodes in th e first iteration carry a recovery message to check nodes. Since a t iteration A P P E N D IX A. A N A L Y S IS OF N B -V B A L G O R IT H M S FO R R E G U L A R GRAPHS75 zero^ no variable node in th e support set — is *---------3 verified, '•we ---have“ ” — ~---rr — • Moreover, —7 0 ,1) Pd>l = 1 — and Ptf'P is thus given by the Ac = 1- T he set of probabilities following. (1,1) __ „(0,1) (1) __ „(1) Ptfi ~ pMdc pMdcll ~ pMdcli -( * * .,) ( « . r o - « , y = («<'>)* (1 - a*1’) * - ' , 0 < i < dc. To find th e probability P % f\ we first find the probability replace it in (A.3). A .3 from (A.4) and then XH As before, we assume to have th e probabilities c*^, P^f~l,1\ and and are interested in deriving the same probabilities for iteration i. Since in the analysis of XH we only track th e probability of unverified non-zero variable nodes, th e analysis will include only one round with two half-rounds ju st like the analysis for the Genie. A .3.1 U p d a te eq u ation s for £ -H R l, I > 2 (C a lcu la tio n of Pm? ) W hen a variable node in (\d v/2] < i < dv) is verified, by definition, o u t of dv check nodes receiving the recovery message, i have /C-degree 1 and dv — i have AC-degrees larger th an 1. For each verified variable node, the set of i check nodes of degree 1 are distributed uniformly with respect to the set of all check nodes of degree 1. It is easy to see th at Ki (£) *=\dv/i\ N l] = 1 - P 1,2) i=0 Furtherm ore, one may assume th a t the rem aining dv — i edges carrying a verified message are uniformly connected to the check nodes w ith /C-degrees larger th an 1 . A P P E N D IX A. A N A L Y S IS OF N B -V B A L G O R IT H M S FOR R E G U L A R GRAPHS76 Following the same approach as the one presented for the Genie, we have: P%u = ( j i ;) (p™i)J (' ~ p™')’ ’ 2 - j S ia p 'k = T , p<' V ' )pM»<' J=i 0 - * - >■ 0 < i < rf,, (f\ where, Pd>x denotes the conditional probability th a t an edge connecting a check node in the set A /^_1,1\ 2 < j < dc, and an unverified variable node, carries a verified message to th e check node in th e first half-round of iteration £. Following the same path for the derivation of Equation A .l, we have: E i= 0 where, l ' j r . 1 - p(t) • 1 is calculated as in A.2. U p d a te eq u ation s for £-H R 2, £ > 2 (C a lcu la tio n of Pfc’2^ and a ( £+1)) A .3.2 In the second half-round, variable nodes receive messages from their neighboring check nodes. According to th e verification rule in th e XH algorithm, th e unverified variable nodes are those in the set (J r}- We define the probability as th e probability of a variable node v € K,f~~1'2^ moving to K ^ '2^. We thus have: r) = (o '0*)' (1 - o '01) * " ' . Hence, th e probability th a t a check node c has a value equal to zero (c = 0) is: Pr[c = 0] = = (l - a (0)) dc. (0 fi2 21 Let A j ’ denote the set of zero-valued variable nodes that receive j zero-valued /q 2) messages. The probability P ^ ’ ’ ; defined as the probability th a t a zero-valued vari­ able node belongs to the set A ^°’’R2,2'1 is calculated as follows: p(o,®,2) = pr[ti g e A (0)] = (')) (i'?)1(' - if‘'T ’ ° s i s < a e) where is the probability th a t an edge adjacent to a zero-valued variable node is also connected to a check node with value equal to zero. This happens if the other dc — 1 variable nodes adjacent to the check node are all zero-valued. Therefore, is calculated as follows: p f := Pr[ce E A fP \v e E A (1)] = (l - <*(0)) dc_1. (A.7) Let p P := Pr[u E A^)] denote the probability th a t a variable node has a zero value b u t is not verified in R2-HR2 of iteration zero. Based on (A.6 ) and (A.7), we have: p P = Pr[u G A (0)] Pr[u G a £0,'R2’2 )| u G A (0)] = (1 - a m ) ( l — (1 —a<°>)de" 1) d” . A .4.3 (A . 8 ) Itera tio n one, R 1-H R 1 (R egrou pin g o f check n o d e s in se ts A f i j based on th e in d ex j ) Based on th e recovery process at iteration zero, all verified variable nodes are in the sets A j, 1 < j < dv. The processing of verified messages sent from these variable nodes to check nodes at iteration 1, R1-HR1 results in some check nodes to move from A/’(^ R2,1) to A 1 < i < dc, 0 < j < dc —i. The set of such check nodes is denoted by A an(l we are interested in the probability th a t a check node belongs to this set. Let PeR denote the probability of an edge in th e set of A-edges carrying a verified message. Such edges are not connected to the set A0. Let ve and ce denote the A P P E N D IX A. A N A L Y S IS OF N B -V B A L G O R IT H M S FOR R E G U L A R GRAPHS79 variable node and the check node connected by edge e. We thus have: peRm) := 1 “ P r be e A<°’* 2,2)|ue 6 A (1),ce £ A/J1}] _ 1 _ Pr[ue E A 0|ue E A (1)] Pr[ce £ Nfp^lve € A 0] Pr[ce £ AfQl)\ve E AP)] . p k r ’2 ) x i 1- p f . pg} 1 _ p ( 0) ’ where and P ^ are given in (A. 8 ) and (A.7), respectively. Moreover, for 1 < i < dv and 0 < j < dc — i, (1.H 1) d c -ilj (dc; !) Hence, pU.m.U = AAA . (A. 9 ) Itera tio n one, R 1-H R 2 (V erification o f variab le n od es based on D 1 C N ) In R1-HR2, received messages from check nodes are processed at variable nodes. At this stage, a check node in the set ■A/"io'R1’P transm its a message w ith its first coordinate equal to 1 , making it possible for variable nodes in th e support set to be verified according to D1CN rule. We partition the set of all variable nodes in into subsets 0 < i < dv, where i denotes the number of received messages w ith the first coordinate equal to 1 (refer to Fig. 4.2a for more inform ation). We denote the set of such variable nodes by Let denote the probability th a t an edge adjacent to a variable node in the support set carries a message with th e first coordinate equal to 1. Using the same notations ve and ce defined above, we have: p (i,m) P rjCe G ^ ( i , * 1.1) 1^ e ^(i)] Pr[ce E ^ y U ) ] P r K € JC^\ce E A /g /* 1'1*] Pr[ue E /C(P] x \/d c p f t" * 1’ A P P E N D IX A. A N A L Y S IS OF N B -V B A L G O R IT H M S FOR R E G U L A R GRAPHS80 0 < i < dv, th a t a variable node v G JC^ belongs to Hence, th e probability th e set /cj1,'R1’2) is calculated as follows: = p{i £ ) ;= Pr{v e € ^(D) = ( t ) (p{1'm ) Y (i ( a . 11 ) Based on the D lC N rule in the LM algorithm, variable nodes in th e set are verified. Therefore, th e probability th a t a variable node in the support set rem ains unverified for iteration 2 is as follows: QP) = Q<.) Y - | > S ! ; ' iU )Y A .4.5 Itera tio n one, R 2-H R 1 (R egrou p in g o f check n o d es in sets A f i j based on th e in d ex i ) Since some variable nodes in th e support set have been verified in R1-HR2, a check node in th e set A m i g h t move into the set Afj]^R2,1^ in R2-HR1. This happens if from %edges in the set of /C-edges adjacent to the check node, i — j of them carry a verified message. The set of such check nodes are denoted by A/^*’^ and we are interested in the probability th a t a check node belongs to this set. /1 DO) Let Pd ’ denote the probability th a t a /C-edge carries a verified message. We have: p f ™ := Pr[„« _ £ JC<», Pr[ue G AC0 \ve G /C(1)] Pr[ce £ A/i.oK G /C0] Pr[ce i A /Y ok e /CCD] [ x 1 I _ p ^0________ ~~ 1_ PA^'m '2) -'Q_____ 1__ ~ i _ p (l,Rl) ’ where P ^ m ’2^ and p ^l,R^ are given by (A. 11) and (A . 10 ), respectively. Hence, the probability P j j ^ l , 2 < i < dc, 0 < j < i ,0 < k < dc —i, th a t a check node belongs to th e set M ^ jR2) is calculated as follows: p ( l , R 2)^ j _ p( i , m y Note th a t we have p f y ^ l = 1 and P § ^ \ = 0. After the regrouping, the probability P ^ R^ ' l\ 0 < j < dc,0 < k < dc — i, th a t a check node belongs to th e set A/^.’^ 2,1^ is A P P E N D IX A. A N A L Y S IS OF N B -V B A L G O R IT H M S FOR R E G U L A R GRAPHS81 calculated by: dc (1,R1,1) (1,7?2,1) _ (1,K2) t=3 A .4.6 Itera tio n one, R 2-H R 2 (V erification o f variab le n od es b ased on Z C N ) The measurem ent corresponding to check nodes in the set A/^1^ 2’1^, 1 < k < dc — 1, changes to zero, as such check nodes are no longer connected to unverified variable nodes in the support set. Hence, the messages transm itted by such check nodes have their second coordinate equal to zero, which in tu rn verifies some variable nodes (in the set A) at R2-HR2 of iteration 1. To find th e probability th a t a zero-valued variable node is verified at this stage, we need th e probability P ^’R2^ th a t an edge adjacent to a zero-valued variable node carries a message with value zero. This probability is calculated as follows: d c- 1 p (i,«2) = ^ p r[C e e ^ ( i , W )|?;eG A (1)] j=i Y Pr[Ce G A /g1*2'1*] Pr[ve e A™ \ce G A/£■“ ’ 3 =1 Y Y Prlce e A /g ’*2,0] Pr[ue e A (1)|ce e A /g ’*2,1*] i=0 j =1 dc-l dc dc—1 / d c- 1 . \ / •\ EEC’i i=0 j =1 \ c/ dc dc—1 i=0 (A. 12 ) -=1 We then, for 0 < i < dv, have: ^ (i,« 2 )y ^ _ p (l,R2)^ dv—t p Qja,2) _ Lastly, th e probability th a t a variable node is zero-valued and rem ains unverified for iteration 2 is calculated by: «(2) _ d(1)d(1,J*2,2) rA — y Ao A P P E N D IX A. A N A L Y S IS OF N B -V B A L G O R IT H M S FO R R E G U L A R GRAPHS82 A .4 .7 Itera tio n tw o and b eyon d The analysis of the second iteration and beyond is similar to th a t of iteration one, and hence om itted. The summ ary of the formulas can be found in Table 4.8. A .5 SBB In this section, we adopt the notation A/i, with any superscript, to denote th e set I \de^ U j= o A f- A .5.1 Itera tio n zero The analysis for iteration zero is the same as th a t of the LM algorithm discussed in P art A.4.1 of the appendix, and is thus not repeated here. A .5.2 Itera tio n one, R 1-H R 1 (R egrou p in g o f check n o d es in sets A f i j b ased on th e in d ex j ) The analysis of R l-H R l for SBB and LM are the same. appendix.) A .5.3 (See P art A.4.3 of the Itera tio n one, R 1-H R 2 (V erification o f variab le n od es based on D 1 C N and E C N ) In R1-HR2, the variable nodes in the support set are verified based on D1CN and ECN rules. Therefore, based on received messages from check nodes, we partition the support set JC(1) into subsets /C,-1,jR1\ 0 < i < dv, where %denotes the num ber of neighboring check nodes in the set (refer to Fig. 4.‘2 b for more information). We denote the set of such variable nodes by This set shall serve as an interm ediate set th a t reflects the processing of messages from check nodes but does not reflect th e verification of support set elements. Let denote the conditional probability th a t an edge e is adjacent to a check node in the set given th a t it is adjacent to a variable node in the support set. We then have: pr[Ce e Af^’m'l)\ve e £ (1)] Pr[ce € A/?1'*1,15] Pr[ue e fC ^ \c e e Pr[ue € /CW] d c —1 j = 0 i I j dc —1 j = 0 A/i(1,H1,1)] A P P E N D IX A . A N A L Y S IS OF NB- V B A L G O R IT H M S FOR R E G U L A R GRAPHSS3 Hence, pf?'” ) = f ^ o" ) := Pr(u € K '1'''11:.) e £<>>), = ( p V ^ y (1 , 0 < i < dv. (A .14) Based on th e ECN rule, variable nodes in the set {J*l2 /C,-1,m^ are verified. A fraction / ( 1,R1) of variable nodes in the set /C[1,m^ th a t receive a message w ith th e first co­ ordinate equal to 1 are also verified based on the D lC N rule. This fraction isequal to: = Pr[Ce € 6 ce E M}°’R2’2)]. By om itting the superscripts for simplicity, and noting Pr[ce E A/i|ce E N \ f i , v e E /Ci] = 1 , we have: ,(i,.ri) _ Pr[ce € A/'i.o] P r K € fCi\ce E A/j,0] Pr[ce E A/i] Pr[ue e /Ci|ce E A/i] p" '» dn P* x 4 M Therefore, th e probability th a t a variable node in the support set rem ains unverified for iteration 2 is calculated as follows: a <2) = a W i dv _ \ Rl) ' t= 2 + C1 - / (1’iil))p £ m)) = «(1) . Correspondingly, th e unverified non-zero variable nodes are partitioned based on the following probabilities: (i,m,2) _ K.0 p (l,R1,2) = ti(i.-Ri) ICo ’ 1 ^ 2 < i < d v T he normalization factor is used to make the set of param eters probability measure, and is calculated as follows: a valid A P P E N D IX A. A N A L Y S IS OF N B - V B A L G O R IT H M S FO R R E G U L A R GRAPH SS4 A .5.4 Itera tio n one, R 2-H R 1 (R egrou p in g o f check n o d es in se ts A/i,j based on th e in d ex i) A t this point, since some variable nodes in the support set have been verified at R lHR2, check nodes should be regrouped based on their /C-degree. Since the variable nodes in the set are left unverified, not all check nodes in th e set A f i j R1'^ (1 < j < dc — 1 ) are moved into th e set A ’o j'R2,1^; some will stay in the same set AT\]jR2’V>■ Hence, in addition to analyzing the set of check nodes moved from to th a t are we also have to analyze the set of check nodes th a t are moved from to M q j R2'^ ■ We partition the edges adjacent to a check node into two sets: /C-edges and A-edges. /C-edges are connected to variable nodes in the set )C ^\ while A-edges are connected to unverified zero-valued variable nodes. To analyze the regrouping of check nodes in the sets and 2 < i < dc, we need the probabilities P^=f2^ and defined as follows. The probability P ^ l ^ is the conditional probability of an edge carrying a verified message given th a t it is a /C-edge adjacent to a check node in th e set ■A/’/ 1’jR1’1\ The probability is defined similarly w ith respect to the set of check nodes in Since th e verified messages involved in th e calculation of P^=f set (jf =2 originate from the we have: P t T ' == Pr[». € (JJC ?'m ) \ve E /C ^ ,c e E A f ^ j = 1 - Pr[ve E £ ? 'm )\ve E /C(1), ce E JS/J1’*1’1*] _ j _ Pr[t>e g /Cxl^e g /C(1)] Pr[ce E .A/'1(1,'R1|1)|r;e £ /Ci] Pr[ce E A/'1(1"R1,1V e £ P(K m) x 1/d v p(1'R1'> Pk [R1) dvp ^ R^ ’ where and p ^ 'RL are given by (A. 14) and (A. 13), respectively. Similarly, P ^ f 2^ is derived as: d r ’+d1;” ’ f ^av ) J____________ _ , ________________ \ i _ p (l,R l) Hence, the set of probabilities 2 < i < dc, 0 < k < i, 0 < j < dc — i, th a t a A P P E N D IX A. A N A L Y S IS OF N B -V B A L G O R IT H M S FOR R E G U L A R GRAPHS85 check node belongs to the set of check nodes A ^ ^ „( 1,-R 2) /*-\ (1>R2)s k ----------i-fc . d^l (1,«2) _ n (l,JB) 'V u o .i ~ Pd=\ J i 0 (1,K2) > pfh-Ra) ■A/no,o . are calculated as follows: ’ — I r>(ii^2) 1< i J moved into tne the set j\-{ Af*^ija oni'i pd,« n(i.fi Let p fyR2'l,+^ an(j ,i,c) denote ^eno^e the )-}ie probabilities probabilities th th a t a check node belongs to ^ 2,i,c XKfc* Iiqaw the; sets A/'|1 AiJj ,'R2’1’+) and / v l j R2’1,C\ respectively. We have: dc pM j “ i—2 PMij PK n ,r M ii.j - “ PNi,j A P P E N D IX A. A N A L Y S IS OF N B -V B A L G O R IT H M S FOR R E G U L A R GRAPHS86 A .5.5 Itera tio n one, R 2-H R 2 (V erification o f variab le n od es b ased on Z C N ) /i Drt\ Let P6 ’ denote th e probability th a t an unverified zero-valued variable node is ver­ ified at this stage. This probability is derived similar to (A. 12) and is given by: d c —1 d c —1 *T2)- E "M*e 1) €a<»] =E ^ W r • J=I E E ^ f 11 (A-is) 1=0 j= l (1 R2 2) Hence, the probability PA’. ’ , 0 < i < dv, defined as the probability th a t an unveri­ fied zero-valued variable node belongs to th e set A f is calculated as follows: Lastly, th e probability th a t a variable node is zero-valued and rem ains unverified for iteration 2 is given by: »(2) ”a A .5.6 _ n {l)A\,R2,2) ~ ”a 0 Itera tio n tw o, R 1-H R 1 (R egrou p in g o f check n o d es in Af i j based on th e in d ex j ) Similar to th e analysis of R1-HR1 a t iteration 1, for 1 < i < dc,0 < j < dc — i, 0 < k < j , we have: V (2, R\) _ ( j \ ( , v ( 2 , R \ ) \ k ( (2,R l ) \ j ~ k - \k) V ~Pe* ) v£« where, r,(2 ) v ( 2, Rl ) __ 1 _ £r Hence, for 0 < k < dc — 1, PA j _ p ( i,m ■ ) ' A P P E N D IX A. A N A L Y S IS OF N B -V B A L G O R IT H M S FOR R E G U L A R GRAPHS87 A .5.7 Itera tio n tw o, R 1-H R 2 (V erification o f variab le n od es based on D 1 C N and E C N ) ■= U^Iq 1 Edges em anating from the set , are responsible for the regrouping of variable nodes a t iteration 2, R1-HR2. Let p^2,R1^ be th e conditional probability th a t an edge is adjacent to a check node in given th a t 1 ) it em anates from an unverified non-zero variable node, and 2 ) it is not adjacent to a check node in the set UfcS)1 This is indeed the probability th a t a variable node has an edge th a t increases its index. This probability is calculated as follows (Pr[ce £ M ^ ' R1'C\ v e G K^2\ c e G A/’i 2"R1’+)] = 1): = Pr[ce G A / f ^ ’+ V G K S'\ Pr[ce G A/J2’H1,+)] Pr[ue G ce $ A /f ’H1’C)] /C(2)|ce G A/}2'm,+)] P r [ve e J C W ,c e <£Ni2’R1'C)} (2 JR1 -f) T he two probabilities in the num erator are equal to P\fy ’ and l / d c, respectively. T he denom inator can be further processed as: Pr[ne G /C(2), ce i N [ 2'Rl'C)] = Pr[ce G A /? ,m,+)] Pr[ne + £ Prt-A/f’*1’15] P r K i—2 We thus have: G G K /C(2)|ce ^ \ ^ G A / f ,jR1'+)] mAh (2,/21,-H) p (2,R1) _ __________1 M i k p% *"+ )+ T , ipT i=2 where, M dc- l k=0 Hence, th e probability P ^ ^ \ i & (0,1}, th a t a variable node from into is moved i < j < dv, is calculated as follows: - f t c / ) (pt7 mT ‘ 0 - ■ A P P E N D IX A . A N A L Y S IS OF NB- V B A L G O R IT H M S FO R R E G U L A R GRAPHS88 Finally, the probability P is calculated by: o< j < dv. t= 0 (2 J?1 2) The probability PK'. ' 1 th a t a variable node in the support set belongs to the set ^ (2,m ,2) ^-g caicuia^e(j based on the set of verified variable nodes a t this stage. Variable 2 < j < dv, are all verified. Variable nodes in th e set nodes in the set are all left unverified, and a fraction of the variable nodes in the set The set consists of two sets of variable nodes: and node in has a neighbor in are verified. A variable while a variable node in neighbor in J\f^'Rl'c \ Variable nodes in the two sets and has a are verified if and only if they are neighbor to check nodes in the sets A/^o^1’1’"^ and A/”j respectively. Let f ( 2 ’m < N an(j j ( 2,#i.O probabilities th a t a variable node in 4 ^ and JC{2nm) is verified at iteration 2, R1-HR2, respectively. We have: „(2,#1,1,+) (2,#1,1,0 f(2,m,c) W2,#i,+) M ,o J „(2,#1,+) ’ 1 Ml M ,o „(2,#1,0 PMy J ■ Finally, for the set of probabilities P ^ m '2^, we have: (2,# 1,2 ) _ _ J _ (2 ,# 1 ) „(2,#1,2,+) 1Ci f (1 ,# 1 ,2 ) (2 ,# 1 ) 0 0 *-ofo ’ _ 1 n (l,# l,2 )n (2 ,# l) _ f(2,Rl,+)\ - N (2, # l ) ^ o oti J )’ N ( 2'R1) ^(2,#1,2,C) _ 1 p (2,m,2) = «(!,#!,2)^(2,#!) jy (2 ,# l) ~ o, j= 1C\ p ICl n K1 rf2,#l,0^ J ) > ,d v. The normalization factor N^2,m^ is calculated by: yy(2,jRl) _ 'p(li^l)2)p(2,.ftl) /-. JCo ^oti ' r(2,.Rl,-}-)\ i p(lj^l)2)p(2,iil.) / -j J ' /,(2,i21,C7)\ ^(2,111) . * ^*o ^oto The probability th a t a variable node in KS1^ remains unverified after iteration 2 is calculated as follows: a<3> = a ^ N ^ m \ A P P E N D IX A. A N A L Y S IS OF N B -V B A L G O R IT H M S FOR R E G U L A R GRAPHS89 A .5.8 Itera tio n tw o, R 2-H R 1 (R egrou p in g o f check n o d es in sets A/i,j b ased on th e in d ex i ) In w hat follows, we find th e probability defined in P a rt A.5.1. In the derivation, we use th e notation s e — 1 (or s e = 0) to denote a verified (or unverified) message passing over edge e from a variable node to a check node. (For simplicity, some superscripts are om itted. They appear when there is a risk of ambiguity.) = Pr[*e = Mve E /C(2),ce Q a / ; (2’-R1’1)] G 3=2 dc = 1 - Pr[ve E JCq ’r1\ s e = 0|ue /C(2), ce E ( J A/}] G 3=2 dc - Pr[ue 6 K ? ’m \ s e = 0|ue E K P \ Ce E ( J Afj] 3=2 dc = 1 - Pr[ue E )Co\ve E K.,ce E A/}] 3=2 dc dc - Pr[ue G )Cotil^e E IC,ce E ( J Afj] Pr[se = 0|ue E )Co n , v e E K , c e e \ j A f j l 3=2 3=2 dc dc - Pr[ue E /Citil't’e E /C,ce E 0 A /} ] Pr[se = 0|ue E /Cl f l ,v e E /C,ce E Q a / ) ] 3=2 j= 2 Pr[ve E K,0\ve E K] Pr[ce € e ^ 0,u e E K] Pr[ce e U ;= 2 ^ > e e Q Pr[ue E fc,Q^\\ve E /C] Pr[ce E (_Jj= 2 A/j'|ue Pr[ce Pr [Ce G ~ /Cofi, ve E /C] . ^ ^ ,^ e ^ e( 2 R \C )\ G \J % 2 N j \ v e E K] Pr[ue E /Citi|ue G K] Pr[ce G 1_ G [ j % 2 M 3 \ve E K] /., 1 - J ' ' ) (i,m,2) (2,m) ICq ACoto i _ p(2,Hl) / 4 - l \ - (p&“ '2,A r ) (1 - / <2'm'+)) + A,A '2)A2;f,,) (1 - i * ™ ) ) . where, n ( 2 ,J t l,+ ) p(2,fli) _ * A/", + _ ( 2 ,J ll ,c ) a^dc A P P E N D IX A. A N A L Y S IS OF N B -V B A L G O R IT H M S FOR R E G U L A R GRAPHS90 2 < i < dc, 0 < k < i, 0 < j < dc — i, is calculated as Hence, the probability follows: d (2,H2) _ f v (2 ,R 2 )y -k ( 1 \k) v * 1 ) v (2 ,R 2 )\k v ~ Pd^ ) • The evolution of sets and J\f(2,m’c ) is a bit more involved. Let a check node c £ A/i(2,H1,+). Suppose, c is neighbor to a variable node v £ IC^'R1K Variable node v is verified if and only if c belongs to the subset A/^2qR1,1’+\ Hence, c moves to the set of zero-valued check nodes if it belongs to th e set A/* o'R1,1’+^ Now, suppose c is neighbor to a variable node v’ £ or v> e Since the variable node v’ is verified w ith probability 1 , check node c becomes a zero-valued check node with probability 1 as well. A similar argum ent holds tru e for the set of check nodes in J \i ’ ’ and variable nodes in . Therefore, we need to further divide check nodes in the sets A f ^ ’m ’+^ and based on w hether or not they are neighbor to variable nodes in th e sets and respectively. We partition the set into subsets ancj. j\f(2'H2'+'F) _ T he set j y ( 2,R2,+,F) consjS|-s ()f check nodes with a neighboring variable node in The rest of the check nodes in Af^2,/*1,+) are all collected in the set . Similarly, the set A/"i2vR1,C^ is partitioned into subsets j \f(2>R2’C’° ) and j^(?,R2,c,f) ^ (2 C JF1) y~(£,Rl) where A ' ’ ’ consists of check nodes with a neighboring variable node in ^ l t l • The rest of the check nodes in J\f^2'm ,c ^ are collected in the set j^f^2’1*2’0'0 ) Figure A.3 depicts the relationship between the sets. Kq o to lfl Kx o ti K2 lf2 rfC .F ) < • ~7r(cR) •/ v l , 0 F) ■(C .O ), j M C .F) •/v3,dc-l ~ 7 f(C S > ) -1 + l.d,. ~1 -/V1,0 M (U°) ’ N i +'F) - ■0 t 2 M + .O ) Af[+'0) •/vl ,0 Afo !Cdv- Figure A.3: Graphical description of sets M d.c A f ^ ° \ A / ? f 2’C'F), A P P E N D IX A. A N A L Y S IS OF N B -V B A L G O R IT H M S FOR R E G U L A R GRAPHS91 and P%'f^'F’F\ for 0 < i < dc — 1, denote the probabilities th at Let a check node belongs to sets A/’| 2t,'R2’+’° ) and and p ^ f®'c 'F) are defined similarly. respectively. Probabilities The calculation of the probability p £ f + ' F\ 0 < i < dc — 1 , follows: P%™’+'F) := Pr[c € A/?2’* 2,+’F)] = Pr[c € = Pr[c € jV1(2i,'Ri’1’+)] Pr[ue « ~ r . n , P r [«« '* l' = Pr[c » G G Pr[c € A /JJ"2’^ ^ /C g f 2)|ce G N $ m X + \ v e e Ve 6 ^ G € A ^2’* 1,1’^ ] K (2)\ ] Pr[ce G A / ^ ^ ’+ V e € /Cg’f U G Pr[ 4 £ < E M I |» , e C T ] 1 >,(2 Ri,i1+ilPrll,« 6 K o t f V € K(2)]Pr[c, e V 1(J H1,1'+)|tie e 6 tC12'] A/iy-------'] ---------------!------------------------- j — jj---------------------- !-----------------n(2,m,l,+)„(l,fll,2)„(2,jei) = _____________________ M , i ^ 0 ^ O f l _________________________________________________________________ / where (using (A . 1.G)), x - x > [„ eg k s t . c. e 1*'**. e «<2>]= m s t i= i j= i B — 5 3 P r K € / CS2f 2) , c c G A / g ^ ’+ V G /C<2>] = ] T ( j - J=2 l ) ^ 1’2^ ^ j=2 - (dv - l ) p £ f V p < ? 'm ) . Also, „(2,a2,+,0) _ J2 .ffl,lI+) M , < - r A / i . i „(2,«2,+> F) “ Following a similar approach, we have: n(2,m,c,F) _ n(2,m,i,c)n(2,m) „(2,m,c,o) _ (2,m,i,c) All checknodes in the sets A/*/2’K2’+’° \ a /^2’R2,c,’0 \ A/i io’A2,+’F\ n{2,m,c,F) and are moved into the set A/q2^ 2’1^ after R2-HR1. On the other hand, check nodes in the sets M [2-m '+'F\ and ^ I < i < dc — \, are moved into the sets a / ^ ’^ 2,1,0). Consequently, we have (2 < k < dc): A P P E N D IX A. A N A L Y S IS OF NB- VB A L G O R IT H M S FOR R E G U L A R GRAPHS92 dc V (2,R 1,1)V (2,R2) _(2,JB,1,+) _ ~ i < ,• < J PK l aj> iSjSdc _ 1 i, t= 2 (2 ,R 2,C ,F) (2,H2,1,C) _ % „(2,fl2,l) _ „(2,m,l) 7V 0lJ (2,R 2,+ ,F ) + PMij ~ - P M 0 ,J + Z i <■ ,- < j , n (2 ,R 2 ,C ,0 ) + IW x , J PM j 1,1,pK i ’ n {2 ,R 2 ,+ ,0 ) + P F fi,j ’ “ i j S i - l . i= 2 A .5.9 Itera tio n tw o, R 2-H R 2 (V erification o f variable n o d es based on Z C N ) (2 R2 2} At this stage, the probability PA’. , 0 < %< dv, is calculated as follows: d v -i p (2 ,R 2 ,2 ) _ where p f ,R2^ is given by (A. 15) with the appropriate change of probabilities to reflect th e values corresponding to iteration 2. Lastly, the probability th a t a variable node is zero-valued and remains unverified for iteration 3 is given by: »(3) _ „ (2 ) d (2,JO,2) ”a A .5.10 — A "A q Iteration s th ree and beyon d The analysis of an iteration £, £ > 3, is similar to th a t of iteration 2. T he sum m ary of update equations for SBB is given in Tables 4.10 and 4.1 1. A p p en d ix B A n a ly sis o f S B B over Irregular G raph s B .l Iteration Zero In this section we assume th a t for a variable degree dv we have 1 < dv < c?Uimax and for a check degree dc we have 1 < dc < dc,max- T he constraints on typical dv and dc values will be om itted for ease of presentation henceforth. They appear when there is a chance of ambiguity. Throughout the analysis we use the following notations. • Let ve and ce denote the edge sockets at variable and check side connected by edge e, respectively. d c ,m ax d v ,m a x • Let dv i \ , be the average variable degree. Similarly, let dc := i= l E ipi i= 1 be the average check degree. • Let £? and ££ denote the set of edges em anating from variable nodes and check nodes of degree i, respectively. • Let Vt and C, denote the set of variable nodes and check nodes of degree i, respectively. Let r j ( x ) denote the variable edge degree distribution; r ) i denotes the fraction of edges em anating from variable nodes of degree i. In the analysis sometimes we need to find th e elements rji in terms of A*. Using com binatorial arguments, it can easily be shown that: r)i := Pr[e G £?] = - - - -- — = ^ d v ,m * x and similarly d Pr[e E £?} = (B .l) J *=i Iteration zero consists of only one round and hence, two half-rounds. In th e first half-round, check nodes pass their measurement values along with their degrees to their neighboring variable nodes. In the second half-round, variable nodes process 93 A P P E N D IX B. A N A L Y S IS OF S B B O V E R IR R E G U L A R G R A P H S 94 the incoming messages. A variable node is verified if it receives at least one message with a value equal to zero. In this case, the variable node is verified w ith a value equal to zero according to the ZCN rule. The set of all variable nodes verified in this half-round make th e set 7Ul\ Since no variable node in the support set is verified, we have: = a4°L Let (dc) denote the set of check nodes of degree dc w ith i neighboring variable nodes in the support set, and therefore dc —i neighboring zero-valued variable nodes. T he probability P/f.d _ i d c) defined as the probability th a t a check node of degree dc belongs to the set A/^^_i(dc) is calculated as follows: t /0 - ( t ) (“ "”)* (‘ - ■ 0 2 i(i)\ve e € A] % ~ n (°) d c ,m a x r .j X 1 1 _ Q (0) » e 6 £?] = J £ c ipi 0 “ • (B -2 ) t=l Let P&\d) denote the probability th a t a variable node of degree d has a zero value and is not verified according to ZCN a t iteration 0; does not receive any message with A P P E N D IX B. A N A L Y S IS OF S B B O V E R IR R E G U L A R G R A P H S 95 value equal to zero in th e second half-round of iteration zero. We have: P%\d) = Pv[v e A (1)|y 6 VS] = Pr[u |i; G V?] Vr[v G A ^ 2’2^ ) ^ € A (0), v € VS] - (i - c*(o)) ( i - p f ^ y , i < d < d„,max. Since no element of th e support set is verified at iteration zero, we have K, ^ and hence, 0 ,(1) _ e /cl1)] = al°). T he edges adjacent to a check node are partitioned into two sets: JC-edges and Aedges. /C-edges are connected to variable nodes in the support set, while A-edges are connected to zero-valued variable nodes. Therefore, a check node in the set N i j R1,1\ d c) (0 < i < dc,0 < j < dc — i) has i, fC-edges and j , A-edges. The regrouping of check nodes is discussed in the next section. B .2 Iteration O ne, R 1-H R 1 (R egrouping check nodes in sets A fi,j(dc) based on th e in d ex j) In this section, we adopt the notation A/i(dc), 0 < i < dc, with any superscript, to denote th e set (JyLo%J^i,j(dc). T he verified messages sent from zero-valued variable nodes to check nodes at the end of iteration zero, are processed a t check nodes at iteration 1, R l-H R l. We partition the set of edges adjacent to a variable node in th e set A j(d ), 0 < j < d, into 0-edges and Ayo-edges. A/”=o-edges are connected to zero-valued check nodes (check nodes in the set (Jj.A/o(t)), while A/^o-edges are connected to non-zero check nodes. Let A /^ e -q j^ c ) denote the set of check nodes of degree dc th a t are regrouped from A f ^ ^ i ^ i d c ) to jV^j’m '1\ d c), 1 < i < d,c and 0 < j < dc — i. To analyze the regrouping, we need to find the probability PgR of an edge in the set of A-edges to carry a non-verified message. Such edges are connected to the set A 0 (d), 1 < d < dv^max. A P P E N D IX B. A N A L Y S IS O F S B B O V E R IR R E G U L A R G R A P H S 96 We have: dv ,m a x ^ = E P riti' 6 A<°'B2'2»(d),e e V > , 6 A m ,c , i U ^ > W ] t d=l “ Pr[e VJ) Ve € A(Q>,ue € A 0 (0,B2’2)(d), ce g Uj A/'0(1)(i)] G tT _ d^ P r K 6 A m , c ^ U A 4 (1)W] x p r [e € VJ] Pr[r>e ^ ^ ^ v ,m a x d l G 0 22 A^°^e G V^] Pr[ue G AQ ,ii ’ ^(d)|t;e G A^°\ e d £ 5Z Prte e d = l i —0 G Vj] 01 e A(0), ve G A f ,fl2,2)(fi), C c £ (J w ( )(i)] x Pr[ce <£ (jA /o 1}(*)|ve € Aj,0,ii2’2)(d),t)e G A (0),e G V, - ^ - ^ - ^ 0))P^0R2'2\ d ) x l dy T d v ,m a x d d = l i= 0 j \ dXdp(Q,R2,2)^ ) d —i The verification of variable nodes of degree d, 1 < d < dVtmax, in th e support set is as follows: 1 . variable nodes in the set U t a JC\l 'm \ d ) are verified based on the ECN rule. 2. variable nodes in the set fC^’R1\ d ) are resolved based on D 1CN only if they are neighbor to a check node in the set Udc .o^1^ (^c) • 3. variable nodes in the set /Cq1,H1^(d) are not resolved in this iteration. It is worth mentioning th a t some variable nodes in the set u t =2 can also be verified according to D1CN. However, since the probability of false verification is zero and since all such variable nodes are verified, the source of verification is not im portant in the analysis. Let / P ’^ 1) denote the fraction of variable nodes in the set th a t are verified according to the D1CN rule. This fraction is independent of th e degree of the variable nodes and is calculated using the Bayes’ rule as follows: ^ c ,m a x /<«■>=Pr|U d= 1 ^ ti.m a x dc ,m a x d c — 1 (J *?'“’(<«.* 6 U d„=l dc= 1 .7=0 Since the formulation is independent of the variable degree, for the sake of presentation A P P E N D IX B. A N A L Y S IS OF S B B O V E R IR R E G U L A R G R A P H S 98 we remove the union notation on dv and all the superscripts. Hence, we obtain: rfc.m&x f(h R l) ^ ^ Pr[ce E A/i,o(d),e E C^] Pr[i>e E K,\(dv)\ce E A /i^ d )] d=l ^ c ,m a x d — 1 EE Pr[ce E M l d (d),e E Q ] Pr[ue E K x{dv)\ce E M j( d ) ] d=l j =0 ^,max A/ij(d!)|ce E JViio(d),ve E x Pr[ce E j d c , m ax E d=l , 1 E d=l j =0 ^ c ,m a x x3x1 c dc,max d ~ 1 * E /Ci(c?v)] d„=l 1 f C c ’i ^ E d=l (B.5) rfc.max <2— 1 E d=l E 0 ^ m Therefore, the probability th a t a variable node of degree d, 1 < d < d„>max, in the support set remains unverified at iteration 1 is as follows: off* := Prju E KS2\ d ) \ = Pr[t> E E T>d\ - Y l N . m ' id) = a<'> f i - = Q(1> ( p g ^ ’w + (i - /"■“ >) d 1;” ^ ) ) ■ The final regrouping of variable nodes of degree d, 1 < d < d„jmax, into sets JC\1,m’2\ d ) , 0 < * < d, is performed by taking into account th e set of verified variable nodes of degree d. We have: < ra '2V ) = 0 - f {hm)) v tm)Wpg;H1’2)(d) = 0 , 2 < i < d. (B. 6 ) The normalization factor N^1,m\ d ) is used to make the set of param eters P ^ m,2\ d ) a valid probability measure, and is calculated as follows: ~(2) N V . m Hd) = p ( u n ) M + (1 _ ,< .,« !)) p a . m {d) = a d a (1) A P P E N D IX B. A N A L Y S IS OF S B B O V E R IR R E G U L A R G R A P H S B .4 Let 99 Iteration One, R 2-H R 1 (R egrouping check n od es in sets A based on th e in d ex i) 1 < d < rfC)inax, 1 < i < d, 0 < j < d — i,0 < k < i, denote the set of check nodes of degree d th a t are regrouped from to A f j ^ ^ ' ^ i d ) . We /n f ) 0 \ need to consider two separate cases: i — 1 and i > 2 , and find the probabilities and defined as follows. The probability P ^ l ^ is defined as th e conditional probability of an edge carrying a verified message (due to the ECN) given th a t it is a /C-edge adjacent to a check node in the set Udc=i* A f\l 'Rl'l\ d c). T he probability defined as th e conditional probability of an edge carrying a verified message (due to th e ECN or D 1CN) given th a t it is a /C-edge adjacent to a check node in the set (Jdc=r To find the probability , we shall consider only the variable nodes in the set (Jd^=” Uf =2 ^ i 1R1'2\ d v). This is because variable nodes in the set K'i’’m '2\ d v) are verified based on D1CN. We proceed as follows: A P P E N D IX B. A N A L Y S IS OF S B B O V E R IR R E G U L A R G R A P H S d r , ,m a x d c ,m a x dv Q (dv)\ve E ) C ^ , c e e Pd=f2) = P r be € i —2 du= 2 ^ c ,m a x l d i 'm '2\ d v)\ve 0 G G JC(1),c e G d v = l d v , m ax 0 A/'i1,'R1,1)(dc)] d c = 1 < ic,m a x Pr[*’*6KS1"R1,2>(. e K (1>,ce e dc=l Q Mll* 1 J,(iic)l = i - X) d v = A/J1’* 1’1^ ) ] dc ~ 1 < iv,m ax = 1 — Pr[we 1 r [ e e V I , v , e K p \ ve e K<1M’1>(dr),C' € dv ~ l Q A /f ■'"■'Vc)] d c= 1 i= 0 dv,m&x Y , Pr[e € VJJ Pr[r;e G /C|e G VJJ Pr[^e G 1 € JC(dv)} d v = 1_____________________________________________________________________________________________________________ - r te G Vl ’v* E K W ' V* e £ ? ’m ’2\ d v),ce G 0 £ d„=l j =o A/?1’" 1*1^ ) ] dc=l d c ,m a x x Pr[ce G [J A/i(dc)|vc G )Ci{dv)\ dc=l < iv,m ax . % 1 W pO ^ ) = 1’ pO PX Z = 1 - P * = * 2) ’ ^ ) = °> l < J < dc - = t- I < j < d c ~i - /j J"! After the regrouping, the probability P\f'kj ’ (dc) th a t a check node belongs to th e set •A/fc1j,'R2,1^(dc) is calculated as follows: ^ 2,1)(4 ) = £ p % i? ' 1\ d e) P % ^ ( d e), 0 < k < d c, 0 < j < d c-i. i—k We need to partition the set of check nodes in A f l j R2,1\ d c), 1 < dc < dC)Xnax, into two sets: A/ri j ‘R2’1’+^(dc) and Af[lJ R2'l'C\ d c). Check nodes in the set Af[X-R2'l '+\ d c) were moved into the set M ^ - R2,X\ d c) from all the other sets -A/^j’m ’^ (d c), 2 < i < dc. Check nodes in th e set A f\X-R2'X'C\ d c), however, are those th a t stayed in the set from M j ’mA)(dc). Let P%'R2,X'+\ d c) and P^fRf ' l 'C\ d c) denote th e probabilities th a t a check node belongs to the sets ■A/’i j fl2’1’+^(dc) and M [X-R2’X'C\ d c), respectively. We have: ^ B .5 2’1,C)( 4 ) = P ^ ' l\ d c ) P ^ ] { d c) = ^ 2,1)(dc) - P j j - f ,1,+)(rfc). Iteration O ne, R 2-H R 2 (V erification o f vari­ able nodes based on ZCN ) T he measurement corresponding to check nodes in the set 1< k < d — 1 , changes to zero, as the check nodes are no longer connected to an unverified variable node in the support set. Hence, the messages transm itted by such check nodes have a value equal to zero, which in tu rn verifies some variable nodes (in the set A) at R2-HR2 of iteration 1. The probability p ^ ,R2^ (defined in (B.2)) is calculated as follows. This param eter is needed to find th e probability th a t a zero-valued variable node is verified at this A P P E N D IX B. A N A L Y S IS OF S B B O V E R IR R E G U L A R G R A P H S 102 stage. d c ,m a x d — 1 = E E Prie e c5’ e d = 1 W b. 6 A<1)] j= 1 ^ c .m a x d — 1 E E Prle e C^1Prlc‘ e < _ d = 1 d c ,m a x ,w lMle e C*1Prbe e A<1)|e e C5.c« e A ^ 'V ) ] j = l ___________________________________________________________________________________________________________________________________ d d —i E E E P r le e « ] P r lc« e Y ! i m ''Hd)\e € q ] Pr[«, 6 A<')|e 6 C% ce 6 d=i i= o i = i d c ,m a x d — 1 E - j E f C .\ ^ c ,m a x ’w ^ ) d —1 E ^ E ^ f ’w .----------------------------= — — d~ 1 U c .m a x / d E E d = 1 t= 0 d —1 , E / t C j= l *\ ’m ( 5 ) c ' ' » c ,m a x ------------------ . d (B. 8 ) d —t E A i E E ^ a r ’M d = l i= 0 j= l Hence, the probabilities P ^ ,R2,2\ d v) and P& \dv) are calculated as follows: = (t) (1 - pi1'*2’) * " * , 0 (<0 p(2.Kl) = _d=l_______________ _ E £* j pi « (l,« h dv,n V J \ J 1 _ p (l,K 2 )^ -l 2 ^ dAdO P8 > For the regrouping of check nodes based on the second index we thus have: P jw V c ) = Q ( ? £ “ ’)* ( l - ’’Y " ) ’ * , l < i < d c , 0 < j < d c - i , 0 < k < j . (B.9) A P P E N D IX B. A N A L Y S IS OF S B B O V E R IR R E G U L A R G R A P H S 103 Hence, dc—i PM*1,1](dc) = 1 - d c ~ dc'max> 2 < i < dc, 0 < k < dc - i, j=k d c-1 p < W ,+ ) (ly = ^ p ( w , +)W l 1 < dc < dcm^ ' 0 < k < d e - l , (B.10) j=k p (2,m,i,c)(dc) = ^ p {i,«2,i,c)(rfc)p(2,m)(dc)) i < < 4 >max, o < fc < dc - 1 . ( B .ll) j=k B .7 Iteration T w o, R 1-H R 2 (V erification o f vari­ able nodes based on E C N and D 1C N ) Edges in the set U f c r A / f ’* 1 ,1 ,+ ^(<2c) are responsible for the regrouping of variable nodes at iteration 2, R1-HR2. We denote by p ^ 'RV> the conditional probability th a t an edge is adjacent to a check node in U d^i* A/ri 2’J?1’1’+^(dc) given th a t 1 ) it em­ anates from an unverified non-zero variable node, and 2 ) it is not adjacent to a check node in the set (dc); i.e. it is connected to a check node in the set U j : r ((Ji=2 A/i(2vR1,1)(dc) u M 2’Rhl’+)(dc) ). This probability is calculated as follows: 104 A P P E N D IX B. A N A L Y S IS OF S B B O V E R IR R E G U L A R G R A P H S p (2,m) = p r [e € Cl,ce e N [ w ’+\ d ) \ v e € £ (2),c e i d= 1 ^ c ,m a x ” S N i 2'm 'c ) {dc)} Q dc= l e Ced] P r [ce e M +\ d ) \ e 6 Q] Pv[ve e £ (2)|ce e M +\ d ) } Pr[«e G >Cm,C' G { u t 2A/'<2,m,1)(d c ) u JVf ,'n'1'+)(<5+E E E t C mJ d = l fc= 0 c d = l i~ 2 j= 0 c d c ,m a x d — 1 E E oC ’m _______________ d=l fc=0______________________________ d c ,m a x d — 1 e d= 1 d c ,m a x d d —t EA*ar+,<“>+e e e w C m fc= 0 d = l j= 0 1 < dv < dViinax, i € {0,1}, is calculated as follows: Hence, th e probability * c ’w = f t : ! ) i= 2 Rl)f ‘ (* - ■ 1- >• *s ^ Finally, the probability P%'}m \ d v) th a t a variable node of degree dv in th e support set belongs to th e set K ^ 'm \ d v) is calculated by: l i= 0 T he probability P% '^'2\ d v) is calculated based on the set of verified variable nodes at this stage. Variable nodes in the set U j =2 f c f ’R1\ d v) are all verified. Variable nodes in the set Ud”=:T ^ o ’m \ ^ v ) are left intact, and a fraction of the variable nodes in the set Uct^i* follows. R1\ d v) are verified. The procedure to find this fraction is as A P P E N D IX B. A N A L Y S IS OF S B B O V E R IR R E G U L A R G R A P H S 105 For any degree d , the set K ^ ’m \ d ) consists of two sets of variable nodes: IC ^ R1\ d ) and )C(^ 'R1\ d ) . Variable nodes in the set fC ^ Rl\ d ) are neighbor to check nodes in while variable nodes in the set JC^'R1\ d ) are neighbor to check th e set Variable nodes in / ( ^ ’/ ^ ( d ) and JC^’R1\ d ) are verified nodes in the set at iteration 2, R1-HR2, if they are neighbor to check nodes in th e sets and A/’^ 0,m ’1,C\ respectively. The param eters / ( 2>-R1>+) and defined as the respective verification probability of variable nodes in -’/ ^ ( d ) and (d) at iteration 2, R1-HR2, are calculated similar to (B.5) (independent of the variable node degree): ^ c .m a x d c , m ax E f( 2 ,m ,+ ) _ E f(2 ,R l,C ) _ d = \ ________________________ i dJ — 1 dA c , m a x ’ p ^ - hC>(d) d=\ j ___________________ A ____ <^c,max d —1 E ^E= °. 2 <3max, j = i 2 < i < dc, 0 < k < i, 0 < j < dc — i, we then have: We explain the evolution of the sets (dc) and jy/d2^ 1-1^ ) 1 < dc < dC)max, in the following. A variable node in the set K ^ ^ l\ d ) , 1 < d < dVtInax., 1 < i < d, has i neighboring check nodes in the set (Jdc A f 2’^ 1’1’^ ^ ) . variable node in the set On the other hand, a 1 < d < dv^max, 1 < i < d, is neighbor to 1 check node in the set {JdcAfi2’R1,1’C\ d c) and i —1 check nodes in the set \JdcA fi2'm ’1,+\ d c). W ithout loss of generality, let c 6 A/’i 2,/n’1’+^(dc). Further, suppose c is neighbor to (0 /?1^ a variable node v £ (d). Variable node v is verified if and only if c belongs to th e subset fdiflR1,1,+\ d c). Hence, c is regrouped as a zero-valued check node if it belongs to the set A ri io’R1’1’+^(dc)- Now, suppose c is neighbor to a variable node v1 £ Uf=2 or v> e Uf=2 Since the variable node v ’ is verified with probability 1 , check node c is regrouped into the set of zero-valued check nodes with probability 1 as well. This argum ent is independent of the check degree dc and similarly holds true for check nodes in A^ 2’fll,1,c^(dc). Therefore, to regroup check nodes in the sets A]f2,in’1,+^(dc) and Afl2'R1,1'C\ d c) , we need to divide them further based on their neighbors; i.e., w hether or not they are neighbor to variable nodes in A P P E N D IX B. A N A L Y S IS OF S B B O V E R IR R E G U L A R G R A P H S 107 th e sets JC^R1\ d ) and )C ^R1\ d ) , respectively. For any check degree d, we partition the set A/r/ 2,in’1’+^((4)] d v ,m a x = Pr[ee V5,ve £ /C g f2>( r [ e £ VI,V, € K^,v„ E K.^f\d),cc € M ^ Rhh+\ d e)\, d = 1 i= l d v ,m a x d B = Y d = l £ > r [ e £ VS,vc £ & 2\ v e £ t= l ce £ V j,t"'‘’+)(4)]. A P P E N D IX B. A N A L Y S IS OF S B B O V E R IR R E G U L A R G R A P H S 108 Hence, ^u,max n (2 ,R 2 ,+ ,F ),j ^ PN n \ a c) — T A,A d =1 “ u v ,m a x a ,» E 1 Qv ✓ ' 1 ^ { c w c w i+ P & m'2)Mr£rMii i } dv,m a x d = 1 ^ v ,in a x d E E a^ 2) {a’fesw,(‘0 i C ,M + (‘ - ^ d=l t=l where the probability f2 /21 1 | } (dc) can be calculated using (B . 10 ). We also have: „(2,H2,+,0) _ „(2,fll,l,+) UA/i,, " ’M d ^ 'V )} “ „(2,fi2,+,F) M,i ~ "Ah,. Following a similar approach, we have: rl(2,JR2,C,F),J x A*1 rl(2,iil>l,C)/ J x l“ c,J - /V A»* (acj > * AdQ!d ^ ®v,m&x W a , "1 E EvW ^Vid^V) d J , f c '0 )()‘ ( 1 - , o 3, is similar to th a t of iteration 2. The update rules for a generic iteration £, £ > 2 are given in Tables 5.3 and 5.4.