We have developed a new algorithm for the reconstruction of seismic traces randomly missing from a uniform grid of a 3D seismic volume. Several algorithms have been developed for such reconstructions, based on properties of the seismic wavefields and on signal processing concepts, such as sparse signal representation in a transform domain. We have investigated a novel approach, originally introduced for noise removal, which is based on the premise that for suitable representation of the seismic data as matrices or tensors, the rank of the seismic data (computed by singular value decomposition) increases with noise or missing traces. Thus, we apply low-rank matrix completion (MC) with a designed texture-patch transformation to 3D seismic data reconstruction. Low-rank components capture geometrically meaningful structures in seismic data that encompass conventional local features such as events and dips. The low-rank MC is based on nuclear-norm minimization. An efficient -norm minimizing algorithm, named approximate message passing, is extended to use for a general nonconvex nuclear-norm minimization problem. A fast MC algorithm named low-rank matrix fitting (LMaFit), which avoids the computation of singular value decomposition, was also considered for the 3D reconstruction. Empirical studies on synthetic and real data have shown promising performance of the method, in comparison with traditional projection onto convex sets.