We discuss new methods for the recovery of signals with block-sparse structure, based on l1-minimization. Our emphasis is on veriable conditions on the problem parameters (sensing matrix and the block structure) for accurate recovery and eciently computable bounds for the recovery error. These bounds are then optimized with respect to the method parameters to construct the estimators with improved statistical properties. To justify the proposed approach we provide an oracle inequality, which links the properties of the recovery algorithms and the best estimation performance. We also propose a new matching pursuit algorithm for block-sparse recovery.