Before revision:  We prove the worst-case property for each of the problems and their modified algorithms.abstract 
After revision:  We prove the worst-case property for each of the problems and their modified algorithms.abstract for the first time. We show that our algorithm is provably better in the spiked covariance model and for Zipfian matrices. We also show the importance of the sketch monotonicity property for combining learned sketches. Our empirical results show the importance of optimizing not only the values of the non-zero entries but also their positions.