Open AccessFast algorithm for least‐squares based image prediction
Author(s) -
Martchenko Andrew,
Deng Guang
Publication year - 2016
Publication title -
iet image processing
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.401
H-Index - 45
eISSN - 1751-9667
pISSN - 1751-9659
DOI - 10.1049/iet-ipr.2016.0017
Subject(s) - cholesky decomposition , minimum degree algorithm , algorithm , computational complexity theory , qr decomposition , incomplete cholesky factorization , least squares function approximation , computer science , matrix decomposition , covariance matrix , mathematics , mathematical optimization , statistics , eigenvalues and eigenvectors , physics , quantum mechanics , estimator
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.