Most bioimaging modalities rely on indirect measurements of the quantity under investigation. The image is obtained as the result of an optimization problem involving a physical model of the measurement system. Due to the ill-posedness of the above problem, the impact of the noise on the reconstructed images must be controlled. The recent emphasis in biomedical image reconstruction is on regularization schemes that favor sparse solutions, which renders the optimization problem non-smooth. In this work, we show how step-size adaptation can be used to speed up the most recent multi-step algorithms (e. g. FISTA) employed in sparse image recovery. We present experiments in MRI and Fluorescence Molecular Tomography with specifically tailored step-adaptation strategies. Our results demonstrate the possibility of an order-of-magnitude speed enhancement over state-of-the-art algorithms.