Advances in neural imaging have enabled neuroscientists to study how large neural populations conspire to produce perception, behavior and cognition. Despite many advances in optical methods, there exists a fundamental tradeoff between imaging speed, field of view, and resolution that limits the scope of neural imaging, especially for the raster-scanning multi-photon imaging needed to image deeper into the brain. One approach to overcoming this trade-off is computational imaging: the co-development of optics designed to encode the target images into fewer measurements that are faster to acquire, with algorithms that compensate by inverting the optical coding to recover a larger or higher resolution image. We present here one such approach for raster-scanning two-photon imaging: Neuroimaging with Oblong Random Acquisition (NORA). NORA quickly acquires each frame in a microscopy video by subsampling only a fraction of the fast scanning lines, ignoring large portions of each frame. NORA mitigates the loss of information by 1) extending the point-spread function in the slow-scan direction to effectively integrate the fluorescence of several lines into a single set of measurements and 2) imaging different, randomly selected, lines at each frame. Rather than reconstruct the video frame-by-frame, NORA recovers full video sequences via nuclear-norm minimization on the pixels-by-time matrix, for which we prove theoretical guarantees on recovery. We simulated NORA imaging using the Neural Anatomy and Optical Microscopy (NAOMi) biophysical simulator, and used the simulations to demonstrate that NORA can accurately recover 400 um X 400 um fields of view at subsampling rates up to 20X, despite realistic noise and motion conditions. As NORA requires minimal changes to current microscopy systems, our results indicate that NORA can provide a promising avenue towards fast imaging of neural circuits.