In this paper, we develop a regularization framework for image deblurring based on a new definition of the
normalized graph Laplacian. We apply a fast scaling algorithm to the kernel similarity matrix to derive the
symmetric, doubly stochastic filtering matrix from which the normalized Laplacian matrix is built. We use this
new definition of the Laplacian to construct a cost function consisting of data fidelity and regularization terms
to solve the ill-posed motion deblurring problem. The final estimate is obtained by minimizing the resulting cost
function in an iterative manner. Furthermore, the spectral properties of the Laplacian matrix equip us with the
required tools for spectral analysis of the proposed method. We verify the effectiveness of our iterative algorithm
via synthetic and real examples.