In this paper, a new approach to parity space-based fault detection (FD) is put forward for linear discrete time-varying (LDTV) systems. The focus of our study is on solving the problem with heavy online computational burden. The main contributions are two folds. Firstly, the problem of parity space-based FD is formulated as finding a minimum of quadratic form of unknown input. Secondly, by applying projection in Krein space, a solution of optimal parity space-based FD is obtained via recursively computing innovations. It is shown that the reduction of computation cost is achievable, especially with the increase of parity space order. Finally, a numerical example is given to demonstrate the application of the proposed method. (C) 2015 Elsevier Ltd. All rights reserved.