SENSitivity Encoding (SENSE) is a mathematically optimal parallel magnetic resonance (MRI) imaging technique when the coil sensitivities are known. In recent times, compressed sensing (CS)-based techniques are incorporated within the SENSE reconstruction framework to recover the underlying MR image. CS-based techniques exploit the fact that the MR images are sparse in a transform domain (e.g., wavelets). Mathematically, this leads to an l(1)-norm-regularized SENSE reconstruction. In this work, we show that instead of reconstructing the image by exploiting its transform domain sparsity, we can exploit its rank deficiency to reconstruct it. This leads to a nuclear norm-regularized SENSE problem. The reconstruction accuracy from our proposed method is the same as the l(1)-norm-regularized SENSE, but the advantage of our method is that it is about an order of magnitude faster.