\label{fig:NumericsResults} Percent of entries that must be sampled for accurate recovery of a matrix as a function of sparsity. Comparison between compressed sensing and two limiting cases: ``no prior knowledge'' of sparsity and the ``perfect oracle'' who reveals where all non-zero entries are located.  Each point on the compressed sensing curve is an average of ten different randomizations.  The accuracy criterion is a relative error in the Frobenius norm smaller than \(10^{-7}\). 