A new computationally efficient algorithm for two-dimensional sliding-window least-squares prediction is presented in this study. The fast algorithm is based on a recursive update of the Cholesky decomposition. Compared with the state-of-the-art algorithm, the proposed algorithm reduces the computational complexity from O(D 3) to O(D 2 h), where D is the predictor order and h is the height of the prediction patch. The computational improvement is made at the stage of solving the normal equations for which an update algorithm for the Cholesky decomposition of the covariance matrix is proposed. It is shown that a large part of the Cholesky decomposition at location n can be efficiently calculated by performing orthonormal updates on the Cholesky decomposition at n − 1. The computational improvement is made without requiring additional storage space. Extensive experiments using causal and non-causal predictors of varying shapes and sizes have confirmed that the proposed algorithm is consistently faster than the state-of-the-art algorithm and produces identical prediction images. The efficiency of the proposed algorithm is shown to be affected by the order in which pixels are sampled, thus an ordering procedure is proposed to minimise the number of numerical operations.
['Andrew Martchenko', 'Guang Deng']
Fast algorithm for least-squares based image prediction