A novel phase noise filtering algorithm for InSAR using dictionary learning in the gradient vector domain is proposed. With this technique, the original optimization problem for the InSAR noise reduction is first established. However, due to the non-convexity of the optimization problem, it is difficult to solve. Then, by using the splitting technique and employing the augmented Lagrangian framework, we obtain a relaxed nonlinear constraint optimization problem with $l_1$-norm regularization which can be solved efficiently by the alternating direction method of multipliers. Specifically, we first train dictionaries from the horizontal and vertical gradients of the InSAR complex phase image sequentially, and then reconstruct the desired image from the sparse representations of both gradients. Numerical experiments on simulated and measured data show that the new InSAR phase noise reduction method has a better performance than several standard phase filtering methods in terms of residual counts, mean square error and maintenance of the fringe completeness.