Reducing size of data sets while preserving their mathematical properties So I'm looking at the paper $l_p$ Row Sampling by Lewis Weights in which the authors provide a method to sample the rows of a matrix while preserving their mathematical properties.
More specifically they talk about preserving the $l_2$ and $l_1$ norms of the original matrix in the sub-sampled one. The authors mention:

The p = 1 case is of particular interest due to its relation to robust regression, or $l_1$-regression

They go on to cite the compressive sampling paper.
My question is: For practical matters why is the preservation of the $l_p$ norms important? What kind of guarantees do we get when these norms are preserved in the sub-sampled matrix when it comes, for example, to statistical learning/modeling?
 A: Data compression is a kind of hoary topic wrt massive data. There is a distinction to be made, however, between compression algorithms such as gzip, tar or winzip and data summarization routines, which are less well known but attempt to create reduced, summary data structures for easier storage. Compression algorithms are efforts focused on reducing the size of data while summarization algorithms attempt to reduce the size while also retaining statistical information related to the variability and covariation inherent in the data. The former is largely the province of computer scientists while the latter is the focus of statisticians.
The pioneers in the summarization field were, for the most part, statisticians at Bell Labs back in the 90s who were facing some of the earliest challenges of big data wrt the rapidly sprawling AT&T databases. These included William DuMouchel and Diane Lambert who wrote some of the earliest data squashing algorithms -- as summarization routines were then called. 
These early approaches were brought to the attention of a wider statistical audience at the first joint NSF/ASA conference on massive data in 1996. Massive data became big data but that's no matter. Here's a link to a 2002 ebook that summarizes that early, still excellent work: The Handbook of Massive Data Sets. It is free and fully hyperlinked. In particular, see all of Part III (CS algs) and DuMouchel's paper in Part IV (a stats approach):
      http://mauricio.resende.info/hmds.html

So, I think that at least partly addresses your question. Not knowing anything about your background, it is likely that you are coming at it from a computer science frame of reference where there is less emphasis put on  retaining information about data variability. For statisticians, the variance in information is extremely valuable and important: in a sense, it is the whole story. Therefore, developing routines sensitive to this requirement has been the key goal. 
That said, the compression algorithms have won the day, so to speak, as the squashing algorithms have been, for the most part, sidelined and nowhere near as widely used. 
