Before revision:  In the spirit of compressed sensing, the dimension reduction is determined by the Gaussian width of a structure associated to the data set, rather than its size . The Gaussian width also turns out to be useful for studying the complexity of other methods for approximating persistent homology  .
After revision:  In the spirit of compressed sensing, the dimension reduction is determined by the Gaussian width of a structure associated to the data set, rather than its size , and such a reduction can be computed efficiently. We further relate the Gaussian width to the doubling dimension of a finite metric space, which appears in the study of the complexity of other methods for approximating persistent homology .