You are an expert at summarizing long articles. Proceed to summarize the following text: 
in compressive imaging @xcite , we aim to estimate an image @xmath0 from @xmath1 noisy linear observations @xmath2 , @xmath3 assuming that the image has a representation @xmath4 in some wavelet basis  @xmath5 ( i.e. , @xmath6 ) containing only a few ( @xmath7 ) large coefficients ( i.e. , @xmath8 ) . in ( [ eqn : system ] ) , @xmath9 is a known measurement matrix and @xmath10 is additive white gaussian noise . though @xmath11 makes the problem ill - posed , it has been shown that @xmath12 can be recovered from @xmath13 when @xmath7 is adequately small and @xmath14 is incoherent with @xmath5 @xcite . the wavelet coefficients of natural images are known to have an additional structure known as _ persistence across scales _ ( pas ) @xcite , which we now describe . for 2d images , the wavelet coefficients are naturally organized into quad - trees , where each coefficient at level @xmath15 acts as a parent for four child coefficients at level @xmath16 . the pas property says that , if a parent is very small , then all of its children are likely to be very small ; similarly , if a parent is large , then it is likely that some ( but not necessarily all ) of its children will also be large . several authors have exploited the pas property for compressive imaging @xcite . the so - called `` model - based '' approach @xcite is a deterministic incarnation of pas that leverages a restricted union - of - subspaces and manifests as a modified cosamp @xcite algorithm . most approaches are bayesian in nature , exploiting the fact that pas is readily modeled by a _ hidden markov tree _ ( hmt ) @xcite . the first work in this direction appears to be @xcite , where an iteratively re - weighted @xmath17 algorithm , generating an estimate of @xmath12 , was alternated with a viterbi algorithm , generating an estimate of the hmt states . more recently , hmt - based compressive imaging has been attacked using modern bayesian tools @xcite . for example , @xcite used markov - chain monte - carlo ( mcmc ) , which is known to yield correct posteriors after convergence . for practical image sizes , however , convergence takes an impractically long time , and so mcmc must be terminated early , at which point its performance may suffer . variational bayes ( vb ) can sometimes offer a better performance / complexity tradeoff , motivating the approach in @xcite . our experiments indicate that , while @xcite indeed offers a good performance / complexity tradeoff , it is possible to do significantly better .    in this paper , we propose a novel approach to hmt - based compressive imaging based on loopy belief propagation @xcite . for this , we model the coefficients in @xmath18 as conditionally gaussian with variances that depend on the values of hmt states , and we propagate beliefs ( about both coefficients and states ) on the corresponding factor graph . a recently proposed `` turbo '' messaging schedule @xcite suggests to iterate between exploitation of hmt structure and exploitation of observation structure from ( [ eqn : system ] ) . for the former we use the standard sum - product algorithm @xcite , and for the latter we use the recently proposed _ approximate message passing _ ( amp ) approach @xcite . the remarkable properties of amp are 1 ) a rigorous analysis ( as @xmath19 with @xmath20 fixed , under i.i.d gaussian @xmath14 ) @xcite establishing that its solutions are governed by a state - evolution whose fixed points  when unique  yield the true posterior means , and 2 ) very low implementational complexity ( e.g. , amp requires one forward and one inverse fast - wavelet - transform per iteration , and very few iterations ) . we consider two types of conditional - gaussian coefficient models : a bernoulli - gaussian ( bg ) model and a two - state gaussian - mixture ( gm ) model . the bg model assumes that the coefficients are either generated from a large - variance gaussian distribution or are exactly zero ( i.e. , the coefficients are exactly sparse ) , whereas the gm model assumes that the coefficients are generated from either a large - variance or a small - variance gaussian distribution . both models have been previously applied for imaging , e.g. , the bg model was used in  @xcite , whereas the gm model was used in  @xcite . although our models for the coefficients @xmath18 and the corresponding hmt states involve statistical parameters like variance and transition probability , we learn those parameters directly from the data . to do so , we take a hierarchical bayesian approach  similar to @xcite  where these statistical parameters are treated as random variables with suitable hyperpriors . experiments on a large image database show that our turbo - amp approach yields state - of - the - art reconstruction performance with substantial reduction in complexity . the remainder of the paper is organized as follows . section  [ sec : model ] describes the signal model , section  [ sec : alg ] describes the proposed algorithm , section  [ sec : sims ] gives numerical results and comparisons with other algorithms , and section  [ sec : conc ] concludes . _ notation _ : above and in the sequel , we use lowercase boldface quantities to denote vectors , uppercase boldface quantities to denote matrices , @xmath21 to denote the identity matrix , @xmath22 to denote transpose , and @xmath23 . we use @xmath24 to denote the probability density function ( pdf ) of random variable @xmath25 given the event @xmath26 , where often the subscript `` @xmath27 '' is omitted when there is no danger of confusion . we use @xmath28 to denote the @xmath29-dimensional gaussian pdf with argument @xmath12 , mean @xmath30 , and covariance matrix @xmath31 , and we write @xmath32 to indicate that random vector @xmath12 has this pdf . we use @xmath33 to denote expectation , @xmath34 to denote the probability of event @xmath35 , and @xmath36 to denote the dirac delta . finally , we use @xmath37 to denote equality up to a multiplicative constant . throughout , we assume that @xmath5 represents a 2d wavelet transform @xcite , so that the transform coefficients @xmath38^t$ ] can be partitioned into so - called `` wavelet '' coefficients ( at indices @xmath39 ) and `` approximation '' coefficients ( at indices @xmath40 ) . the wavelet coefficients can be further partitioned into several quad - trees , each with @xmath41 levels ( see fig . [ fig : quadtree ] ) . we denote the indices of all coefficients at level @xmath42 of these wavelet trees by @xmath43 , where @xmath44 refers to the root . in the interest of brevity , and with a slight abuse of notation , we refer to the approximation coefficients as level `` @xmath45 '' of the wavelet tree ( i.e. , @xmath46 ) . as discussed earlier , two coefficient models are considered in this paper : bernoulli - gaussian ( bg ) and two - state gaussian mixture ( gm ) . for ease of exposition , we focus on the bg model until section  [ sec : gm ] , at which point the gm case is detailed . in the bg model , each transform coefficient @xmath47 is modeled using the ( conditionally independent ) prior pdf @xmath48 where @xmath49 is a hidden binary state . the approximation states @xmath50 are assigned the apriori activity rate @xmath51 , which is discussed further below . meanwhile , the root wavelet states @xmath52 are assigned @xmath53 . within each quad - tree , the states have a markov structure . in particular , the activity of a state at level @xmath54 is determined by its parent s activity ( at level @xmath15 ) and the transition probabilities @xmath55 , where @xmath56 denotes the probability that the child s state equals @xmath57 given that his parent s state also equals @xmath57 , and @xmath58 denotes the probability that the child s state equals @xmath59 given given that his parent s state also equals @xmath59 . the corresponding factor graph is shown in fig . [ fig : fga1 ] . [ l][bl][0.9]@xmath60 [ l][bl][0.9]@xmath61 [ l][bl][0.9]@xmath62 [ l][bl][0.9]@xmath63 [ l][bl][0.9]@xmath64 [ l][bl][0.9]@xmath65 [ l][bl][0.9]@xmath66 [ l][bl][0.9]@xmath67 [ l][bl][0.9]@xmath68 [ l][bl][0.9]@xmath69 [ l][bl][0.9]@xmath70 [ l][bl][0.9]@xmath71 [ l][bl][0.9]@xmath72 [ l][bl][0.9]@xmath73 [ l][bl][0.9]@xmath74 [ l][bl][0.9]@xmath75 [ l][bl][0.9]@xmath76 [ l][bl][0.9]@xmath77 [ l][bl][0.9]@xmath78 [ l][bl][0.9]@xmath79 [ l][bl][0.9]@xmath80 [ l][bl][0.9]@xmath81 [ l][bl][0.9]@xmath82 [ l][bl][0.9]@xmath83 [ r][b][0.9]@xmath84 [ r][b][0.9]@xmath85 [ r][b][0.9]@xmath86 [ l][bl][0.9]@xmath87 [ l][bl][0.9]@xmath88 [ l][bl][0.9]@xmath89 [ l][bl][0.9]@xmath90 [ b][b][0.8]observation structure [ b][b][0.8]support structure    we take a hierarchical bayesian approach , modeling the statistical parameters @xmath91 as random variables and assigning them appropriate hyperpriors . rather than working directly with variances , we find it more convenient to work with precisions ( i.e. , inverse - variances ) such as @xmath92 . we then assume that all coefficients at the same level have the same precision , so that @xmath93 for all @xmath94 . to these precisions , we assign conjugate priors @xcite , which in this case take the form @xmath95 where @xmath96 for @xmath97 , and where @xmath98 are hyperparameters . ( recall that the mean and variance of @xmath99 are given by @xmath100 and @xmath101 , respectively @xcite . ) for the activity rates and transition parameters , we assume @xmath102 where @xmath103 , and where @xmath104 are hyperparameters . ( recall that the mean and variance of @xmath105 are given by @xmath106 and @xmath107 , respectively @xcite . ) our hyperparameter choices are detailed in section  [ sec : sims ] . to infer the wavelet coefficients @xmath18 , we would ideally like to compute the posterior pdf @xmath108 & = & \sum_{{\ensuremath{\boldsymbol{s}}}}\underbrace{p({\ensuremath{\boldsymbol{s}}})}_{\displaystyle \triangleq h({\ensuremath{\boldsymbol{s } } } ) }   \prod_{n=1}^n \underbrace{p(\theta_n { \,|\,}s_n)}_{\displaystyle \triangleq f_n(\theta_n , s_n ) }   \prod_{m=1}^m \underbrace{p(y_m { \,|\,}{\ensuremath{\boldsymbol{\theta}}})}_{\displaystyle \triangleq g_m({\ensuremath{\boldsymbol{\theta } } } ) } ,       \quad \label{eqn : post2}\end{aligned}\ ] ] where @xmath37 denotes equality up to a multiplicative constant . for the bg coefficient model , @xmath109 is specified by ( [ eqn : spike_slab ] ) . due to the white gaussian noise model ( [ eqn : system ] ) , we have @xmath110 , where @xmath111 denotes the @xmath112 row of the matrix @xmath113 .      while exact computation of @xmath114 is computationally prohibitive , the marginal posteriors @xmath115 can be efficiently approximated using _ loopy belief propagation _ ( lbp ) @xcite on the factor graph of fig . [ fig : fga1 ] , which uses round nodes to denote variables and square nodes to denote the factors in ( [ eqn : post2 ] ) . in doing so , we also obtain the marginal posteriors @xmath116 . for now , we treat statistical parameters @xmath117 , as if they were fixed and known , and we detail the procedure by which they are learned in section  [ sec : update ] .    in lbp , messages are exchanged between the nodes of the factor graph until they converge . messages take the form of pdfs ( or pmfs ) , and the message flowing to / from a variable node can be interpreted as a local belief about that variable . according to the _ sum - product algorithm _ @xcite the message emitted by a variable node along a given edge is ( an appropriate scaling of ) the product of the incoming messages on all other edges . meanwhile , the message emitted by a function node along a given edge is ( an appropriate scaling of ) the integral ( or sum ) of the product of the node s constraint function and the incoming messages on all other edges , where the integration ( or summation ) is performed over all variables other than the one directly connected to the edge along which the message travels . when the factor graph has no loops , exact marginal posteriors result from two ( i.e. , forward and backward ) passes of the sum - product algorithm @xcite . when the factor graph has loops , however , exact inference is known to be np hard @xcite and so lbp is not guaranteed to produce correct posteriors . still , lbp has shown state - of - the - art performance in many applications , such as inference on markov random fields @xcite , turbo decoding @xcite , ldpc decoding @xcite , multiuser detection @xcite , and compressive sensing @xcite . with loopy belief propagation , there exists some freedom in how messages are scheduled . in this work , we adopt the `` turbo '' approach recently proposed in @xcite . for this , we split the factor graph in fig . [ fig : fga1 ] along the dashed line and obtain the two decoupled subgraphs in fig . [ fig : turbo ] . we then alternate between belief propagation on each of these two subgraphs , treating the likelihoods on @xmath118 generated from belief propagation on one subgraph as priors for subsequent belief propagation on the other subgraph . we now give a more precise description of this turbo scheme , referring to one full round of alternation as a `` turbo iteration . '' in the sequel , we use @xmath119 to denote the message passed from node @xmath120 to node @xmath121 during the @xmath122 turbo iteration . [ l][bl][0.8]@xmath123 [ l][bl][0.8]@xmath84 [ l][bl][0.8]@xmath85 [ l][bl][0.8]@xmath124 [ l][bl][0.8]@xmath68 [ l][bl][0.8]@xmath69 [ l][bl][0.8]@xmath70 [ l][bl][0.8]@xmath125 [ l][bl][0.8]@xmath76 [ l][bl][0.8]@xmath77 [ l][bl][0.8]@xmath78 [ l][bl][0.8]@xmath126 [ l][bl][0.8]@xmath60 [ l][bl][0.8]@xmath61 [ l][bl][0.8]@xmath62 [ l][bl][0.8]@xmath127 [ l][bl][0.8]@xmath128 [ l][bl][0.8]@xmath129 [ l][bl][0.8]@xmath130 [ l][bl][0.8]@xmath131 [ l][bl][0.8]@xmath132 [ l][bl][0.8]@xmath133 [ l][bl][0.8]@xmath134 [ l][bl][0.8]@xmath135 [ ] [ b][1.0]@xmath90   [ b][b][0.8]amp     the procedure starts at @xmath136 by setting the `` prior '' pmfs @xmath137 in accordance with the apriori activity rates @xmath138 described in section  [ sec : model ] . lbp is then iterated ( to convergence ) on the left subgraph in fig . [ fig : turbo ] , finally yielding the messages @xmath139 . we note that the message @xmath140 can be interpreted as the current estimate of the likelihood would be referred to as the `` extrinsic '' information about @xmath141 produced by the left `` decoder '' , since it does not directly involve the corresponding prior @xmath142 . similarly , the message @xmath143 would be referred to as the extrinsic information about @xmath141 produced by the right decoder . ] on @xmath141 , i.e. , @xmath144 as a function of @xmath141 . these likelihoods are then treated as priors for belief propagation on the right subgraph , as facilitated by the assignment @xmath145 for each @xmath146 . due to the tree structure of hmt , there are no loops in right subgraph ( i.e. , inside the `` @xmath123 '' super - node in fig . [ fig : turbo ] ) , and thus it suffices to perform only one forward - backward pass of the sum - product algorithm @xcite . the resulting leftward messages @xmath147 are subsequently treated as priors for belief propagation on the left subgraph at the next turbo iteration , as facilitated by the assignment @xmath148 . the process then continues for turbo iterations @xmath149 , until the likelihoods converge or a maximum number of turbo iterations has elapsed . formally , the turbo schedule is summarized by @xmath150    in the sequel , we refer to inference of @xmath118 using compressive - measurement structure ( i.e. , inference on the left subgraph of fig .  [ fig : turbo ] ) as _ soft support - recovery _ ( ssr ) and inference of @xmath118 using hmt structure ( i.e. , inference on the right subgraph of fig . [ fig : turbo ] ) as _ soft support - decoding _ ( ssd ) . ssr details are described in the next subsection . we now discuss our implementation of ssr during a single turbo iteration @xmath151 . because the operations are invariant to @xmath151 , we suppress the @xmath151-notation . as described above , ssr performs several iterations of loopy belief propagation per turbo iteration using the fixed priors @xmath152 . this implies that , over ssr s lbp iterations , the message @xmath153 is fixed at @xmath154 the dashed box in fig . [ fig : turbo ] shows the region of the factor graph on which messages are updated during ssr s lbp iterations . this subgraph can be recognized as the one that donoho , maleki , and montanari used to derive their so - called _ approximate message passing _ ( amp ) algorithm @xcite . while @xcite assumed an i.i.d laplacian prior for @xmath18 , the approach for generic i.i.d priors was outlined in @xcite . below , we extend the approach of @xcite to independent _ non_-identical priors ( as analyzed in @xcite ) and we detail the bernoulli - gaussian case . in the sequel , we use a superscript-@xmath155 to index ssr s lbp iterations .    according to the sum - product algorithm , the fact that @xmath153 is non - gaussian implies that @xmath156 is also non - gaussian , which complicates the exact calculation of the subsequent messages @xmath157 as defined by the sum - product algorithm . however , for large @xmath29 , the combined effect of @xmath158 at the @xmath159 nodes can be approximated as gaussian using central - limit theorem ( clt ) arguments , after which it becomes sufficient to parameterize each message @xmath156 by only its mean and variance : @xmath160 combining @xmath161 with @xmath162 , the clt then implies that @xmath163 the updates @xmath164 and @xmath165 can then be calculated from @xmath166 where , using ( [ eqn : prod_gauss ] ) , the product term in ( [ eqn : xntogm_ip1 ] ) is @xmath167 assuming that the values @xmath168 satisfy @xmath169 which occurs , e.g. , when @xmath170 is large and @xmath171 are generated i.i.d with variance @xmath172 , we have @xmath173 , and thus ( [ eqn : xntogm_ip1 ] ) is well approximated by @xmath174 in this case , the mean and variance of @xmath175 become @xmath176\nonumber\end{aligned}\ ] ] where @xmath177 according to the sum - product algorithm , @xmath178 , the posterior on @xmath47 after ssr s @xmath179-lbp iteration , obeys @xmath180 whose mean and variance determine the @xmath179-iteration mmse estimate of @xmath47 and its variance , respectively . noting that the difference between  ( [ eqn : p_hat_xn ] ) and ( [ eqn : xntogm_ip1 ] ) is only the inclusion of the @xmath112 product term , these mmse quantities become @xmath181 similarly , the posterior on @xmath141 after the @xmath179 iteration obeys @xmath182\nonumber\end{aligned}\ ] ] where @xmath183\nonumber\end{aligned}\ ] ] since @xmath184 , it can be seen that the corresponding log - likelihood ratio ( llr ) is @xmath185 clearly , the llr @xmath186 and the likelihood function @xmath187 express the same information , but in different ways . the procedure described thus far updates @xmath188 variables per lbp iteration , which is impractical since @xmath189 can be very large . in @xcite , donoho , maleki , and montanari proposed , for the i.i.d case , further approximations that yield a `` first - order '' approximate message passing ( amp ) algorithm that allows the update of only @xmath190 variables per lbp iteration , essentially by approximating the _ differences _ among the outgoing means / variances of the @xmath191 nodes ( i.e. , @xmath192 and @xmath193 ) as well as the differences among the outgoing means / variances of the @xmath194 nodes ( i.e. , @xmath195 and @xmath196 ) . these resulting algorithm was then rigorously analyzed by bayati and montanari in @xcite . we now summarize a straightforward extension of the i.i.d amp algorithm from @xcite to the case of an independent but non - identical bernoulli - gaussian prior ( [ eqn : fntoxn ] ) : @xmath197 where @xmath198 , @xmath199 and @xmath200 are defined as @xmath201}{[1+\tau_n(\xi;c)]^2 } \ ! \quad \label{eqn : fnd}\\ \tau_n(\xi;c ) & = & \beta_n(c ) \exp(-\zeta_n(c ) \xi^2 ) . \label{eqn : taun}\end{aligned}\ ] ] for the first turbo iteration ( i.e. , @xmath202 ) , we initialize amp using @xmath203 , @xmath204 , and @xmath205 for all @xmath206 . for subsequent turbo iterations ( i.e. , @xmath207 ) , we initialize amp by setting @xmath208 equal to the final values of @xmath209 generated by amp at the _ previous _ turbo iteration . we terminate the amp iterations as soon as either @xmath210 or a maximum of @xmath211 amp iterations have elapsed . similarly , we terminate the turbo iterations as soon as either @xmath212 a maximum of @xmath211 turbo iterations have elapsed . the final value of @xmath213^t$ ] is output at the signal estimate @xmath214 . we now describe how the precisions @xmath215 are learned . first , we recall that @xmath216 describes the apriori precision on the active coefficients at the @xmath217 level , i.e. , on @xmath218 , where the corresponding index set @xmath219 is of size @xmath220 . furthermore , we recall that the prior on @xmath216 was chosen as in ( [ eqn : prior_rhoj ] ) . thus , _ if _ we had access to the true values @xmath218 , then ( [ eqn : spike_slab ] ) implies that @xmath221 which implies ) . ] that the posterior on @xmath216 would take the form of @xmath222 where @xmath223 and @xmath224 . in practice , we do nt have access to the true values @xmath218 nor to the set @xmath225 , and thus we propose to build surrogates from the ssr outputs . in particular , to update @xmath216 after the @xmath122 turbo iteration , we employ @xmath226 and @xmath227 , where @xmath228 and @xmath229 denote the final llr on @xmath141 and the final mmse estimate of @xmath47 , respectively , at the @xmath122 turbo iteration . these choices imply the hyperparameters @xmath230 finally , to perform ssr at turbo iteration @xmath231 , we set the variances @xmath232 equal to the inverse of the expected precisions , i.e. , @xmath233 . the noise variance @xmath234 is learned similarly from the ssr - estimated residual .    next , we describe how the transition probabilities @xmath235 are learned . first , we recall that @xmath58 describes the probability that a child at level @xmath54 is active ( i.e. , @xmath236 ) given that his parent ( at level @xmath15 ) is active . furthermore , we recall that the prior on @xmath58 was chosen as in ( [ eqn : prior_pij11 ] ) . thus _ if _ we knew that there were @xmath237 active coefficients at level @xmath15 , of which @xmath238 had active children , then the posterior on @xmath58 would take the form of @xmath239 , where @xmath240 and @xmath241 . in practice , we do nt have access to the true values of @xmath237 and @xmath238 , and thus we build surrogates from the ssr outputs . in particular , to update @xmath58 after the @xmath122 turbo iteration , we approximate @xmath236 by the event @xmath242 , and based on this approximation set @xmath243 ( as in ( [ eqn : kj ] ) ) and @xmath244 . the corresponding hyperparameters are then updated as @xmath245 finally , to perform ssr at turbo iteration @xmath231 , we set the transition probabilities @xmath246 equal to the expected value @xmath247 . the parameters @xmath248 , @xmath249 , and @xmath250 are learned similarly .      until now , we have focused on the bernoulli - gaussian ( bg ) signal model ( [ eqn : spike_slab ] ) . in this section , we describe the modifications needed to handle the gaussian mixture ( gm ) model @xmath251 where @xmath252 denotes the variance of `` large '' coefficients and @xmath253 denotes the variance of `` small '' ones . for either the bg or gm prior , amp is performed using the steps ( [ eqn : xini])-([eqn : cni ] ) . for the bg case , the functions @xmath198 , @xmath199 , @xmath200 , and @xmath254 are given in ( [ eqn : fn])([eqn : taun ] ) , whereas for the gm case , they take the form @xmath255 ^ 2}{[1+\bar{\tau}_n(\xi , c)]^2 }   + \ , c\,\xi^{-1}\ ! f_n(\xi ; c ) \nonumber\label{eqn : gn2}\\[-1.5mm]&&\\[-3.0 mm ] f'_n(\xi;c ) & = & \frac{\bar{\tau}_n(\xi;c)\bar{\alpha}{_{n,\text{\sf l}}}(c)(1+\bar{\tau}_n(\xi;c ) - 2 \xi^2 \bar{\zeta}_n(c ) ) } { [ 1+\bar{\tau}_n(\xi;c)]^2 } \nonumber\\ & & +   \frac{\bar{\alpha}{_{n,\text{\sf s}}}(c)(1+\bar{\tau}_n(\xi;c ) + 2 \xi^2 \bar{\zeta}_n(c)\bar{\tau}_n(\xi;c ) ) } { [ 1+\bar{\tau}_n(\xi;c)]^2 }   \quad \label{eqn : fnd2}\\ \bar{\tau}_n(\xi , c ) & = & \bar{\beta}_n(c ) \exp(-\bar{\zeta}_n(c)\xi^2),\end{aligned}\ ] ] where @xmath256 likewise , for the bg case , the extrinsic llr is given by ( [ eqn : amp_llr ] ) , whereas for the gm case , it becomes @xmath257 the proposed turbo approach to compressive imaging was compared to several other tree - sparse reconstruction algorithms : modelcs  @xcite , hmt+irwl1  @xcite , mcmc  @xcite , variational bayes  ( vb )  @xcite ; and to several simple - sparse reconstruction algorithms : cosamp  @xcite , spgl1  @xcite , and bernoulli - gaussian ( bg ) amp . all numerical experiments were performed on @xmath258 ( i.e. , @xmath259 ) grayscale images using a @xmath260-level 2d haar wavelet decomposition , yielding @xmath261 approximation coefficients and @xmath262 individual markov trees . in all cases , the measurement matrix @xmath14 had i.i.d gaussian entries . unless otherwise specified , @xmath263 noiseless measurements were used . we used normalized mean squared error ( nmse ) @xmath264 as the performance metric . we now describe how the hyperparameters were chosen for the proposed turbo schemes . below , we use @xmath265 to denote the total number of wavelet coefficients at level @xmath15 , and @xmath266 to denote the total number of approximation coefficients . for both turbo - bg and turbo - gm , the beta hyperparameters were chosen so that @xmath267 , @xmath268 and @xmath269 with @xmath270 , @xmath271 , @xmath272 , and @xmath273 . these informative hyperparameters are similar to the `` universal '' recommendations in @xcite and , in fact , identical to the ones suggested in the mcmc work @xcite . for turbo - bg , the hyperparameters for the signal precisions @xmath274 were set to @xmath275 and @xmath276\!=\![10 , 1 , 1 , 0.1 , 0.1]$ ] . this choice is motivated by the fact that wavelet coefficient magnitudes are known to decay exponentially with scale @xmath15 ( e.g. , @xcite ) . meanwhile , the hyperparameters for the noise precision @xmath277 were set to @xmath278 . although the measurements were noiseless , we allow turbo - bg a nonzero noise variance in order to make up for the fact that the wavelet coefficients are not exactly sparse , as assumed by the bg signal model . ( we note that the same was done in the bg - based work @xcite . ) for turbo - gm , the hyperparameters @xmath279 for the signal precisions @xmath280 were set at the values of @xmath281 for the bg case , while the hyperparameters @xmath282 for @xmath283 were set as @xmath284 and @xmath285 . meanwhile , the noise variance @xmath234 was assumed to be exactly zero , because the gm signal prior is capable of modeling non - sparse wavelet coefficients .    for mcmc @xcite , the hyperparameters were set in accordance with the values described in  @xcite ; the values of @xmath286 are same as the ones used for the proposed turbo - bg scheme , while @xmath287 . for vb , the same hyperparameters as mcmc were used except for @xmath288 and @xmath289 , which were the default values of hyperparameters used in the publicly available code . we experimented with the values for both mcmc and vb and found that the default values indeed seem to work best . for example , if one swaps the @xmath281 hyperparameters between vb and mcmc , then the average performance of vb and mcmc degrade by @xmath290db and @xmath291db , respectively , relative to the values reported in table  [ tab : summary ] .    for both the cosamp and modelcs algorithms , the principal tuning parameter is the assumed number of non - zero coefficients . for both modelcs ( which is based on cosamp ) and cosamp itself , we used the rice university codes , which include a genie - aided mechanism to compute the number of active coefficients from the original image . however , since we observed that the algorithms perform somewhat poorly under that tuning mechanism , we instead ran ( for each image ) multiple reconstructions with the number of active coefficients varying from @xmath292 to @xmath293 in steps of @xmath294 , and reported the result with the best nmse . the number of active coefficients chosen in this manner was usually much smaller than that chosen by the genie - aided mechanism .    to implement bg - amp , we used the amp scheme described in section  [ sec : mp : ssr ] with the hyperparameter learning scheme described in section  [ sec : update ] ; hmt structure was not exploited . for this , we assumed that the priors on variance @xmath295 and activity @xmath296 were identical over the coefficient index @xmath146 , and assigned gamma and beta hyperpriors of @xmath297 and @xmath298 , respectively . for hmt+irwl1 , we ran code provided by the authors with default settings . for spgl1 , the residual variance was set to @xmath57 , and all parameters were set at their defaults . [ fig : reccomp ] shows a @xmath258 section of the `` cameraman '' image along with the images recovered by the various algorithms . qualitatively , we see that cosamp , which leverages only simple sparsity , and modelcs , which models persistence - across - scales ( pas ) through a deterministic tree structure , both perform relatively poorly . hmt+irwl1 also performs relatively poorly , due to ( we believe ) the ad - hoc manner in which the hmt structure was exploited via iteratively re - weighted @xmath17 . the bg - amp and spgl1 algorithms , neither of which attempt to exploit pas , perform better . the hmt - based schemes ( vb , mcmc , turbo - gm , and turbo - gm ) all perform significantly better , with the turbo schemes performing best . [ b][b][0.8]original [ b][b][0.8]hmt+irwl1 [ b][b][0.8]cosamp [ b][b][0.8]modelcs [ b][b][0.8]bg - amp [ b][b][0.8]spgl1 [ b][b][0.8]variational bayes [ b][b][0.8]mcmc [ b][b][0.8]turbo - bg [ b][b][0.8]turbo - gm                         +                        [ c][bc][0.8]image type [ c][c][0.8]average nmse ( db ) [ l][l][0.45 ] cosamp [ l][l][0.45 ] hmt - irwl1 [ l][l][0.45]turbo  bg [ l][l][0.45]turbo  gm    [ c][bc][0.8]image type [ c][c][0.8]average runtime ( sec ) [ l][l][0.45 ] cosamp [ l][l][0.45 ] hmt - irwl1 [ l][l][0.45]turbo  bg [ l][l][0.45]turbo  gm    .nmse and runtime averaged over @xmath299 images . [ cols="^,^,^",options="header " , ]     [ c][bc][0.8]number of measurements @xmath300 [ c][c][0.8]average nmse ( db ) [ l][l][0.45 ] cosamp [ l][l][0.45 ] hmt - irwl1 [ l][l][0.45]turbo  bg [ l][l][0.45]turbo  gm    [ c][bc][0.8]number of measurements @xmath300 [ c][c][0.8]average runtime ( sec ) [ l][l][0.45 ] cosamp [ l][l][0.45 ] hmt - irwl1 [ l][l][0.45]turbo  bg [ l][l][0.45]turbo  gm    for a quantitative comparison , we measured average performance over a suite of images in a _ microsoft research object class recognition _ database images extracted from the `` pixel - wise labelled image database v2 '' at _ http://research.microsoft.com / en - us / projects / objectclassrecognition_. what we refer to as an `` image type '' is a `` row '' in this database . ] that contains @xmath301 types of images ( see fig .  [ fig : categories ] ) with roughly @xmath302 images of each type . in particular , we computed the average nmse and average runtime on a 2.5  ghz pc , for each image type . these results are reported in figures  [ fig : nmse ] and  [ fig : comptime ] , and the global averages ( over all @xmath299 images ) are reported in table  [ tab : summary ] . from the table , we observe that the proposed turbo algorithms outperform all the other tested algorithms in terms of reconstruction nmse , but are beaten only by cosamp in speed . between the two turbo algorithms , we observe that turbo - gm slightly outperforms turbo - bg in terms of reconstruction nmse , while taking the same runtime . in terms of nmse performance , the closest competitor to the turbo schemes is mcmc , db ( i.e. , @xmath303db better ) at an average runtime of @xmath304 sec ( i.e. , @xmath305 slower ) . ] whose nmse is @xmath306db worse than turbo - bg and @xmath307db worse than turbo - gm . the good nmse performance of mcmc comes at the cost of complexity , though : mcmc is @xmath308 times slower than the turbo schemes . the second closest nmse - competitor is vb , showing performance @xmath309  db worse than turbo - bg and @xmath310db worse than turbo - gm . even with this sacrifice in performance , vb is still twice as slow as the turbo schemes . among the algorithms that do not exploit pas , we see that spgl1 offers the best nmse performance , but is by far the slowest ( e.g. , @xmath301 times slower than cosamp ) . meanwhile , cosamp is the fastest , but shows the worst nmse performance ( e.g. , @xmath311db worse than spgl1 ) . bg - amp strikes an excellent balance between the two : its nmse is only @xmath312db away from spgl1 , whereas it takes only @xmath313 times as long as cosamp . however , by combining the amp algorithm with hmt structure via the turbo approach , it is possible to significantly improve nmse while simultaneously decreasing the runtime . the reason for the complexity decrease is twofold . first , the hmt structure helps the amp and parameter - learning iterations to converge faster . second , the hmt steps are computationally negligible relative to the amp steps : when , e.g. , @xmath314 , the amp portion of the turbo iteration takes approximately @xmath315 sec while the hmt portion takes @xmath316 sec . we also studied nmse and compute time as a function of the number of measurements , @xmath170 . for this study , we examined images of type  1 at @xmath317 . in figure [ fig : nmse_varym ] , we see that turbo - gm offers the uniformly best nmse performance across @xmath170 . however , as @xmath170 decreases , there is little difference between the nmses of turbo - gm , turbo - cs , and mcmc . as @xmath170 increases , though , we see that the nmses of mcmc and vb converge , but that they are significantly outperformed by turbo - gm , turbo - cs , and somewhat surprisingly  spgl1 . in fact , at @xmath318 , spgl1 outperforms turbo - bg , but not turbo - gm . however , the excellent performance of spgl1 at these @xmath170 comes at the cost of very high complexity , as evident in figure  [ fig : comptime_varym ] . we proposed a new approach to hmt - based compressive imaging based on loopy belief propagation , leveraging a turbo message passing schedule and the amp algorithm of donoho , maleki , and montanari . we then tested our algorithm on a suite of @xmath299 natural images and found that it outperformed the state - of - the - art approach ( i.e. , variational bayes ) while halving its runtime . m.  f. duarte , m.  b. wakin , and r.  g. baraniuk , `` wavelet - domain compressive signal reconstruction using a hidden markov tree model , '' in _ proc . speech & signal process . _ , las vegas , nv , apr . 2008 , pp . 51375140 . b.  j. frey and d.  j.  c. mackay , `` a revolution : belief propagation in graphs with cycles , '' in _ adv . in neural inform . processing syst . _ , m.  jordan , m.  s. kearns , and s.  a. solla , eds.1em plus 0.5em minus 0.4em mit press , 1998 . s.  som , l.  c. potter , and p.  schniter , `` on approximate message passing for reconstruction of non - uniformly sparse signals , '' in _ proc . national aerospace and electronics conf . _ , dayton , oh , jul . 2010 . j.  k. romberg , h.  choi , and r.  g. baraniuk , `` bayesian tree - structured image modeling using wavelet - domain hidden markov models , '' _ ieee trans . image process . _ , vol . 10 , no .  7 , pp . 10561068 , jul . s.  som , l.  c. potter , and p.  schniter , `` compressive imaging using approximate message passing and a markov - tree prior , '' in _ proc . asilomar conf . signals syst . _ , pacific grove , ca , nov .
we propose a novel algorithm for compressive imaging that exploits both the sparsity and persistence across scales found in the 2d wavelet transform coefficients of natural images . like other recent works , 
 we model wavelet structure using a hidden markov tree ( hmt ) but , unlike other works , ours is based on loopy belief propagation ( lbp ) . for lbp , we adopt a recently proposed `` turbo '' message passing schedule that alternates between exploitation of hmt structure and exploitation of compressive - measurement structure . for the latter , we leverage donoho , maleki , and montanari s recently proposed approximate message passing ( amp ) algorithm . 
 experiments with a large image database suggest that , relative to existing schemes , our turbo lbp approach yields state - of - the - art reconstruction performance with substantial reduction in complexity .