A central challenge in scanning transmission electron microscopy (STEM) is to reduce the electron radiation dosage required for accurate imaging of 3D biological nano-structures. Methods that permit tomographic reconstruction from a reduced number of STEM acquisitions without introducing significant degradation in the final volume are thus of particular importance. In random-beam STEM (RB-STEM), the projection measurements are acquired by randomly scanning a subset of pixels at every tilt view. In this work, we present a tailored RB-STEM acquisition-reconstruction framework that fully exploits the compressed sensing principles. We first demonstrate that RB-STEM acquisition fulfills the "incoherence" condition when the image is expressed in terms of wavelets. We then propose a regularized tomographic reconstruction framework to recover volumes from RB-STEM measurements. We demonstrate through simulations on synthetic and real projection measurements that the proposed framework reconstructs high-quality volumes from strongly downsampled RB-STEM data and outperforms existing techniques at doing so. This application of compressed sensing principles to STEM paves the way for a practical implementation of RB-STEM and opens new perspectives for high-quality reconstructions in STEM tomography. (C) 2017 The Authors. Published by Elsevier B.V.