{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,20]],"date-time":"2025-08-20T12:35:59Z","timestamp":1755693359776},"reference-count":38,"publisher":"Walter de Gruyter GmbH","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,9,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Low-rank matrix approximation is extremely useful in the analysis of data that arises in scientific computing, engineering applications, and data science. However, as data sizes grow, traditional low-rank matrix approximation methods, such as singular value decomposition (SVD) and column pivoting QR decomposition (CPQR), are either prohibitively expensive or cannot provide sufficiently accurate results.\nA solution is to use randomized low-rank matrix approximation methods such as randomized SVD, and randomized LU decomposition on extremely large data sets. In this paper, we focus on the randomized LU decomposition method. Then we propose a novel randomized LU algorithm, called SubspaceLU, for the fixed low-rank approximation problem. SubspaceLU is based on the sketch of the co-range of input matrices and allows for an arbitrary number of passes of the input matrix, <jats:inline-formula id=\"j_mcma-2023-2012_ineq_9999\">\n                     <jats:alternatives>\n                        <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                           <m:mrow>\n                              <m:mi>v<\/m:mi>\n                              <m:mo>\u2265<\/m:mo>\n                              <m:mn>2<\/m:mn>\n                           <\/m:mrow>\n                        <\/m:math>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/j_mcma-2023-2012_eq_0238.png\" \/>\n                        <jats:tex-math>{v\\geq 2}<\/jats:tex-math>\n                     <\/jats:alternatives>\n                  <\/jats:inline-formula>. Numerical experiments on CPU show that our proposed SubspaceLU is generally faster than the existing randomized LU decomposition, while remaining accurate. Experiments on GPU shows that our proposed SubspaceLU can gain more speedup than the existing randomized LU decomposition.\nWe also propose a version of SubspaceLU, called SubspaceLU_FP, for the fixed precision low-rank matrix approximation problem. SubspaceLU_FP is a post-processing step based on an efficient blocked adaptive rank determination Algorithm 5 proposed in this paper.\nWe present numerical experiments that show that SubspaceLU_FP can achieve close results to SVD but faster in speed. We finally propose a single-pass algorithm based on LU factorization. Tests show that the accuracy of our single-pass algorithm is comparable with the existing single-pass algorithms.<\/jats:p>","DOI":"10.1515\/mcma-2023-2012","type":"journal-article","created":{"date-parts":[[2023,8,21]],"date-time":"2023-08-21T10:51:23Z","timestamp":1692615083000},"page":"181-202","source":"Crossref","is-referenced-by-count":2,"title":["Pass-efficient randomized LU algorithms for computing low-rank matrix approximation"],"prefix":"10.1515","volume":"29","author":[{"given":"Bolong","family":"Zhang","sequence":"first","affiliation":[{"name":"Department of Computer Science , Florida State University , Tallahassee , FL 32306-4530 , USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Mascagni","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Department of Mathematics, Department of Scientific Computing , Florida State University , Tallahassee , FL 32306-4530 ; and National Institute of Standards & Technology, Information Technology Laboratory, Applied and Computational Mathematics Division, Gaithersburg, MD 20899-8910 , USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"374","published-online":{"date-parts":[[2023,8,22]]},"reference":[{"key":"2023083109202714685_j_mcma-2023-2012_ref_001","doi-asserted-by":"crossref","unstructured":"E. K.  Bjarkason,\nPass-efficient randomized algorithms for low-rank matrix approximation using any number of views,\nSIAM J. Sci. Comput. 41 (2019), no. 4, A2355\u2013A2383.","DOI":"10.1137\/18M118966X"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_002","doi-asserted-by":"crossref","unstructured":"R.  Dai, L.  Li and W.  Yu,\nFast training and model compression of gated rnns via singular value decomposition,\n2018 International Joint Conference on Neural Networks (IJCNN),\nIEEE Press, Piscataway (2018), 1\u20137.","DOI":"10.1109\/IJCNN.2018.8489156"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_003","doi-asserted-by":"crossref","unstructured":"P.  Drineas, R.  Kannan and M. W.  Mahoney,\nFast Monte Carlo algorithms for matrices. I. Approximating matrix multiplication,\nSIAM J. Comput. 36 (2006), no. 1, 132\u2013157.","DOI":"10.1137\/S0097539704442684"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_004","doi-asserted-by":"crossref","unstructured":"P.  Drineas, R.  Kannan and M. W.  Mahoney,\nFast Monte Carlo algorithms for matrices. II. Computing a low-rank approximation to a matrix,\nSIAM J. Comput. 36 (2006), no. 1, 158\u2013183.","DOI":"10.1137\/S0097539704442696"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_005","doi-asserted-by":"crossref","unstructured":"P.  Drineas, R.  Kannan and M. W.  Mahoney,\nFast Monte Carlo algorithms for matrices. III. Computing a compressed approximate matrix decomposition,\nSIAM J. Comput. 36 (2006), no. 1, 184\u2013206.","DOI":"10.1137\/S0097539704442702"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_006","doi-asserted-by":"crossref","unstructured":"P.  Drineas and M. W.  Mahoney,\nRandNLA: Randomized numerical linear algebra,\nComm. ACM 59 (2016), no. 6, 80\u201390.","DOI":"10.1145\/2842602"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_007","doi-asserted-by":"crossref","unstructured":"P.  Drineas and M. W.  Mahoney,\nLectures on randomized numerical linear algebra,\nThe Mathematics of Data,\nIAS\/Park City Math. Ser. 25,\nAmerican Mathematical Society, Providence (2018), 1\u201348.","DOI":"10.1090\/pcms\/025\/01"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_008","doi-asserted-by":"crossref","unstructured":"C.  Eckart and G.  Young,\nThe approximation of one matrix by another of lower rank,\nPsychometrika 1 (1936), no. 3, 211\u2013218.","DOI":"10.1007\/BF02288367"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_009","doi-asserted-by":"crossref","unstructured":"M.  Elad and M.  Aharon,\nImage denoising via sparse and redundant representations over learned dictionaries,\nIEEE Trans. Image Process. 15 (2006), no. 12, 3736\u20133745.","DOI":"10.1109\/TIP.2006.881969"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_010","unstructured":"G. H.  Golub and C. F.  Van Loan,\nMatrix Computations. Vol. 3,\nJohns Hopkins University, Baltimore, 2012."},{"key":"2023083109202714685_j_mcma-2023-2012_ref_011","unstructured":"A.  Gopal and P.-G.  Martinsson,\nThe PowerURV algorithm for computing rank-revealing full factorizations,\npreprint (2018), https:\/\/arxiv.org\/abs\/1812.06007."},{"key":"2023083109202714685_j_mcma-2023-2012_ref_012","doi-asserted-by":"crossref","unstructured":"M.  Gu and S. C.  Eisenstat,\nEfficient algorithms for computing a strong rank-revealing QR factorization,\nSIAM J. Sci. Comput. 17 (1996), no. 4, 848\u2013869.","DOI":"10.1137\/0917055"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_013","doi-asserted-by":"crossref","unstructured":"N.  Halko, P. G.  Martinsson and J. A.  Tropp,\nFinding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions,\nSIAM Rev. 53 (2011), no. 2, 217\u2013288.","DOI":"10.1137\/090771806"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_014","doi-asserted-by":"crossref","unstructured":"R.  Kannan and S.  Vempala,\nRandomized algorithms in numerical linear algebra,\nActa Numer. 26 (2017), 95\u2013135.","DOI":"10.1017\/S0962492917000058"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_015","doi-asserted-by":"crossref","unstructured":"H. A. L.  Kiers,\nTowards a standardized notation and terminology in multiway analysis,\nJ. Chemometrics 14 (2000), no. 3, 105\u2013122.","DOI":"10.1002\/1099-128X(200005\/06)14:3<105::AID-CEM582>3.0.CO;2-I"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_016","doi-asserted-by":"crossref","unstructured":"T. G.  Kolda and B. W.  Bader,\nTensor decompositions and applications,\nSIAM Rev. 51 (2009), no. 3, 455\u2013500.","DOI":"10.1137\/07070111X"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_017","doi-asserted-by":"crossref","unstructured":"H.  Li, G. C.  Linderman, A.  Szlam, K. P.  Stanton, Y.  Kluger and M.  Tygert,\nAlgorithm 971: An implementation of a randomized algorithm for principal component analysis,\nACM Trans. Math. Software 43 (2017), no. 3, Article ID 28.","DOI":"10.1145\/3004053"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_018","doi-asserted-by":"crossref","unstructured":"H.  Li and S.  Yin,\nSingle-pass randomized algorithms for LU decomposition,\nLinear Algebra Appl. 595 (2020), 101\u2013122.","DOI":"10.1016\/j.laa.2020.03.001"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_019","doi-asserted-by":"crossref","unstructured":"M. W.  Mahoney,\nRandomized algorithms for matrices and data,\nFound. Trends Mach. Learn. 3 (2011), no. 2, 123\u2013224.","DOI":"10.1561\/2200000035"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_020","doi-asserted-by":"crossref","unstructured":"M. W.  Mahoney and P.  Drineas,\nCUR matrix decompositions for improved data analysis,\nProc. Natl. Acad. Sci. USA 106 (2009), no. 3, 697\u2013702.","DOI":"10.1073\/pnas.0803205106"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_021","doi-asserted-by":"crossref","unstructured":"P.-G.  Martinsson and S.  Voronin,\nA randomized blocked algorithm for efficiently computing rank-revealing factorizations of matrices,\nSIAM J. Sci. Comput. 38 (2016), no. 5, S485\u2013S507.","DOI":"10.1137\/15M1026080"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_022","doi-asserted-by":"crossref","unstructured":"L.  Miranian and M.  Gu,\nStrong rank revealing LU factorizations,\nLinear Algebra Appl. 367 (2003), 1\u201316.","DOI":"10.1016\/S0024-3795(02)00572-4"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_023","doi-asserted-by":"crossref","unstructured":"I. V.  Oseledets,\nTensor-train decomposition,\nSIAM J. Sci. Comput. 33 (2011), no. 5, 2295\u20132317.","DOI":"10.1137\/090752286"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_024","doi-asserted-by":"crossref","unstructured":"C.-T.  Pan,\nOn the existence and computation of rank-revealing LU factorizations,\nLinear Algebra Appl. 316 (2000), no. 1\u20133, 199\u2013222.","DOI":"10.1016\/S0024-3795(00)00120-8"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_025","unstructured":"A.  Rotbart, G.  Shabat, Y.  Shmueli and A.  Averbuch,\nRandomized LU decomposition: An algorithm for dictionaries construction,\npreprint (2015), https:\/\/arxiv.org\/abs\/1502.04824."},{"key":"2023083109202714685_j_mcma-2023-2012_ref_026","doi-asserted-by":"crossref","unstructured":"K. K.  Sabelfeld and N. S.  Mozartova,\nSparsified randomization algorithms for low rank approximations and applications to integral equations and inhomogeneous random field simulation,\nMath. Comput. Simulation 82 (2011), no. 2, 295\u2013317.","DOI":"10.1016\/j.matcom.2011.08.002"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_027","unstructured":"G.  Shabat,\nRandomized LU matrix factorization code."},{"key":"2023083109202714685_j_mcma-2023-2012_ref_028","doi-asserted-by":"crossref","unstructured":"G.  Shabat, Y.  Shmueli, Y.  Aizenbud and A.  Averbuch,\nRandomized LU decomposition,\nAppl. Comput. Harmon. Anal. 44 (2018), no. 2, 246\u2013272.","DOI":"10.1016\/j.acha.2016.04.006"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_029","doi-asserted-by":"crossref","unstructured":"G. W.  Stewart,\nUpdating a rank-revealing ULV decomposition,\nSIAM J. Matrix Anal. Appl. 14 (1993), no. 2, 494\u2013499.","DOI":"10.1137\/0614034"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_030","doi-asserted-by":"crossref","unstructured":"G. W.  Stewart,\nThe QLP approximation to the singular value decomposition,\nSIAM J. Sci. Comput. 20 (1999), no. 4, 1336\u20131348.","DOI":"10.1137\/S1064827597319519"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_031","doi-asserted-by":"crossref","unstructured":"J. A.  Tropp, A.  Yurtsever, M.  Udell and V.  Cevher,\nPractical sketching algorithms for low-rank matrix approximation,\nSIAM J. Matrix Anal. Appl. 38 (2017), no. 4, 1454\u20131485.","DOI":"10.1137\/17M1111590"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_032","doi-asserted-by":"crossref","unstructured":"L. R.  Tucker,\nImplications of factor analysis of three-way matrices for measurement of change,\nProbl. Meas. Change 15 (1963), 122\u2013137.","DOI":"10.1108\/09534810210423008"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_033","unstructured":"L. R.  Tucker,\nThe extension of factor analysis to three-dimensional matrices,\nContrib. Math. Psychol. (1964), Article ID 110119."},{"key":"2023083109202714685_j_mcma-2023-2012_ref_034","doi-asserted-by":"crossref","unstructured":"L. R.  Tucker,\nSome mathematical notes on three-mode factor analysis,\nPsychometrika 31 (1966), 279\u2013311.","DOI":"10.1007\/BF02289464"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_035","doi-asserted-by":"crossref","unstructured":"M.  Udell and A.  Townsend,\nWhy are big data matrices approximately low rank?,\nSIAM J. Math. Data Sci. 1 (2019), no. 1, 144\u2013160.","DOI":"10.1137\/18M1183480"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_036","unstructured":"S.  Voronin and P.-G.  Martinsson,\nRSVDPACK: An implementation of randomized algorithms for computing the singular value, interpolative, and cur decompositions of matrices on multi-core and gpu architectures,\npreprint (2015), https:\/\/arxiv.org\/abs\/1502.05366."},{"key":"2023083109202714685_j_mcma-2023-2012_ref_037","doi-asserted-by":"crossref","unstructured":"W.  Yu, Y.  Gu, J.  Li, S.  Liu and Y.  Li,\nSingle-pass PCA of large high-dimensional data,\npreprint (2017), https:\/\/arxiv.org\/abs\/1704.07669.","DOI":"10.24963\/ijcai.2017\/468"},{"key":"2023083109202714685_j_mcma-2023-2012_ref_038","doi-asserted-by":"crossref","unstructured":"W.  Yu, Y.  Gu and Y.  Li,\nEfficient randomized algorithms for the fixed-precision low-rank matrix approximation,\nSIAM J. Matrix Anal. Appl. 39 (2018), no. 3, 1339\u20131359.","DOI":"10.1137\/17M1141977"}],"container-title":["Monte Carlo Methods and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/mcma-2023-2012\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/mcma-2023-2012\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,31]],"date-time":"2023-08-31T09:40:30Z","timestamp":1693474830000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/mcma-2023-2012\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,22]]},"references-count":38,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2023,7,4]]},"published-print":{"date-parts":[[2023,9,1]]}},"alternative-id":["10.1515\/mcma-2023-2012"],"URL":"https:\/\/doi.org\/10.1515\/mcma-2023-2012","relation":{},"ISSN":["0929-9629","1569-3961"],"issn-type":[{"value":"0929-9629","type":"print"},{"value":"1569-3961","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,22]]}}}