This paper presents a novel approach that represents an image or a set of images using a non-orthogonal binary subspace (NBS) spanned by box-like base vectors. These base vectors possess the property that the inner product operation with them can be computed very efficiently. We investigate the optimized orthogonal matching pursuit method for finding the best NBS base vectors. It is demonstrated in this paper how the NBS based expansion can be applied to speed up several common computer vision algorithms, including normalized cross correlation (NCC), sum of squared difference (SSD) matching, appearance subspace projection and subspace-based object recognition. Promising experimental results on facial and natural images are demonstrated in this paper.