An novel algorithm for computing holographic fringe patterns based on nonuniform sampling is described. We show both analytically and via simulation that nonuniform sampling reduces the number of samples required to represent the hologram, in some cases by as much as 30 to 40%. This method of computing compact holograms is information-theoretically lossless. Methods for decompressing the computed fringe pattern are also presented. The algorithm is implemented on the Massachusetts Institute of Technology (MIT) Mark II Holographic Video System and results demonstrating its performance are provided. To the best of the author’s knowledge, this is the first time that nonuniform sampling has been used to compress holographic fringe patterns for display purposes. The possibility of using other sophisticated nonuniform sampling approaches emerges from this research.