We address the problem of identifying underground anomalies (e.g. holes) based on gravity measurements. This is theoretically well-studied and difficult problem. In all except a few special cases, the inverse problem has multiple solutions, and additional constraints are needed to regularize it. Our approach makes general assumptions about the shape of the anomaly that can be seen as sparsity assumptions. Then we adapt recently developed sparse reconstruction algorithms to bear on this problem. The results are extremely promising, even though the theoretical assumptions underlying sparse recovery do not hold for gravity problems of this kind. We examine several types of sparse bases in the context of the gravity inverse problem and compare and contrast their relative merit.