{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,15]],"date-time":"2025-12-15T14:13:51Z","timestamp":1765808031098,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,5,26]],"date-time":"2022-05-26T00:00:00Z","timestamp":1653523200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2022,6,30]]},"abstract":"<jats:p>In this article, we propose a computationally efficient iterative algorithm for proper orthogonal decomposition (POD) using random sampling based techniques. In this algorithm, additional rows and columns are sampled and a merging technique is used to update the dominant POD modes in each iteration. We derive bounds for the spectral norm of the error introduced by a series of merging operations. We use an existing theorem to get an approximate measure of the quality of subspaces obtained on convergence of the iteration. Results on various datasets indicate that the POD modes and\/or the subspaces are approximated with excellent accuracy with a significant runtime improvement over computing the truncated SVD. We also propose a method to compute the POD modes of large matrices that do not fit in the RAM using this iterative sampling and merging algorithms.<\/jats:p>","DOI":"10.1145\/3506691","type":"journal-article","created":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T11:31:55Z","timestamp":1648639915000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Fast and Accurate Proper Orthogonal Decomposition using Efficient Sampling and Iterative Techniques for Singular Value Decomposition"],"prefix":"10.1145","volume":"48","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1864-0631","authenticated-orcid":false,"given":"V.","family":"Charumathi","sequence":"first","affiliation":[{"name":"Indian Institute of Technology, Tamilnadu, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2089-637X","authenticated-orcid":false,"given":"M.","family":"Ramakrishna","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology, Tamilnadu, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7039-3821","authenticated-orcid":false,"given":"Vinita","family":"Vasudevan","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology, Tamilnadu, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,5,26]]},"reference":[{"key":"e_1_3_3_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1219092.1219097"},{"key":"e_1_3_3_3_1","first-page":"471","volume-title":"Advanced Parallel Processing Technologies","author":"Bai Zheng-Jian","year":"2005","unstructured":"Zheng-Jian Bai, Raymond H. Chan, and Franklin T. Luk. 2005. Principal component analysis for distributed data sets with updating. In Advanced Parallel Processing Technologies. Jiannong Cao, Wolfgang Nejdl, and Ming Xu (Eds.), Springer, Berlin, 471\u2013483."},{"key":"e_1_3_3_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2011.07.018"},{"key":"e_1_3_3_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-05089-8"},{"key":"e_1_3_3_6_1","doi-asserted-by":"publisher","DOI":"10.2307\/2005662"},{"key":"e_1_3_3_7_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btz157"},{"key":"e_1_3_3_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-47969-4_47"},{"key":"e_1_3_3_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2005.07.021"},{"key":"e_1_3_3_10_1","unstructured":"AT&T Laboratories Cambridge. 2002. The Database of Faces. (2002). Retrieved 05 Jan. 2018 from http:\/\/www.cl.cam.ac.uk\/research\/dtg\/attarchive\/facedatabase.html."},{"key":"e_1_3_3_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688073.2688113"},{"key":"e_1_3_3_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109681"},{"key":"e_1_3_3_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11830924_28"},{"key":"e_1_3_3_14_1","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/3-540-38076-0_19","volume-title":"Advances in Informatics","author":"Drineas Petros","year":"2003","unstructured":"Petros Drineas, Eleni Drinea, and Patrick S. Huggins. 2003. An experimental evaluation of a monte-carlo algorithm for singular value decomposition. In Advances in Informatics, Yannis Manolopoulos, Skevos Evripidou, and Antonis C. Kakas (Eds.). Springer, Berlin, 279\u2013296."},{"key":"e_1_3_3_15_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:MACH.0000033113.59016.96"},{"key":"e_1_3_3_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704442696"},{"key":"e_1_3_3_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2842602"},{"key":"e_1_3_3_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/07070471X"},{"key":"e_1_3_3_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCVW.2017.222"},{"key":"e_1_3_3_20_1","doi-asserted-by":"publisher","DOI":"10.18637\/jss.v089.i"},{"key":"e_1_3_3_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039494"},{"key":"e_1_3_3_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.927464"},{"key":"e_1_3_3_23_1","volume-title":"Matrix Computations (3 ed.)","author":"Golub Gene H.","year":"2007","unstructured":"Gene H. Golub and Charles F. Van Loan. 2007. Matrix Computations (3 ed.). Hindustan Book agency."},{"key":"e_1_3_3_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/130938700"},{"key":"e_1_3_3_25_1","unstructured":"Ming Gu and Stanley C. Eisenstat. 1993. A stable and fast algorithm for updating the singular value decomposition. Technical Report. YALEU\/DCS\/RR-966. Dept. of Computer Science Yale University."},{"key":"e_1_3_3_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/100804139"},{"key":"e_1_3_3_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/090771806"},{"key":"e_1_3_3_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1058467"},{"key":"e_1_3_3_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2005.92"},{"key":"e_1_3_3_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3004053"},{"key":"e_1_3_3_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.22"},{"key":"e_1_3_3_32_1","volume-title":"Relative Perturbation Theory: (II) Eigenspace and Singular Subspace Variations","author":"Li Ren-Cang","year":"1996","unstructured":"Ren-Cang Li. 1996. Relative Perturbation Theory: (II) Eigenspace and Singular Subspace Variations. Technical Report Lapack working note #85. Oak Ridge National Laboratories."},{"key":"e_1_3_3_33_1","volume-title":"Handbook of Linear Algebra","author":"Li Ren-Cang","year":"2014","unstructured":"Ren-Cang Li. 2014. Matrix perturbation theory. In Handbook of Linear Algebra. L. Hogben (Ed.), Chapman and Hall\/CRC."},{"key":"e_1_3_3_34_1","first-page":"3113","volume-title":"Advances in Neural Information Processing Systems 27","author":"Liang Yingyu","year":"2014","unstructured":"Yingyu Liang, Maria-Florina F. Balcan, Vandana Kanchanapally, and David Woodruff. 2014. Improved distributed principal component analysis. In Advances in Neural Information Processing Systems 27. Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger (Eds.), Curran Associates, Inc., 3113\u20133121. Retrieved from http:\/\/papers.nips.cc\/paper\/5619-improved-distributed-principal-component-analysis.pdf."},{"key":"e_1_3_3_35_1","volume-title":"Handbook of Linear Algebra","author":"Mathias R.","year":"2014","unstructured":"R. Mathias. 2014. Singular values and singular value inequalities. In Handbook of Linear Algebra. L. Hogben (Ed.), Chapman and Hall\/CRC."},{"key":"e_1_3_3_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1921632.1921639"},{"key":"e_1_3_3_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536446"},{"key":"e_1_3_3_38_1","first-page":"1788","volume-title":"Proceedings of IEEE International Conference on Data Mining (ICDM)","volume":"1318","author":"Qu Yongming","year":"2002","unstructured":"Yongming Qu, George Ostrouchov, Nagiza Samatova, and Al Geist. 2002. Principal component analysis for dimension reduction in massive distributed data sets. In Proceedings of IEEE International Conference on Data Mining (ICDM), Vol. 1318. 1788."},{"key":"e_1_3_3_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/080736417"},{"key":"e_1_3_3_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.37"},{"key":"e_1_3_3_41_1","volume-title":"Matrix Perturbation Theory","author":"Stewart G. W.","year":"1990","unstructured":"G. W. Stewart and Ji guang Sun. 1990. Matrix Perturbation Theory. Academic Press. lc90033378"},{"key":"e_1_3_3_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972771.33"},{"key":"e_1_3_3_43_1","unstructured":"Vinita Vasudevan and M. Ramakrishna. 2017. A hierarchical singular value decomposition algorithm for low rank matrices. (October 2017). arXiv:1710.02812. Retrieved from https:\/\/arxiv.org\/abs\/1710.02812."},{"key":"e_1_3_3_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01932678"},{"key":"e_1_3_3_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2017.8257997"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3506691","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3506691","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:11:50Z","timestamp":1750191110000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3506691"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,26]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6,30]]}},"alternative-id":["10.1145\/3506691"],"URL":"https:\/\/doi.org\/10.1145\/3506691","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"type":"print","value":"0098-3500"},{"type":"electronic","value":"1557-7295"}],"subject":[],"published":{"date-parts":[[2022,5,26]]},"assertion":[{"value":"2020-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-05-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}