Despite recent developments in improved acquisition, seismic data often remain undersampled along source and receiver coordinates, resulting in incomplete data for key applications such as migration and multiple prediction. We have interpreted the missing- trace interpolation problem in the context of matrix completion (MC), and developed three practical principles for using lowrank optimization techniques to recover seismic data. Specifically, we strive for recovery scenarios wherein the original signal is low rank and the subsampling scheme increases the singular values of the matrix. We use an optimization program that restores this low-rank structure to recover the full volume. Omitting one or more of these principles can lead to poor interpolation results, as we found experimentally. In light of this theory, we compensate for the high-rank behavior of data in the source-receiver domain by using the midpoint-offset transformation for 2D data and a source-receiver permutation for 3D data to reduce the overall singular values. Simultaneously, towork with computationally feasible algorithms for large-scale data, we use a factorizationbased approach to MC, which significantly speeds up the computations compared with repeated singular value decompositions without reducing the recovery quality. In the context of our theory and experiments, we also find that windowing the data too aggressively can have adverse effects on the recovery quality. To overcome this problem, we carried out our interpolations for each frequency independently while working with the entire frequency slice. The result is a computationally efficient, theoretically motivated framework for interpolating missing-trace data. Our tests on realistic 2D and 3D seismic data sets show that our method compares favorably in terms of computational speed and recovery quality with existing curvelet- and tensor-based techniques.