You are an expert at summarizing long articles. Proceed to summarize the following text: 
sparse matrices are particularly useful in applied and computational mathematics because of their low storage complexity and fast implementation as compared to dense matrices . of late , significant progress has been made to incorporate sparse matrices in compressed sensing , with @xcite giving both theoretical performance guarantees and also exhibiting numerical results that shows sparse matrices coming from expander graphs can be as good sensing matrices as their dense counterparts . in fact , blanchard and tanner @xcite recently demonstrated in a gpu implementation how well these type of matrices do compared to dense gaussian and discrete cosine transform matrices even with very small fixed number of nonzeros per column ( as considered here ) .    in this manuscript we consider random sparse matrices that are adjacency matrices of lossless expander graphs . expander graphs are highly connected graphs with very sparse adjacency matrices , a precise definition of a lossless expander graph is given in definition [ def : expander ] . [ def : expander ] @xmath0 is a lossless @xmath1-expander if it is a bipartite graph with @xmath2 left vertices , @xmath3 right vertices and has a regular left degree @xmath4 , such that any @xmath5 with @xmath6 has a set of neighbors @xmath7 with @xmath8 neighbors . note that these graphs are _ lossless _ because @xmath9 , they are also referred to as _ unbalanced expanders _ in the literature because @xmath10 and a @xmath11-lossless expander graph has an _ expansion _ of @xmath12 . such graphs have been well studied in theoretical computer science and mathematics and have many applications . probabilistic constructions of such graphs using random left - regular bipartite graphs with optimal parameters exist but deterministic constructions only achieve sub - optimal parameters , see @xcite or @xcite for a more detailed survey .    using a novel technique of _ dyadic splitting of sets _ , this work derives quantitative guarantees on the probabilistic construction of these graphs in the form of a bound on the tail probability of the size of the _ set of neighbors _ , @xmath13 for a given @xmath5 , of a randomly generated left - degree bipartite graph . moreover , this tail bound proves a bound on the tail probability of the _ expansion _ of the graph , @xmath14 . in addition , we derive the first phase transitions showing regions in parameter space that depicting when a left - regular bipartite graph with a given set of parameters is guaranteed to be a lossless expander with high probability . similar results in terms of the adjacency matrices of these graphs is also presented . another contribution of this work is the derivation of sampling theorems comparing performance guarantees for some of the algorithms proposed for compressed sensing using such sparse matrices as well as the more traditional @xmath15 minimization compressed sensing formulation . it also provides phase transitions of @xmath15 minimization performance guarantees for such sparse matrices compared to what @xmath16 restricted isometry constants ( @xmath17 ) analysis yields for gaussian matrices . our main result is the presentation of formulae for the expected cardinality of the _ set of neighbors _ of @xmath11-lossless expander graphs and the sparse non - mean zero matrices from these graphs . based on this , we present a tail bound on the probability that this cardinality will be less than the expected value . we start by defining the class of matrices we consider and a key concept of a _ set of neighbors _ used in our derivation . [ def:1set_expansion ] let @xmath18 be an @xmath19 matrix with @xmath4 nonzeros in each column . we refer to @xmath18 as a random a ) sparse expander ( se ) if every nonzero has value @xmath20 and b ) sparse signed expander ( sse ) if every nonzero has value from @xmath21 . the support set of the @xmath4 nonzeros per column of these matrices are drawn uniformly at random and independently for each column . an se matrix is an adjacency matrix of @xmath11-lossless expander graph while an sse matrix have random sign patterns in the nonzeros of an adjacency matrix of a @xmath11-lossless expander graph . if @xmath18 is either an se or sse it will have only @xmath4 nonzeros per column and since we fix @xmath22 , @xmath18 is therefore extremely sparse . we formally define the _ set of neighbors _ in both graph theory and linear algebra notation to aid translation between the terminology of the two communities . denote @xmath23 as a submatrix of @xmath18 composed of columns of @xmath18 indexed by the set @xmath24 with @xmath25 . [ def : neighbours ] consider a bipartite graph @xmath26 where @xmath27 is the set of edges and @xmath28 is the edge that connects vertex @xmath29 to vertex @xmath30 . for a given subset of left vertices @xmath31 its set of neighbors @xmath32 is defined as @xmath33 . in terms of the adjacency matrix , @xmath18 , of @xmath26 the set of neighbors of @xmath23 denoted by @xmath34 , is the set of rows with at least one nonzero . henceforth , we will only use the linear algebra notation @xmath34 which is equivalent to @xmath35 . note that @xmath36 is a random variable depending on the draw of the set of columns , @xmath24 , for each fixed @xmath18 . therefore , we can ask what is the probability that @xmath36 is not greater than @xmath37 , in particular where @xmath37 is smaller than the expected value of @xmath36 . this is the question that theorem [ thm : prob_bound_1set_expansion ] attempts to answers . [ thm : prob_bound_1set_expansion ] for fixed @xmath38 and @xmath39 , let an @xmath19 matrix , @xmath18 be drawn from either of the classes of matrices defined in definition [ def:1set_expansion ] , then @xmath40}\ ] ] where @xmath41 , and for random variables @xmath42 and @xmath43 , @xmath44 is given by @xmath45},\end{gathered}\ ] ] where @xmath46 is the shannon entropy function of base @xmath47 logarithm . consequently :    1 . if no restriction is imposed on @xmath37 then the @xmath48 for @xmath49 take on the expected values of @xmath36 , which are given by @xmath50 for @xmath51 ; 2 .   else if @xmath52 is restricted to be less than @xmath53 , then the @xmath48 for @xmath49 are the unique solutions to the following polynomial system @xmath54 for @xmath55 with @xmath56 for each @xmath57 . theorem [ thm : prob_bound_1set_expansion ] gives a bound on the probability that the cardinality of a union of @xmath58 sets each with @xmath4 elements is less than @xmath59 . figure [ fig : cardinalities1 ] shows plots of values of @xmath60 ( size of set of neighbors ) for different @xmath58 taken over 500 realizations ( in blue ) , superimposed on these plots is the empirical mean values of @xmath60 over the 500 runs ( in red ) and the @xmath61 in green .     and @xmath62 , over @xmath63 realizations , plots ( in blue ) of the cardinalities of the index sets of nonzeros in a given number of set sizes , @xmath58 . the dotted red curve is mean of the simulations and the green squares are the @xmath61.,scaledwidth=40.0% ]    furthermore , simulations illustrate that the @xmath61 are the expected values of the cardinalities of the union of @xmath58 sets , @xmath60 , as shown in figure [ fig : cardinalities2 ] , where we show the relative error between @xmath61 and the empirical mean values of the @xmath60 , denoted by @xmath64 , realized over @xmath63 runs , to be less than @xmath65 .     and @xmath62 , over @xmath63 realizations , plots of the relative error between the mean values of @xmath59 ( referred to as @xmath64 ) and the @xmath61.,scaledwidth=40.0% ] we now use theorem [ thm : prob_bound_1set_expansion ] with the @xmath15-norm restricted isometry property ( rip-1 ) , introduced by berinde et . al . in @xcite , to deduce the corollaries that follow which are about the probabilistic construction of expander graphs , the matrices we consider , and sampling theorems of some selected compressed sensing algorithms . firstly , using only the expansion property of these graphs we can draw the following corollary from theorem [ thm : prob_bound_1set_expansion ] .    [ cor : prob_bound_1set_expander ] for fixed @xmath38 and @xmath66 , let an @xmath19 matrix , @xmath18 be drawn from the class of matrices defined in definition [ def:1set_expansion ] , then @xmath67},\ ] ] where @xmath68 with @xmath69 . theorem [ thm : prob_bound_1set_expansion ] and corollary [ cor : prob_bound_1set_expander ] allow us to calculate @xmath70 where the probability of the probabilistic constructions in definition [ def:1set_expansion ] not being a @xmath71-lossless expander is exponentially small . using corollary [ cor : prob_bound_1set_expander ] and the rip-1 results in @xcite we derived a bound for the probability that a random draw of a matrix with @xmath72s or @xmath73s in each column fails to satisfy the lower bound of the rip-1 constant ( @xmath74 ) and hence fails to come from the class of matrices given in definition [ def:1set_expansion ] , for details see @xcite . from this bound we deduce the following corollary which is a sampling theorem on the existence of lossless expander graphs . [ cor : prob_expander_existence2 ] consider @xmath66 and @xmath4 fixed . if @xmath18 is drawn from the class of matrices in definition [ def:1set_expansion ] and any @xmath58-sparse @xmath75 with @xmath76 while @xmath77 and @xmath78 then for @xmath79 and @xmath80 @xmath81 exponentially in @xmath82 , where @xmath83 is the largest limiting value of @xmath84 for which @xmath85    for each fixed @xmath66 and each fixed @xmath4 , @xmath83 in corollary [ cor : prob_expander_existence2 ] is a function of @xmath86 and a phase transition function in the @xmath87 plane . below the curve of @xmath83 the probability in goes to one exponentially in @xmath82 as the problem size grows . that is if @xmath18 is drawn at random with @xmath72s or @xmath88s in each column and having parameters @xmath89 that fall below the curve of @xmath83 then we say it is from the class of matrices in definition [ def:1set_expansion ] with probability approaching one exponentially in @xmath82 . in terms of @xmath90 for @xmath91 and @xmath92 , corollary [ cor : prob_expander_existence2 ] say that the probability @xmath93 goes to one exponentially in @xmath82 if the parameters of our graph lies in the region below @xmath83 . this implies that if we draw a random bipartite graphs that has parameters in the region below the curve of @xmath83 then with probability approaching one exponentially in @xmath82 that graph is a @xmath11-lossless expander .     for fixed @xmath94 and @xmath95 with @xmath4 varied.,scaledwidth=40.0% ]    figure [ fig : phase_transition1 ] shows a plot of what @xmath83 converge to for different values of @xmath4 with @xmath96 and @xmath82 fixed . it is interesting to note how increasing @xmath4 increases the phase transition up to a point then it decreases the phase transition . essentially beyond @xmath97 there is inconsequential gain in increasing @xmath4 . this vindicates the use of small @xmath4 in most of the numerical simulations involving the class of matrices considered here . note the vanishing sparsity as the problem size @xmath89 grows while @xmath4 is fixed to a small value of @xmath98 . corollary [ cor : prob_expander_existence2 ] can also be arrived at based on similar probabilistic constructions of expander graphs first proven by pinsker in @xcite with more recent proofs in @xcite . to put our results in perspective , we compare them to the phase transitions derived from the constants from the construction in @xcite , shown in figure [ fig : phase_transition2 ] .     in corollary [ cor : prob_expander_existence2 ] to @xmath99 derived from the alternative construction proven in @xcite.,scaledwidth=40.0% ] furthermore , for moderate values of @xmath96 this allows us to make quantitative sampling theorems for some compressed sensing reconstruction algorithms . as usual in compressed sensing , in addition to @xmath15-minimization quite a few _ combinatorial _ greedy algorithms have been proposed for these sparse non - mean zero matrices . these algorithms iteratively locates and eliminate large ( in magnitude ) components of the vector , @xcite . they include sequential sparse matching pursuit ( ssmp ) , see @xcite ; and expander recovery ( er ) , see @xcite . besides , theoretical guarantees have been given for @xmath15 recovery and some of the greedy algorithms including ssmp and er . base on these theoretical guarantees , we derived sampling theorems and present here phase transition curves which are plots of phase transition functions @xmath100 of algorithms such that for @xmath101 , a given algorithm is guaranteed to recovery all @xmath58-sparse signals with overwhelming probability approaching one exponentially in @xmath82 . computed over finite values of @xmath102 with @xmath4 fixed and the different @xmath103 values for each algorithm - 1/4 , 1/6 and 1/16 for er , @xmath15 and ssmp respectively.,scaledwidth=40.0% ]    figure [ fig : pt_alg_compare1 ] compares the phase transition of thee above mentioned algorithms . remarkably , for er recovery is guaranteed for a larger portion of the @xmath104 plane than is guaranteed by the theory for @xmath15-minimization using sparse matrices ; however , @xmath15-minimization has a larger recovery region than does ssmp . figure [ fig : pt_alg_compare2 ] shows a comparison of the phase transition of @xmath15-minimization as presented by blanchard et . al . in @xcite for dense gaussian matrices based on @xmath17 analysis and the phase transition we derived here for the sparse binary matrices coming from lossless expander based on @xmath74 analysis . this shows a significant difference between the two with sparse matrices having better performance guarantees . however , these improved recovery guarantees are likely more due to the closer match of the method of analysis than to the efficacy of sparse matrices over dense matrices .    , @xmath105 , for gaussian matrices derived using @xmath17 and @xmath106 for adjacency matrices of expander graphs with @xmath107 , @xmath108 , and @xmath94.,scaledwidth=40.0% ] due to space constraints the details of the proofs are skipped and the interested reader is referred to @xcite . it is however important to briefly describe the key innovations in the derivation of the main result , theorem [ thm : prob_bound_1set_expansion ] .    for one fixed set of columns of @xmath18 , denoted @xmath23 , the probability in can be understood as the cardinality of the unions of nonzeros in the columns . our analysis of this probability follows from a nested unions of subsets using a _ dyadic splitting _ technique . given a starting set of columns we recursively split the number of columns from this set and the resulting sets into two sets of cardinality of the ceiling and floor of the cardinality of their union until a level when the cardinalities are at most two . resulting from this type of splitting is a regular binary tree where the size of each child is either the ceiling or the floor of the size of it s parent set . the probability of interest becomes a product of the probabilities involving all the children from the dyadic splitting of @xmath34 . the proof therefore reduces to upper bounding this product . furthermore , in the binary tree resulting from our dyadic splitting scheme the number of columns in the two children of a parent node is the ceiling and the floor of half of the number of columns of the parent node . at each level of the split the number of columns of the children of that level differ by one . the enumeration of these two quantities at each level of the splitting process is necessary in the computation of the bound in . this led to another novel technical result in our derivation , i.e. _ dyadic splitting lemma _ ( lemma 2.5 in @xcite ) . this work derived bounds on the tail probability of the cardinality of the _ set of neighbours _ of expander graphs resulting into better order constants than the standard probabilistic construction . using this bound and @xmath74 analysis , we deduce sampling theorems for the existence of expander graphs and their adjacency matrices . the derivation of the tail bound used a novel technique of _ dyadic set splitting_. we also compared quantitatively , performance guarantees of compressed sensing algorithms which show greater phase transitions for er than @xmath15-minimization which in turn is greater than ssmp . a comparison of @xmath15-minimization for dense and sparse matrices shows a higher phase transition for sparse matrices . r.  berinde , a.  gilbert , p.  indyk , h.  karloff , and m.  strauss , `` combining geometry and combinatorics : a unified approach to sparse signal recovery , '' in _ communication , control , and computing , 2008 46th annual allerton conference on_.1em plus 0.5em minus 0.4emieee , 2008 , pp . 798805 . s.  jafarpour , w.  xu , b.  hassibi , and r.  calderbank , `` efficient and robust compressed sensing using optimized expander graphs , '' _ information theory , ieee transactions on _ , vol . 55 , no .  9 , pp . 42994308 , 2009 . w.  xu and b.  hassibi , `` further results on performance analysis for compressive sensing using expander graphs , '' in _ signals , systems and computers , 2007 . acssc 2007 . conference record of the forty - first asilomar conference on_.1em plus 0.5em minus 0.4emieee , 2007 , pp . 621625 . m.  capalbo , o.  reingold , s.  vadhan , and a.  wigderson , `` randomness conductors and constant - degree lossless expanders , '' in _ proceedings of the thiry - fourth annual acm symposium on theory of computing_.1em plus 0.5em minus 0.4emacm , 2002 , pp . 659668 . r.  berinde and p.  indyk , `` sequential sparse matching pursuit , '' in _ communication , control , and computing , 2009 . allerton 2009 . 47th annual allerton conference on_.1em plus 0.5em minus 0.4emieee , 2009 , pp . j.  blanchard , c.  cartis , j.  tanner , and a.  thompson , `` phase transitions for greedy sparse approximation algorithms , '' _ applied and computational harmonic analysis _ , vol .  30 , no .  2 , pp . 188203 , 2011 .
we revisit the probabilistic construction of sparse random matrices where each column has a fixed number of nonzeros whose row indices are drawn uniformly at random . 
 these matrices have a one - to - one correspondence with the adjacency matrices of lossless expander graphs . 
 we present tail bounds on the probability that the cardinality of the _ set of neighbors _ for these graphs will be less than the expected value . 
 the bounds are derived through the analysis of collisions in unions of sets using a _ 
 dyadic splitting _ technique . 
 this analysis led to the derivation of better constants that allow for quantitative theorems on existence of lossless expander graphs and hence the sparse random matrices we consider and also quantitative compressed sensing sampling theorems when using sparse non mean - zero measurement matrices . 
 -5 mm