© 2017, Springer-Verlag Berlin Heidelberg. The ℓ1 / 2-regularizer has been studied widely in compressed sensing, but there have been few studies about dictionary learning problems. The dictionary learning method with the ℓ1 / 2-regularizer aims to learn a dictionary, which requires solving a very challenging nonconvex and nonsmooth optimization problem. In addition, the low mutual coherence of a dictionary is an important property that ensures the optimality of the sparse representation in the dictionary. In this paper, we address a dictionary learning problem involving the ℓ1 / 2-regularizer and the coherence penalty, which is difficult to solve quickly and efficiently. We employ a decomposition scheme and an alternating optimization, which transforms the overall problem into a set of minimizations of single-vector-variable subproblems. Although the subproblems are nonsmooth and even nonconvex, we propose the use of proximal operator technology to conquer them, which leads to a rapid and efficient dictionary learning algorithm. In a theoretical analysis, we establish the algorithm’s global convergence. Experiments were performed for dictionary learning using both synthetic data and real-world data. For the synthetic data, we demonstrated that our algorithm performed better than state-of-the-art algorithms. Using real-world data, the learned dictionaries were shown to be more efficient than algorithms using ℓ1-norm for sparsity.