The ℓ0 regularized optimization (ℓ0-RO) problem is a nonconvex problem that is central to several applications such as sparse coding, dictionary learning, compressed sensing, etc. Iterative algorithms for ℓ0 - RO problem are only known to have local or subsequence convergence properties i.e. the solution is trapped in a saddle point or in an inferior local solution. Inspired by techniques used to improve the alternating optimization (AO) of nonconvex functions, we propose a simple yet effective two step iterative method to improve the solution to the ℓ0RO problem. Given an initial solution, we first find the vanilla solution to ℓ0RO via a descent method (in particular, Nesterov's accelerated gradient descent), to then estimate a new initial solution by using a scaled version of the dictionary involved in the ℓ0-RO problem, considering only a reduced number of its atoms. Our proposed algorithm is empirically demonstrated to have the best tradeoff between accuracy and computation time, when compared to state-of-the-art algorithms. Furthermore, due to its structure, our proposed algorithm can be directly apply to the convolutional formulation of ℓ0-RO.