The coded aperture snapshot spectral imager (CASSI) senses the spatial and spectral information of a scene using a set of K random projections of the scene onto focal plane array measurements. The reconstruction of the underlying three-dimensional (3D) scene is then obtained by l1 norm-based inverse optimization algorithms such as the gradient projections for sparse reconstruction (GPSR). The Computational complexity of the inverse problem in this case grows with order OKN4L per iteration, where N2 and L are the spatial and spectral dimensions of the scene, respectively. In some applications the computational complexity becomes overwhelming since reconstructions can take up to several hours in desktop architectures. This paper presents a mathematical model for lapped block reconstructions in CASSI with OKB4L complexity per GPSR iteration where B ? N is the block size. The approach takes advantage of the structure of the sensing matrix thus allowing the independent recovery of smaller overlapping blocks spanning the measurement set. The reconstructed 3D lapped parallelepipeds are then merged to reduce the block-artifacts in the reconstructed scenes. The full data cube is reconstructed with complexity OKN4?N02L, per iteration, where N0 ?N?B?. Simulations show the benefits of the new model as data cube reconstruction can be accelerated by an order of magnitude. Furthermore, the lapped block reconstructions lead to comparable or higher image reconstruction quality. © 2013 Optical Society of America