Patch-based low-rank approximation (PLRA) via truncated singular value decomposition is a powerful and effective tool for recovering the underlying low-rank structure in images. Generally, it first performs an approximate nearest neighbors (ANN) search algorithm to group similar patches into a collection of matrices with reshaping them as vectors. The inherent correlation among similar patches makes these matrices have a low-rank structure. Then the singular value decomposition (SVD) is used to derive a low-rank approximation of each matrix by truncating small singular values. However, the conventional implementation of patch-based low-rank image restoration suffers from high computational cost of the ANN search and full SVD. To address this limitation, we propose a fast approximation method that accelerates the computation of PLRA using multiple kd-trees and Lanczos approximation. The basic idea of this method is to exploit an index kd-tree built from patch samples of the observed image and several small kd-trees built from overlapping regions of the image to accelerate the search for similar patches, and apply the Lanczos bidiagonalization procedure to obtain a fast low-rank approximation of patch matrix without computing the full SVD. Experimental results on image denoising and inpainting tasks demonstrate the efficiency and accuracy of our method. © 2020 Elsevier Inc.