We develop a fast algorithm for solving the under-determined 3D linear gravity inverse problem based on randomized singular-value decomposition (RSVD). The algorithm combines an iteratively reweighted approach for -norm regularization with the RSVD methodology in which the large-scale linear system at each iteration is replaced with a much smaller linear system. Although the optimal choice for the low-rank approximation of the system matrix with rows is , acceptable results are achievable with . In contrast to the use of the iterative LSQR algorithm for the solution of linear systems at each iteration, the singular values generated using RSVD yield a good approximation of the dominant singular values of the large-scale system matrix. Thus, the regularization parameter found for the small system at each iteration is dependent on the dominant singular values of the large-scale system matrix and appropriately regularizes the dominant singular space of the large-scale problem. The results achieved are comparable with those obtained using the LSQR algorithm for solving each linear system, but they are obtained at a reduced computational cost. The method has been tested on synthetic models along with real gravity data from the Morro do Engenho complex in central Brazil.