  Sparsity and rank functions are important ways of regularizing
under-determined linear systems. Optimization of the resulting formulations is
made difficult since both these penalties are non-convex and discontinuous. The
most common remedy is to instead use the $\ell^1$- and nuclear-norms. While
these are convex and can therefore be reliably optimized they suffer from a
shrinking bias that degrades the solution quality in the presence of noise.
  In this paper we combine recently developed bias free non-convex alternatives
with the nuclear- and $\ell^1-$penalties. This reduces bias and still enables
reliable optimization properties. We develop an efficient minimization scheme
using derived proximal operators and evaluate the method on several real and
synthetic computer vision applications with promising results.
