In this paper we propose a new methodology to synthesize and implement robust monotonically convergent ILC for lifted systems, with the computational complexity that is linear in the trial length. Starting from the model uncertainty of the local sample to sample LTI or LTV models, and using the randomized algorithm, we compute the bound on the model uncertainty of the ILC system representation in the trial domain (lifted ILC). Based on this computed uncertainty bound, we design weighting matrices of the Norm Optimal ILC, such that the robust monotonic convergence condition is satisfied. Since we compute the uncertainty bound, rather than assuming its value in the trial domain, we reduce the conservatism of the robust design. The linear computational complexity of the algorithms for computation of the uncertainty bound and implementation of the Norm Optimal ILC law, is achieved through exploiting the sequentially semi-separable structure of the lifted system matrices. Therefore the framework proposed in this paper is especially suitable for the LTI and LTV uncertain systems with a large number of samples in the trial. We have performed numerical experiments to demonstrate the robustness and linear computational complexity of the proposed method. (C) 2012 Elsevier Ltd. All rights reserved.