Understand
Datasets that are terabytes in size are increasingly common, but computer bottlenecks often frustrate a complete analysis of the data.
- While more data are better than less, diminishing returns suggest that we may not need terabytes of data to estimate a parameter or test a hypothesis.
- But which rows of data should we analyze, and might an arbitrary subset of rows preserve the features of the original data? This paper reviews a line of work that is grounded in theoretical computer science and numerical linear algebra, and which finds that an algorithmically desirable sketch, which is a randomly chosen subset of the data, must preserve the eigenstructure of the data, a property known as a subspace embedding.
- Building on this work, we study how prediction and inference can be affected by data sketching within a linear regression setup.