  In this work we consider numerical efficiency and convergence rates for
solvers of non-convex multi-penalty formulations when reconstructing sparse
signals from noisy linear measurements. We extend an existing approach, based
on reduction to an augmented single-penalty formulation, to the non-convex
setting and discuss its computational intractability in large-scale
applications. To circumvent this limitation, we propose an alternative
single-penalty reduction based on infimal convolution that shares the benefits
of the augmented approach but is computationally less dependent on the problem
size. We provide linear convergence rates for both approaches, and their
dependence on design parameters. Numerical experiments substantiate our
theoretical findings.
