In this paper, we study the minimization of l(0) regularized optimization problems, where the objective function is composed of a smooth convex function and the l(0) regularization. We analyze optimality conditions for this nonconvex problem which lead to the separation of local minima into two restricted classes that are nested and around the set of global minima. Based on these restricted classes of local minima, we devise two new random coordinate descent type methods for solving these problems. In particular, we analyze the convergence properties of an iterative hard thresholding based random coordinate descent algorithm for which we prove that any limit point is a local minimum from the first restricted class of local minimizers. Then, we analyze the convergence of a random proximal alternating minimization method and show that any limit point of this algorithm is a local minima from the second restricted class of local minimizers. We also provide numerical experiments which show the superior behavior of our methods in comparison with the usual iterative hard thresholding algorithm.