zbMATH — the first resource for mathematics

Streaming low-rank matrix approximation with an application to scientific simulation. (English) Zbl 1420.65060

65F30 Other matrix algorithms (MSC2010)
68W20 Randomized algorithms
Full Text: DOI arXiv
[1] Physical Sciences Division, National Oceanic and Atmospheric Administration, Feb. 2019, https://www.esrl.noaa.gov/psd/.
[2] D. Achlioptas, Database-friendly random projections: Johnson–Lindenstrauss with binary coins, J. Comput. System Sci., 66 (2003), pp. 671–687. · Zbl 1054.68040
[3] N. Ailon and B. Chazelle, The fast Johnson–Lindenstrauss transform and approximate nearest neighbors, SIAM J. Comput., 39 (2009), pp. 302–322, https://doi.org/10.1137/060673096. · Zbl 1185.68327
[4] N. Alon, P. B. Gibbons, Y. Matias, and M. Szegedy, Tracking join and self-join sizes in limited storage, J. Comput. System Sci., 64 (2002), pp. 719–747, https://doi.org/10.1006/jcss.2001.1813. · Zbl 1051.68136
[5] N. Alon, Y. Matias, and M. Szegedy, The space complexity of approximating the frequency moments, in Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (Philadelphia, PA, 1996), ACM, New York, 1996, pp. 20–29, https://doi.org/10.1145/237814.237823. · Zbl 0922.68057
[6] W. Austin, G. Ballard, and T. G. Kolda, Parallel tensor compression for large-scale scientific data, in Proceedings of the 2016 IEEE International Symposium on Parallel and Distributed Processing, IEEE, Washington, DC, 2016, pp. 912–922.
[7] H. Avron and S. Toledo, Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix, J. ACM, 58 (2011), 8, https://doi.org/10.1145/1944345.1944349. · Zbl 1327.68331
[8] A. H. Baker, H. Xu, J. M. Dennis, M. N. Levy, D. Nychka, S. A. Mickelson, J. Edwards, M. Vertenstein, and A. Wegener, A methodology for evaluating the impact of data compression on climate simulation data, in Proceedings of the 23rd ACM International Symposium on High-Performance Parallel and Distributed Computing, ACM, New York, 2014, pp. 203–214.
[9] R. Baurle, Modeling of high speed reacting flows: Established practices and future challenges, in Proceedings of the 42nd AIAA Aerospace Sciences Meeting and Exhibit, Reno, NV, 2004, p. 267.
[10] A. Bejan, Convection Heat Transfer, John Wiley & Sons, New York, 2013.
[11] R. Bhatia, Matrix Analysis, Grad. Texts in Math. 169, Springer-Verlag, New York, 1997, https://doi.org/10.1007/978-1-4612-0653-8.
[12] J. Bourgain, S. Dirksen, and J. Nelson, Toward a unified theory of sparse dimensionality reduction in Euclidean space, Geom. Funct. Anal., 25 (2015), pp. 1009–1088, https://doi.org/10.1007/s00039-015-0332-9. · Zbl 1341.46007
[13] C. Boutsidis and A. Gittens, Improved matrix algorithms via the subsampled randomized Hadamard transform, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 1301–1340, https://doi.org/10.1137/120874540. · Zbl 1286.65054
[14] C. Boutsidis, D. Woodruff, and P. Zhong, Optimal Principal Component Analysis in Distributed and Streaming Models, preprint, https://arxiv.org/abs/1504.06729, 2016. · Zbl 1381.62140
[15] C. Boutsidis, D. Woodruff, and P. Zhong, Optimal principal component analysis in distributed and streaming models, in Proceedings of the 48th ACM Symposium on Theory of Computing (STOC 2016), Cambridge, MA, 2016, pp. 236–249. · Zbl 1381.62140
[16] M. Brand, Fast low-rank modifications of the thin singular value decomposition, Linear Algebra Appl., 415 (2006), pp. 20–30, https://doi.org/10.1016/j.laa.2005.07.021. · Zbl 1088.65037
[17] J. Calhoun, F. Cappello, L. N. Olson, M. Snir, and W. D. Gropp, Exploring the feasibility of lossy compression for PDE simulations, Internat. J. High Perform. Comput. Appl., 33 (2019), https://doi.org/10.1177/1094342018762036.
[18] S. Castruccio and M. G. Genton, Compressing an ensemble with statistical models: An algorithm for global \(3\)D spatio-temporal temperature, Technometrics, 58 (2016), pp. 319–328.
[19] CERN, Processing: What to Record, Feb. 2019, https://home.cern/science/computing/processing-what-record.
[20] K. L. Clarkson and D. P. Woodruff, Numerical linear algebra in the streaming model, in Proceedings of the 41st ACM Symposium on Theory of Computing (STOC), Bethesda, MD, 2009, pp. 205–214. · Zbl 1304.65138
[21] K. L. Clarkson and D. P. Woodruff, Low rank approximation and regression in input sparsity time, in Proceedings of the 45th ACM Symposium on Theory of Computing (STOC), ACM, New York, 2013, pp. 81–90, https://doi.org/10.1145/2488608.2488620. · Zbl 1293.65069
[22] M. Cohen, Nearly tight oblivious subspace embeddings by trace inequalities, in Proceedings of the 27th ACM–SIAM Symposium on Discrete Algorithms (SODA), Arlington, VA, 2016, pp. 278–287, https://doi.org/10.1137/1.9781611974331.ch21. · Zbl 1415.65106
[23] M. B. Cohen, S. Elder, C. Musco, C. Musco, and M. Persu, Dimensionality reduction for k-means clustering and low rank approximation, in Proceedings of the 47th ACM Symposium on Theory of Computing (STOC), ACM, New York, 2015, pp. 163–172. · Zbl 1321.68398
[24] J. D. Dixon, Estimating extremal eigenvalues and condition numbers of matrices, SIAM J. Numer. Anal., 20 (1983), pp. 812–814, https://doi.org/10.1137/0720053. · Zbl 0536.65022
[25] J. B. Drake, Climate Modeling for Scientists and Engineers, Math. Model. Comput. 19, SIAM, Philadelphia, 2014, https://doi.org/10.1137/1.9781611973549.
[26] D. Feldman, M. Volkov, and D. Rus, Dimensionality reduction of massive sparse datasets using coresets, in Proceedings of the 30th International Conference on Neural Information Processing Systems (NIPS), Barcelona, Spain, 2016, pp. 2774–2782.
[27] A. Frieze, R. Kannan, and S. Vempala, Fast Monte-Carlo algorithms for finding low-rank approximations, J. ACM, 51 (2004), pp. 1025–1041, https://doi.org/10.1145/1039488.1039494. · Zbl 1125.65005
[28] E. Garnier, N. Adams, and P. Sagaut, Large Eddy Simulation for Compressible Flows, Springer, Cham, 2009. · Zbl 1179.76005
[29] M. Ghashami, E. Liberty, J. M. Phillips, and D. P. Woodruff, Frequent directions: Simple and deterministic matrix sketching, SIAM J. Comput., 45 (2016), pp. 1762–1792, https://doi.org/10.1137/15M1009718. · Zbl 1348.65075
[30] M. X. Goemans and D. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. Assoc. Comput. Mach., 42 (1995), pp. 1115–1145. · Zbl 0885.68088
[31] S. Gratton and D. Titley-Peloquin, Improved bounds for small-sample estimation, SIAM J. Matrix Anal. Appl., 39 (2018), pp. 922–931, https://doi.org/10.1137/17M1137541. · Zbl 1451.65044
[32] A. Griewank and A. Walther, Algorithm 799: Revolve: An implementation of checkpointing for the reverse or adjoint mode of computational differentiation, ACM Trans. Math. Softw., 26 (2000), pp. 19–45, https://doi.org/10.1145/347837.347846. · Zbl 1137.65330
[33] J. Guinness and D. Hammerling, Compression and conditional emulation of climate model output, J. Amer. Stat. Assoc., 113 (2018), pp. 56–67. · Zbl 1398.68157
[34] N. Halko, P.-G. Martinsson, Y. Shkolnisky, and M. Tygert, An algorithm for the principal component analysis of large data sets, SIAM J. Sci. Comput., 33 (2011), pp. 2580–2594, https://doi.org/10.1137/100804139. · Zbl 1232.65058
[35] N. Halko, P. G. Martinsson, and J. A. Tropp, Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions, SIAM Rev., 53 (2011), pp. 217–288, https://doi.org/10.1137/090771806. · Zbl 1269.65043
[36] N. J. Higham, Matrix nearness problems and applications, in Applications of Matrix Theory (Bradford, 1988), Oxford University Press, New York, 1989, pp. 1–27.
[37] M. Hinze, A. Walther, and J. Sternberg, An optimal memory-reduced procedure for calculating adjoints of the instationary Navier-Stokes equations, Optim. Control Appl. Methods, 27 (2006), pp. 19–40, https://doi.org/10.1002/oca.771.
[38] R. Horstmeyer, R. Y. Chen, X. Ou, B. Ames, J. A. Tropp, and C. Yang, Solving ptychography with a convex relaxation, New J. Phys., 17 (2015), 053044.
[39] M. F. Hutchinson, A stochastic estimator of the trace of the influence matrix for Laplacian smoothing splines, Comm. Statist. Simul. Comput., 18 (1989), pp. 1059–1076, https://doi.org/10.1080/03610918908812806. · Zbl 0695.62113
[40] P. Indyk and R. Motwani, Approximate nearest neighbors: Towards removing the curse of dimensionality, in Proceedings of the 30th ACM Symposium on Theory of Computing (STOC), ACM, New York, 1998, pp. 604–613, https://doi.org/10.1145/276698.276876. · Zbl 1029.68541
[41] W. B. Johnson and J. Lindenstrauss, Extensions of Lipschitz mapping into Hilbert space, Contemp. Math., 26 (1984), pp. 189–206. · Zbl 0539.46017
[42] I. T. Jolliffe, Principal Component Analysis, 2nd ed., Springer Series in Statistics, Springer-Verlag, New York, 2002.
[43] Y. Li, H. L. Nguyen, and D. P. Woodruff, Turnstile streaming algorithms might as well be linear sketches, in Proceedings of the 46th ACM Symposium on Theory of Computing (STOC), ACM, New York, 2014, pp. 174–183. · Zbl 1315.68281
[44] E. Liberty, Accelerated Dense Random Projections, Ph.D. thesis, Yale University, New Haven, CT, 2009.
[45] M. Lopes, S. Wang, and M. Mahoney, Error estimation for randomized least-squares algorithms via the bootstrap, in Proceedings of the 35th International Conference on Machine Learning (ICML), Stockholm, Sweden, 2018, pp. 3223–3232.
[46] M. W. Mahoney, Randomized algorithms for matrices and data, Found. Trends Mach. Learning, 3 (2011), pp. 123–224.
[47] M. R. Malik, B. J. Isaac, A. Coussement, P. J. Smith, and A. Parente, Principal component analysis coupled with nonlinear regression for chemistry reduction, Combustion and Flame, 187 (2018), pp. 30–41.
[48] P.-G. Martinsson, Randomized Methods for Matrix Computations, preprint, https://arxiv.org/abs/1607.01649v3, 2019. · Zbl 1237.65028
[49] P.-G. Martinsson, V. Rokhlin, and M. Tygert, A randomized algorithm for the decomposition of matrices, Appl. Comput. Harmon. Anal., 30 (2011), pp. 47–68, https://doi.org/10.1016/j.acha.2010.02.003. · Zbl 1210.65095
[50] 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 ACM Symposium on Theory of Computing (STOC), ACM, New York, 2013, pp. 91–100, https://doi.org/10.1145/2488608.2488621. · Zbl 1293.68150
[51] F. R. Menter, M. Kuntz, and R. Langtry, Ten years of industrial experience with the SST turbulence model, Turbulence Heat Mass Transfer, 4 (2003), pp. 625–632.
[52] R. Moarref, A. S. Sharma, J. A. Tropp, and B. J. McKeon, Model-based scaling of the streamwise energy intensity in high-Reynolds-number turbulent channels, J. Fluid Mech., 734 (2013), pp. 275–316, https://doi.org/10.1017/jfm.2013.457. · Zbl 1294.76181
[53] S. Muthukrishnan, Data streams: Algorithms and applications, Found. Trends Theor. Comput. Sci., 1 (2005), pp. 117–236.
[54] J. Nelson and H. L. Nguyen, OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings, in Proceedings of the 54th IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Los Alamitos, CA, 2013, pp. 117–126, https://doi.org/10.1109/FOCS.2013.21.
[55] J. Nelson and H. L. Nguyen, Lower bounds for oblivious subspace embeddings, in Automata, Languages, and Programming. Part I, Lecture Notes in Comput. Sci. 8572, Springer, Heidelberg, 2014, pp. 883–894, https://doi.org/10.1007/978-3-662-43948-7_73. · Zbl 1398.68202
[56] C. H. Papadimitriou, P. Raghavan, H. Tamaki, and S. Vempala, Latent semantic indexing: A probabilistic analysis, J. Comput. System Sci., 61 (2000), pp. 217–235, https://doi.org/10.1006/jcss.2000.1711. · Zbl 0963.68063
[57] S. Patankar, Numerical Heat Transfer and Fluid Flow, CRC Press, Boca Raton, FL, 1980.
[58] R. W. Reynolds, N. A. Rayner, T. M. Smith, D. C. Stokes, and W. Wang, An improved in situ and satellite SST analysis for climate, J. Climate, 15 (2002), pp. 1609–1625.
[59] R. W. Reynolds, T. M. Smith, C. Liu, D. B. Chelton, K. S. Casey, and M. G. Schlax, Daily high-resolution-blended analyses for sea surface temperature, J. Climate, 20 (2007), pp. 5473–5496.
[60] V. Rokhlin, A. Szlam, and M. Tygert, A randomized algorithm for principal component analysis, SIAM J. Matrix Anal. Appl., 31 (2009), pp. 1100–1124, https://doi.org/10.1137/080736417. · Zbl 1198.65035
[61] F. Roosta-Khorasani and U. Ascher, Improved bounds on sample size for implicit matrix trace estimators, Found. Comput. Math., 15 (2015), pp. 1187–1212, https://doi.org/10.1007/s10208-014-9220-1. · Zbl 1323.65043
[62] P. Sagaut, Large Eddy Simulation for Incompressible Flows: An Introduction, Springer, Berlin, 2006. · Zbl 1091.76001
[63] T. Sarlós, Improved approximation algorithms for large matrices via random projections, in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Berkeley, CA, 2006, https://doi.org/10.1109/FOCS.2006.37.
[64] S. W. Son, Z. Chen, W. Hendrix, A. Agrawal, W.-k. Liao, and A. Choudhary, Data compression for the exascale computing era—survey, Supercomput. Frontiers Innovations, 1 (2014), pp. 76–88.
[65] Y. Sun, Y. Guo, J. A. Tropp, and M. Udell, Low-Rank Tucker Approximation of a Tensor from Streaming Data, manuscript, 2018.
[66] Y. Sun, Y. Guo, J. A. Tropp, and M. Udell, Tensor random projection for low memory dimension reduction, in NeurIPS Workshop on Relational Representation Learning, 2018, https://r2learning.github.io/assets/papers/CameraReadySubmission%2041.pdf.
[67] J. A. Tropp, Improved analysis of the subsampled randomized Hadamard transform, Adv. Adapt. Data Anal., 3 (2011), pp. 115–126, https://doi.org/10.1142/S1793536911000787. · Zbl 1232.15029
[68] J. A. Tropp, A. Yurtsever, M. Udell, and V. Cevher, Fixed-rank approximation of a positive-semidefinite matrix from streaming data, in Advances in Neural Information Processing Systems 30 (NIPS), Long Beach, CA, 2017. · Zbl 1379.65026
[69] J. A. Tropp, A. Yurtsever, M. Udell, and V. Cevher, Practical sketching algorithms for low-rank matrix approximation, SIAM J. Matrix Anal. Appl., 38 (2017), pp. 1454–1485, https://doi.org/10.1137/17M1111590. · Zbl 1379.65026
[70] J. A. Tropp, A. Yurtsever, M. Udell, and V. Cevher, Randomized Single-View Algorithms for Low-Rank Matrix Approximation, ACM Report 2017-01, Caltech, Pasadena, CA, 2017; preprint, https://arxiv.org/abs/1609.00048v1, 2016. · Zbl 1379.65026
[71] J. Upadhyay, Fast and Space-Optimal Low-Rank Factorization in the Streaming Model with Application in Differential Privacy, preprint, https://arxiv.org/abs/1604.01429v1, 2016.
[72] J. Woodring, S. Mniszewski, C. Brislawn, D. DeMarle, and J. Ahrens, Revisiting wavelet compression for large-scale climate data using JPEG 2000 and ensuring data precision, in Proceedings of the 2011 IEEE Symposium on Large Data Analysis and Visualization (LDAV), IEEE, Washington, DC, 2011, pp. 31–38.
[73] D. P. Woodruff, Sketching as a tool for numerical linear algebra, Found. Trends Theor. Comput. Sci., 10 (2014).
[74] F. Woolfe, E. Liberty, V. Rokhlin, and M. Tygert, A fast randomized algorithm for the approximation of matrices, Appl. Comput. Harmon. Anal., 25 (2008), pp. 335–366. · Zbl 1155.65035
[75] A. Yurtsever, M. Udell, J. A. Tropp, and V. Cevher, Sketchy decisions: Convex low-rank matrix optimization with optimal storage, in the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), Fort Lauderdale, FL, 2017. · Zbl 1379.65026
[76] G. Zhou, A. Cichocki, and S. Xie, Decomposition of Big Tensors with Low Multilinear Rank, preprint, https://arxiv.org/abs/1412.1885, 2014.
[77] R. Zimmermann, B. Pedersdorfer, and K. Willcox, Geometric subspace updates with applications to online adaptive nonlinear model reduction, SIAM J. Matrix Anal. Appl., 39 (2018), pp. 234–261, https://doi.org/10.1137/17M1123286. · Zbl 1383.65034
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.