Structural Properties Underlying Randomized Linear Algebra Algorithms 153
46. A. Javed, P. Drineas, M. W. Mahoney, and P. Paschou. Efficient genomewide selection
of PCA-correlated tSNPs for genotype imputation. Annals of Human Genetics, 75(6):
707–722, 2011.
47. E. Liberty, F. Woolfe, P.-G. Martinsson, V. Rokhlin, and M. Tygert. Randomized
algorithms for the low-rank approximation of matrices. Proceedings of the National
Academy of Sciences of the United States of America, 104(51):20167–20172, 2007.
48. P. Ma, M. W. Mahoney, and B. Yu. A statistical perspective on algorithmic leveraging.
Journal of Machine Learning Research, 32(1):91–99, 2014.
49. M. W. Mahoney. Randomized algorithms for matrices and data. In Foundations and
Trends in Machine Learning. NOW Publishers, Boston, MA, 2011.
50. M. W. Mahoney and P. Drineas. CUR matrix decompositions for improved data
analysis. Proceedings of the National Academy of Sciences of the United States of
America, 106:697–702, 2009.
51. J. Manyika, M. Chui, B. Brown, J. Bughin, R. Dobbs, C. Roxburgh, and A. H. Byers.
Big data: The next frontier for innovation, competition, and productivity. Technical
report, McKinsey Global Institute, 2011.
52. P.-G. Martinsson, V. Rokhlin, and M. Tygert. A randomized algorithm for the
decomposition of matrices. Applied and Computational Harmonic Analysis, 30:47–68,
2011.
53. X. Meng and M. W. Mahoney. Low-distortion subspace embeddings in input-sparsity
time and applications to robust linear regression. In Proceedings of the 45th Annual
ACM Symposium on Theory of Computing, pp. 91–100, 2013.
54. X. Meng and M. W. Mahoney. Robust regression on MapReduce. In Proceedings of the
30th International Conference on Machine Learning, 2013.
55. X. Meng, M. A. Saunders, and M. W. Mahoney. LSRN: A parallel iterative solver for
strongly over- or under-determined systems. SIAM Journal on Scientific Computing,
36(2):C95–C118, 2014.
56. J. Nelson and N. L. Huy. OSNAP: Faster numerical linear algebra algorithms via
sparser subspace embeddings. In Proceedings of the 54th Annual IEEE Symposium on
Foundations of Computer Science, pp. 117–126, 2013.
57. C. H. Papadimitriou, P. Raghavan, H. Tamaki, and S. Vempala. Latent semantic
indexing: A probabilistic analysis. In Proceedings of the 17th ACM Symposium on
Principles of Database Systems, pp. 159–168, 1998.
58. C. H. Papadimitriou, P. Raghavan, H. Tamaki, and S. Vempala. Latent semantic
indexing: A probabilistic analysis. Journal of Computer and System Sciences, 61(2):
217–235, 2000.
59. P. Paschou, J. Lewis, A. Javed, and P. Drineas. Ancestry informative markers for fine-
scale individual assignment to worldwide populations. Journal of Medical Genetics,
doi:10.1136/jmg.2010.078212, 2010.
60. P. Paschou, E. Ziv, E. G. Burchard, S. Choudhry, W. Rodriguez-Cintron, M. W.
Mahoney, and P. Drineas. PCA-correlated SNPs for structure identification in worldwide
human populations. PLoS Genetics, 3:1672–1686, 2007.