Improved Solution to the ℓ₀ Regularized Optimization Problem via Dictionary-Reduced Initial Guess

The ℓ₀ regularized optimization (ℓ₀-RO) problem is a nonconvex problem that is central to several applications such as sparse coding, dictionary learning, compressed sensing, etc. Iterative algorithms for ℓ₀ - 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 ℓ₀RO problem. Given an initial solution, we first find the vanilla solution to ℓ₀RO 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 ℓ₀-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 ℓ₀-RO.