  As shown in [Blumensath and Davies 2009, Baraniuk et al. 2010], signals whose
wavelet coefficients exhibit a rooted tree structure can be recovered using
specially-adapted compressed sensing algorithms from just n=O(k) measurements,
where k is the sparsity of the signal. Motivated by these results, we introduce
a simplified proportional-dimensional asymptotic framework which enables the
quantitative evaluation of recovery guarantees for tree-based compressed
sensing. In the context of Gaussian matrices, we apply this framework to
existing worst-case analysis of the Iterative Tree Projection (ITP) algorithm
which makes use of the tree-based Restricted Isometry Property (RIP). Within
the same framework, we then obtain quantitative results based on a new method
of analysis, recently introduced in [Cartis and Thompson, 2015], which
considers the fixed points of the algorithm. By exploiting the realistic
average-case assumption that the measurements are statistically independent of
the signal, we obtain significant quantitative improvements when compared to
the tree-based RIP analysis. Our results have a refreshingly simple
interpretation, explicitly determining a bound on the number of measurements
that are required as a multiple of the sparsity. For example we prove that
exact recovery of binary tree-based signals from noiseless Gaussian
measurements is asymptotically guaranteed for ITP with constant stepsize
provided n>50k. All our results extend to the more realistic case in which
measurements are corrupted by noise.
