152 Handbook of Big Data
29. P. Drineas, M. W. Mahoney, and S. Muthukrishnan. Subspace sampling and relative-
error matrix approximation: Column-based methods. In Proceedings of the 10th
International Workshop on Randomization and Computation, pp. 316–326, 2006.
30. P. Drineas, M. W. Mahoney, and S. Muthukrishnan. Relative-error CUR matrix
decompositions. SIAM Journal on Matrix Analysis and Applications, 30:844–881, 2008.
31. P. Drineas, M. W. Mahoney, S. Muthukrishnan, and T. Sarl´os. Faster least squares
approximation. Numerische Mathematik, 117(2):219–249, 2010.
32. D. Feldman and M. Langberg. A unified framework for approximating and clustering
data. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing,
pp. 569–578, 2011.
33. D. Feldman, M. Monemizadeh, C. Sohler, and D. P. Woodruff. Coresets and sketches for
high dimensional subspace approximation problems. In Proceedings of the 21st Annual
ACM-SIAM Symposium on Discrete Algorithms, pp. 630–649, 2010.
34. A. Frieze, R. Kannan, and S. Vempala. Fast Monte-Carlo algorithms for finding low-rank
approximations. In Proceedings of the 39th Annual IEEE Symposium on Foundations
of Computer Science, pp. 370–378, 1998.
35. A. Gittens. The spectral norm error of the naive Nystr¨om extension. Technical report.
Preprint: arXiv:1110.5305, 2011.
36. A. Gittens and M. W. Mahoney. Revisiting the Nystr¨om method for improved large-
scale machine learning. Technical report. Preprint: arXiv:1303.1849, 2013.
37. G. H. Golub. Numerical methods for solving linear least squares problems. Numerische
Mathematik, 7:206–216, 1965.
38. G. H. Golub and C. F. Van Loan. Matrix Computations. Johns Hopkins University
Press, Baltimore, MD, 1989.
39. G. H. Golub and C. F. Van Loan. Matrix Computations. Johns Hopkins University
Press, Baltimore, MD, 1996.
40. M. Gu. Subspace iteration randomization and singular value problems. Technical report.
Preprint: arXiv:1408.2208, 2014.
41. M. Gu and S. C. Eisenstat. Efficient algorithms for computing a strong rank-revealing
QR factorization. SIAM Journal on Scientific Computing, 17:848–869, 1996.
42. V. Guruswami and A. K. Sinop. Optimal column-based low-rank matrix reconstruction.
In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pp.
1207–1214, 2012.
43. N. Halko, P.-G. Martinsson, Y. Shkolnisky, and M. Tygert. An algorithm for the princi-
pal component analysis of large data sets. Technical report. Preprint: arXiv:1007.5510,
2010.
44. N. Halko, P.-G. Martinsson, and J. A. Tropp. Finding structure with randomness:
Probabilistic algorithms for constructing approximate matrix decompositions. SIAM
Review, 53(2):217–288, 2011.
45. R.A. Horn and C.R. Johnson. Matrix Analysis. Cambridge University Press, New York,
1985.
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.
154 Handbook of Big Data
61. V. Rokhlin, A. Szlam, and M. Tygert. A randomized algorithm for principal component
analysis. SIAM Journal on Matrix Analysis and Applications, 31(3):1100–1124, 2009.
62. V. Rokhlin and M. Tygert. A fast randomized algorithm for overdetermined linear least-
squares regression. Proceedings of the National Academy of Sciences of the United States
of America, 105(36):13212–13217, 2008.
63. T. Sarl´os. Improved approximation algorithms for large matrices via random projec-
tions. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer
Science, pp. 143–152, 2006.
64. B. Sch¨olkopf and A. J. Smola. Learning with Kernels: Support Vector Machines,
Regularization, Optimization, and Beyond. MIT Press, Cambridge, MA, 2001.
65. N. D. Shyamalkumar and K. Varadarajan. Efficient subspace approximation algorithms.
In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms,
pp. 532–540, 2007.
66. P. F. Velleman and R. E. Welsch. Efficient computing of regression diagnostics. The
American Statistician, 35(4):234–242, 1981.
67. C. K. I. Williams and M. Seeger. Using the Nystr¨om method to speed up kernel ma-
chines. In Annual Advances in Neural Information Processing Systems 13: Proceedings
of the 2000 Conference, pp. 682–688, 2001.
68. D. P. Woodruff. Sketching as a tool for numerical linear algebra. In Foundations and
Trends in Theoretical Computer Science. NOW Publishers, Boston, MA, 2014.
69. F. Woolfe, E. Liberty, V. Rokhlin, and M. Tygert. A fast randomized algorithm for
the approximation of matrices. Applied and Computational Harmonic Analysis, 25(3):
335–366, 2008.
70. J. Yang, X. Meng, and M. W. Mahoney. Quantile regression for large-scale applications.
SIAM Journal on Scientific Computing, 36:S78–S110, 2014.
71. J. Yang, X. Meng, and M. W. Mahoney. Implementing randomized matrix algorithms
in parallel and distributed environments. Technical report. Preprint: arXiv:1502.03032,
2015.
72. J. Yang, O. Rubel, Prabhat, M. W. Mahoney, and B. P. Bowen. Identifying important
ions and positions in mass spectrometry imaging data using CUR matrix decomposi-
tions. Analytical Chemistry, 87(9):4658–4666, 2015.
73. C.-W.Yip,M.W.Mahoney,A.S.Szalay,I.Csabai,T.Budavari,R.F.G.Wyse,and
L. Dobos. Objective identification of informative wavelength regions in galaxy spectra.
The Astronomical Journal, 147(110):15, 2014.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.