A small random sample of rows/columns of any matrix is a decent proxy for the matrix, provided sampling probabilities are proportional to squared lengths. Since the early theorems on this from the 90's, there has been a substantial body of work using sampling (with more sophisticated probabilities) to reduce matrix sizes for Linear Algebra computations.The talk will describe theorems, applications and challenges in the area.
