Ultrasound Computed Tomography (UCT) is challenging due to phenomena such as strong refraction, multiple scattering, and mode conversion. In NDT, large speed of sound contrasts lead to strong artifacts if such phenomena are not modeled correctly; however, enhanced models are computationally expensive. In this work, a two-step framework for Compressed UCT based on the integral approach to the solution of the Helmholtz equation is presented. It comprises a physically motivated forward step and an imaging step that solves a suitable inverse problem. Multiple scattering is accounted for through the use of Neumann series. Convergence problems of Neumann series in high contrast settings are addressed via Padé approximants. Compressed sensing is employed to reduce the computational complexity of the reconstruction procedure by reducing data volumes directly at the measurement step, avoiding redundancy in the data and allowing the ability to steer the admissible computational effort at the expense of reconstruction quality. The proposed method is shown to yield high quality reconstructions under heavy subsampling in the frequency and spatial domains.