This paper presents a mathematically rigorous framework of remarkably robust signal recovery over networks. The proposed framework is based on the so-called minimax concave (MC) loss, which is a “hybrid’’ between Tukey’s biweight loss and Huber’s loss in the sense of yielding remarkable outlierrobustness and being able to preserve convexity of the overall cost under an appropriate choice of parameters so that an iterative algorithm could generate a sequence of vectors converging provably to a solution (a global minimizer of the overall cost). We present a formulation which involves an auxiliary vector to accommodate the statistical property of noise explicitly, and we present a condition to guarantee convexity of the local cost. We apply the distributed triangularly preconditioned primal-dual algorithm to our formulation and show by numerical examples that our proposed formulation exhibits remarkable robustness under devastating outliers, and outperforms the existing methods.