Relative recovery error as a function of the extent of undersampling.  As the matrix to recover grows less sparse, more samples are required for accurate recovery.  Note the logarithmic scale, indicating an abrupt transition to accurate recovery.