Inexact and incremental bilinear Lanczos components algorithms for high dimensionality reduction and image reconstruction

•We proposed an inexact algorithm for image reconstruction•This algorithm is efficient both in storage and running time.•We analyze its convergence and backward errors.•An incremental version of the algorithm is given to handle dynamic increased data set.

Recently, matrix-based methods have gained wide attentions in pattern recognition and machine learning communities. The generalized low rank approximations of matrices (GLRAM) and the bilinear Lanczos components (BLC) algorithm are two popular algorithms that treat data as the native two-dimensional matrix patterns. However, these two algorithms often require heavy computation time and memory space in practice, especially for large scale problems. In this paper, we propose inexact and incremental bilinear Lanczos components algorithms for high dimensionality reduction and image reconstruction. We first introduce the thick-restarting strategy to the BLC algorithm, and present a thick-restarted Lanczos components (TRBLC) algorithm. In this algorithm, we use the Ritz vectors as approximations to dominant eigenvectors instead of the Lanczos vectors. In our implementation, the iterative matrices are neither formed nor stored explicitly, thanks to the characteristic of the Lanczos procedure. Then, we explore the relationship between the reconstruction error and the accuracy of the Ritz vectors, so that the computational complexities of eigenpairs can be reduced significantly. As a result, we propose an inexact thick-restarted Lanczos components (Inex-TRBLC) algorithm. Moreover, we investigate the problem of incremental generalized low rank approximations of matrices, and propose an incremental and inexact TRBLC (Incr-TRBLC) algorithm. Numerical experiments illustrate the superiority of the new algorithms over the GLRAM algorithm and its variations, as well as the BLC algorithm for some real-world image reconstruction and face recognition problems.