Single-pass randomized QLP decomposition for low-rank approximation

As a special UTV decomposition, the QLP decomposition is an effective alternative of the singular value decomposition (SVD) for the low-rank approximation. In this paper, we propose a single-pass randomized QLP decomposition algorithm for computing a low-rank matrix approximation. Compared with the...

Full description

Saved in:
Bibliographic Details
Published in:Calcolo 2022-11, Vol.59 (4), Article 49
Main Authors: Ren, Huan, Xiao, Guiyun, Bai, Zheng-Jian
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Error analysis
Mathematical analysis
Mathematics
Mathematics and Statistics
Numerical Analysis
Singular value decomposition
Theory of Computation
Tracking
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c319t-9fb75fd0808381b1ab34bfda1ec56637764910b4801eaca52500251be8326f3a3
cites cdi_FETCH-LOGICAL-c319t-9fb75fd0808381b1ab34bfda1ec56637764910b4801eaca52500251be8326f3a3
container_end_page
container_issue 4
container_start_page
container_title Calcolo
container_volume 59
creator Ren, Huan
Xiao, Guiyun
Bai, Zheng-Jian
description As a special UTV decomposition, the QLP decomposition is an effective alternative of the singular value decomposition (SVD) for the low-rank approximation. In this paper, we propose a single-pass randomized QLP decomposition algorithm for computing a low-rank matrix approximation. Compared with the randomized QLP decomposition, the complexity of the proposed algorithm does not increase significantly and the data matrix needs to be accessed only once. Therefore, our algorithm is suitable for a large matrix stored outside of memory or generated by streaming data. In the error analysis, we give the matrix approximation error analysis. We also provide singular value approximation error bounds, which can track the target largest singular values of the data matrix with high probability. Numerical experiments are also reported to verify our results.
doi_str_mv 10.1007/s10092-022-00491-4
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2736742866</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2736742866</sourcerecordid><originalsourceid>FETCH-LOGICAL-c319t-9fb75fd0808381b1ab34bfda1ec56637764910b4801eaca52500251be8326f3a3</originalsourceid><addsrcrecordid>eNp9UEtLxDAQDqLgWv0Dngqeo5N3epTFFyyoqOeQtsnSdbepSRcfv96sFbx5mBmG-R7Dh9ApgXMCoC5S7hXFQHMBrwjme2hGCJVYcMb30QwANAZJ-SE6SmmVV8E1n6H5U9cv1w4PNqUy2r4Nm-7LteXj4qFsXRM2Q0jd2IW-9CGW6_COM-i1tMMQw0e3sbvTMTrwdp3cye8s0Mv11fP8Fi_ub-7mlwvcMFKNuPK1Er4FDZppUhNbM1771hLXCCmZUjI_DjXXQJxtrKACgApSO82o9MyyAp1Nutn7bevSaFZhG_tsaahiUnGqs06B6IRqYkgpOm-GmB-Nn4aA2YVlprBMDsv8hGV4JrGJlDK4X7r4J_0P6xtLVWvd</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2736742866</pqid></control><display><type>article</type><title>Single-pass randomized QLP decomposition for low-rank approximation</title><source>Springer Nature</source><creator>Ren, Huan ; Xiao, Guiyun ; Bai, Zheng-Jian</creator><creatorcontrib>Ren, Huan ; Xiao, Guiyun ; Bai, Zheng-Jian</creatorcontrib><description>As a special UTV decomposition, the QLP decomposition is an effective alternative of the singular value decomposition (SVD) for the low-rank approximation. In this paper, we propose a single-pass randomized QLP decomposition algorithm for computing a low-rank matrix approximation. Compared with the randomized QLP decomposition, the complexity of the proposed algorithm does not increase significantly and the data matrix needs to be accessed only once. Therefore, our algorithm is suitable for a large matrix stored outside of memory or generated by streaming data. In the error analysis, we give the matrix approximation error analysis. We also provide singular value approximation error bounds, which can track the target largest singular values of the data matrix with high probability. Numerical experiments are also reported to verify our results.</description><identifier>ISSN: 0008-0624</identifier><identifier>EISSN: 1126-5434</identifier><identifier>DOI: 10.1007/s10092-022-00491-4</identifier><language>eng</language><publisher>Cham: Springer International Publishing</publisher><subject>Algorithms ; Approximation ; Error analysis ; Mathematical analysis ; Mathematics ; Mathematics and Statistics ; Numerical Analysis ; Singular value decomposition ; Theory of Computation ; Tracking</subject><ispartof>Calcolo, 2022-11, Vol.59 (4), Article 49</ispartof><rights>The Author(s) under exclusive licence to Istituto di Informatica e Telematica (IIT) 2022. Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c319t-9fb75fd0808381b1ab34bfda1ec56637764910b4801eaca52500251be8326f3a3</citedby><cites>FETCH-LOGICAL-c319t-9fb75fd0808381b1ab34bfda1ec56637764910b4801eaca52500251be8326f3a3</cites><orcidid>0000-0002-5134-3500</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,776,780,27901,27902</link.rule.ids></links><search><creatorcontrib>Ren, Huan</creatorcontrib><creatorcontrib>Xiao, Guiyun</creatorcontrib><creatorcontrib>Bai, Zheng-Jian</creatorcontrib><title>Single-pass randomized QLP decomposition for low-rank approximation</title><title>Calcolo</title><addtitle>Calcolo</addtitle><description>As a special UTV decomposition, the QLP decomposition is an effective alternative of the singular value decomposition (SVD) for the low-rank approximation. In this paper, we propose a single-pass randomized QLP decomposition algorithm for computing a low-rank matrix approximation. Compared with the randomized QLP decomposition, the complexity of the proposed algorithm does not increase significantly and the data matrix needs to be accessed only once. Therefore, our algorithm is suitable for a large matrix stored outside of memory or generated by streaming data. In the error analysis, we give the matrix approximation error analysis. We also provide singular value approximation error bounds, which can track the target largest singular values of the data matrix with high probability. Numerical experiments are also reported to verify our results.</description><subject>Algorithms</subject><subject>Approximation</subject><subject>Error analysis</subject><subject>Mathematical analysis</subject><subject>Mathematics</subject><subject>Mathematics and Statistics</subject><subject>Numerical Analysis</subject><subject>Singular value decomposition</subject><subject>Theory of Computation</subject><subject>Tracking</subject><issn>0008-0624</issn><issn>1126-5434</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2022</creationdate><recordtype>article</recordtype><recordid>eNp9UEtLxDAQDqLgWv0Dngqeo5N3epTFFyyoqOeQtsnSdbepSRcfv96sFbx5mBmG-R7Dh9ApgXMCoC5S7hXFQHMBrwjme2hGCJVYcMb30QwANAZJ-SE6SmmVV8E1n6H5U9cv1w4PNqUy2r4Nm-7LteXj4qFsXRM2Q0jd2IW-9CGW6_COM-i1tMMQw0e3sbvTMTrwdp3cye8s0Mv11fP8Fi_ub-7mlwvcMFKNuPK1Er4FDZppUhNbM1771hLXCCmZUjI_DjXXQJxtrKACgApSO82o9MyyAp1Nutn7bevSaFZhG_tsaahiUnGqs06B6IRqYkgpOm-GmB-Nn4aA2YVlprBMDsv8hGV4JrGJlDK4X7r4J_0P6xtLVWvd</recordid><startdate>20221101</startdate><enddate>20221101</enddate><creator>Ren, Huan</creator><creator>Xiao, Guiyun</creator><creator>Bai, Zheng-Jian</creator><general>Springer International Publishing</general><general>Springer Nature B.V</general><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>7TB</scope><scope>8FD</scope><scope>FR3</scope><scope>JQ2</scope><scope>KR7</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><orcidid>https://orcid.org/0000-0002-5134-3500</orcidid></search><sort><creationdate>20221101</creationdate><title>Single-pass randomized QLP decomposition for low-rank approximation</title><author>Ren, Huan ; Xiao, Guiyun ; Bai, Zheng-Jian</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c319t-9fb75fd0808381b1ab34bfda1ec56637764910b4801eaca52500251be8326f3a3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2022</creationdate><topic>Algorithms</topic><topic>Approximation</topic><topic>Error analysis</topic><topic>Mathematical analysis</topic><topic>Mathematics</topic><topic>Mathematics and Statistics</topic><topic>Numerical Analysis</topic><topic>Singular value decomposition</topic><topic>Theory of Computation</topic><topic>Tracking</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Ren, Huan</creatorcontrib><creatorcontrib>Xiao, Guiyun</creatorcontrib><creatorcontrib>Bai, Zheng-Jian</creatorcontrib><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Mechanical &amp; Transportation Engineering Abstracts</collection><collection>Technology Research Database</collection><collection>Engineering Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Civil Engineering Abstracts</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Calcolo</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Ren, Huan</au><au>Xiao, Guiyun</au><au>Bai, Zheng-Jian</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Single-pass randomized QLP decomposition for low-rank approximation</atitle><jtitle>Calcolo</jtitle><stitle>Calcolo</stitle><date>2022-11-01</date><risdate>2022</risdate><volume>59</volume><issue>4</issue><artnum>49</artnum><issn>0008-0624</issn><eissn>1126-5434</eissn><abstract>As a special UTV decomposition, the QLP decomposition is an effective alternative of the singular value decomposition (SVD) for the low-rank approximation. In this paper, we propose a single-pass randomized QLP decomposition algorithm for computing a low-rank matrix approximation. Compared with the randomized QLP decomposition, the complexity of the proposed algorithm does not increase significantly and the data matrix needs to be accessed only once. Therefore, our algorithm is suitable for a large matrix stored outside of memory or generated by streaming data. In the error analysis, we give the matrix approximation error analysis. We also provide singular value approximation error bounds, which can track the target largest singular values of the data matrix with high probability. Numerical experiments are also reported to verify our results.</abstract><cop>Cham</cop><pub>Springer International Publishing</pub><doi>10.1007/s10092-022-00491-4</doi><orcidid>https://orcid.org/0000-0002-5134-3500</orcidid></addata></record>
fulltext fulltext
identifier ISSN: 0008-0624
ispartof Calcolo, 2022-11, Vol.59 (4), Article 49
issn 0008-0624
1126-5434
language eng
recordid cdi_proquest_journals_2736742866
source Springer Nature
subjects Algorithms
Approximation
Error analysis
Mathematical analysis
Mathematics
Mathematics and Statistics
Numerical Analysis
Singular value decomposition
Theory of Computation
Tracking
title Single-pass randomized QLP decomposition for low-rank approximation
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-02-05T23%3A26%3A35IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Single-pass%20randomized%20QLP%20decomposition%20for%20low-rank%20approximation&rft.jtitle=Calcolo&rft.au=Ren,%20Huan&rft.date=2022-11-01&rft.volume=59&rft.issue=4&rft.artnum=49&rft.issn=0008-0624&rft.eissn=1126-5434&rft_id=info:doi/10.1007/s10092-022-00491-4&rft_dat=%3Cproquest_cross%3E2736742866%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c319t-9fb75fd0808381b1ab34bfda1ec56637764910b4801eaca52500251be8326f3a3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2736742866&rft_id=info:pmid/&rfr_iscdi=true