We propose a novel method for data reduction in gait recognition, called Subblock Complete Two Dimensional Principal Component Analysis (SbC2DPCA). GEIs were divided into smaller sub-images and redundant subblocks were adaptively removed. Complete Two Dimensional Principal Component Analysis (C2DPCA) was then applied to every sub-image directly, to acquire a set of projection sub-vectors for both row and column directions and these were synthesized into whole features for subsequent classification using nearest neighbor classifier. We evaluate the proposed gait recognition method on the CASIA gait database. The experimental results and analysis show the recognition accuracy of SbC2DPCA to be superior to C2DPCA, with C2DPCA being a special case of SbC2DPCA. The novelty of the proposed method lies in the adaptive removal of redundant data while extracting local features. This translates to data reduction with very minimal loss of information, as demonstrated by the remarkable recognition accuracy when subjects change clothing or have a backpack.