Conventional ultrasound (US) image reconstruction methods rely on delay-and-sum (DAS) beamforming, which is a relatively poor solution to the image reconstruction problem. An alternative to DAS consists in using iterative techniques, which require both an accurate measurement model and a strong prior on the image under scrutiny. Toward this goal, much effort has been deployed in formulating models for US imaging, which usually require a large amount of memory to store the matrix coefficients. We present two different techniques, which take advantage of fast and matrix-free formulations derived for the measurement model and its adjoint, and rely on sparsity of US images in well-chosen models. Sparse regularization is used for enhanced image reconstruction. Compressed beamforming exploits the compressed sensing framework to restore high-quality images from fewer raw data than state-of-the-art approaches. Using simulated data and in vivo experimental acquisitions, we show that the proposed approach is three orders of magnitude faster than non-DAS state-of-the-art methods, with comparable or better image quality.