{"entities":{"Q952399":{"pageid":954247,"ns":120,"title":"Item:Q952399","lastrevid":50491709,"modified":"2026-01-14T04:54:14Z","type":"item","id":"Q952399","labels":{"en":{"language":"en","value":"A fast randomized algorithm for the approximation of matrices"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5365054"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952399$20B449EB-4EC8-4D80-B954-6C14B3BAABBB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"06f5e1b264d8941165854d157177c3beabeeaedb","datavalue":{"value":{"text":"A fast randomized algorithm for the approximation of matrices","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q952399$9B173B60-118B-47CD-9B35-26CF3FD24508","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ce42cb57f20713b7a712469dd0725a57df96f815","datavalue":{"value":"1155.65035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q952399$EB683C8C-F62D-4ECA-AD75-B426EF24F1D9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"de3012cde3ae0a612365f1b4c63f696f3f2722c7","datavalue":{"value":{"entity-type":"item","numeric-id":952398,"id":"Q952398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952399$6F78DED6-771E-4721-ADE1-4B9C3B1A7815","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ef97ae6a54a043526f33dd01d27b480872fb6a6c","datavalue":{"value":{"entity-type":"item","numeric-id":629830,"id":"Q629830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952399$303C6125-577B-401D-A339-7C6056417FAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"82a8e64b54c76f1cbfe977f0f871351caf853242","datavalue":{"value":{"entity-type":"item","numeric-id":262080,"id":"Q262080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952399$517E0A5C-68F5-4569-A11D-62D58660FDC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"78cbf5547a50756d2cc183c570e7f4c5cb21085b","datavalue":{"value":{"entity-type":"item","numeric-id":347529,"id":"Q347529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952399$ED756580-B2CC-47FF-8641-A21263E0D92F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e219ca58c5478bf431640db74af74d5c15bdb120","datavalue":{"value":{"entity-type":"item","numeric-id":107999,"id":"Q107999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952399$D649C395-5CCE-4A88-AE47-3DDEA0346A7A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9c0c5d55f421b4befea01725a45f89d7530e49d2","datavalue":{"value":{"time":"+2008-11-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q952399$9206A93B-5EBE-419C-8F11-D5DABFBC627D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"82ed64d28e88b31e38afe330a7dee3d689a146eb","datavalue":{"value":"The authors propose a randomized procedure that, given an \\(m \\times n\\) matrix \\(A\\) and a positive integer \\(k\\), approximates \\(A\\) with a matrix \\(Z\\) of rank \\(k\\). The algorithm relies on applying a structured \\(l \\times m\\) random matrix \\(R\\) to each column of \\(A\\), where \\(l\\) is an integer near to, but greater than \\(k\\). The structure of \\(R\\) allows us to apply it to arbitrary \\(m \\times l\\) vector at a cost proportional to \\(m \\log(l)\\); the resulting procedure can construct a rank -\\(k\\) approximation \\(Z\\) from the entries of \\(A\\) at a cost proportional to \\(mn \\log(k)+l^2(m+n)\\).   The authors prove several bounds on the accuracy of the algorithm. The proposed algorithm operates reliably independently of the structure of the matrix \\(A\\), can access each column of \\(A\\) independently and at most twice, and parallelizes naturally. Numerical examples are also provided.","type":"string"},"datatype":"string"},"type":"statement","id":"Q952399$68D01E8B-4362-40E0-9CCC-42E916B6C712","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8f9e4f5ee2ff4efa1345e650ad5729a2a6fa6cff","datavalue":{"value":{"entity-type":"item","numeric-id":589121,"id":"Q589121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952399$FC7E5A0B-737B-42B1-81A6-D6D7C19AA8C4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"72309745094959b676ca20810c7af21a33fe24b5","datavalue":{"value":"65F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q952399$E39EF84A-0C37-4640-BE9E-20FAA237C7FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"70859ede1ca06ac7d3be51584cbccead36f691b1","datavalue":{"value":"15B52","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q952399$F52A0F96-380E-4733-B5DE-CC492BEB7906","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"830ff2f0cf366a27db413522731e7545bf1905a3","datavalue":{"value":"5365054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q952399$FC398904-EA4F-4FD5-AF1E-DBF2F2956055","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e37654a903467a5e6bbeca3c0e4f78cfb92c4a18","datavalue":{"value":"Lanczos method","type":"string"},"datatype":"string"},"type":"statement","id":"Q952399$26ED5018-6EE2-4BAD-8E89-E6A908E7309B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"538b484a5a128b52124c03373521df8950795cd5","datavalue":{"value":"singular value decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q952399$809F6A57-3224-4C56-B5FA-2A3559908482","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"974297935e1c2d56401cc217d1529a09d320546a","datavalue":{"value":"QR factorization","type":"string"},"datatype":"string"},"type":"statement","id":"Q952399$A32273A2-4942-4638-B98D-FB41CFB66458","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"29ef22b3af0ff2b7639eb6eeb493357093087744","datavalue":{"value":"random matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q952399$B5897709-7C66-4B78-9C45-75349061C7F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d74cb5419439f42eb1ba8891c8722bd3702922d","datavalue":{"value":"numerical examples","type":"string"},"datatype":"string"},"type":"statement","id":"Q952399$E46C88FD-0738-4025-90D0-9EAB399899A1","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"6a1136ea541d14ad531b9bbbe1ef89ed6387b512","datavalue":{"value":{"entity-type":"item","numeric-id":16583,"id":"Q16583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952399$E6222D9B-35FC-4B02-A74F-C875D495DF08","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952399$3EEFB366-261F-4A1C-A357-D85F933899B2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"22d74317c6015c3d75b0be56070a87dca40bb27e","datavalue":{"value":"https://doi.org/10.1016/j.acha.2007.12.002","type":"string"},"datatype":"url"},"type":"statement","id":"Q952399$8AA5A563-DC9E-49F0-95E2-B5661A4E12BB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f49663141f8808cd6abe48438ac49efab803cb1e","datavalue":{"value":"W4213311204","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q952399$7E55EC56-6DDA-4AA9-AFCB-28D4E2DF731D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d0c21070f96e72815914c0c6ee2d64c28ebf566","datavalue":{"value":{"entity-type":"item","numeric-id":2931418,"id":"Q2931418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952399$E169A639-6628-43F7-978F-923DBBDE36EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd1f93c8560445d7e9909d98a79bd784af26a4f7","datavalue":{"value":{"entity-type":"item","numeric-id":3579390,"id":"Q3579390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952399$C039F8CB-242F-44EF-826A-C786B20280F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"22c2949e0d8c8c9b439d6f0348f847eaaa96bca0","datavalue":{"value":{"entity-type":"item","numeric-id":5248550,"id":"Q5248550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952399$77E826A9-5950-40E9-B737-9FFF7F66F9CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1fd7a613bd01b81aa1a62803f3283dc3b00ac8ec","datavalue":{"value":{"entity-type":"item","numeric-id":3992218,"id":"Q3992218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952399$CF4766EA-D7E3-4E6C-B899-4D786D520114","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de8fc3a1856e81eb0982bf913be56fc8912d41fc","datavalue":{"value":{"entity-type":"item","numeric-id":5318307,"id":"Q5318307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952399$D68FA73E-F1E4-430D-A62C-34B3D11A69D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d265fbff8b64abcf0b5d33afc6285bbd82d8752","datavalue":{"value":{"entity-type":"item","numeric-id":3321334,"id":"Q3321334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952399$308FEF66-4C67-4F0B-889F-E718308382CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d52df2154bfdd0f3ced81e7603ae5503222445b","datavalue":{"value":{"entity-type":"item","numeric-id":5689624,"id":"Q5689624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952399$24E4EB59-EEFE-4544-BA3A-9374A4295313","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"931d00e2419fc3bfef9b1873594ced701c426add","datavalue":{"value":{"entity-type":"item","numeric-id":2784645,"id":"Q2784645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952399$1FA9FC2B-0EA8-4B58-B92B-37DAE88F2D77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e569de28b5b7a6d05835353d344a9b06a92f06a","datavalue":{"value":{"entity-type":"item","numeric-id":4891737,"id":"Q4891737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952399$BE01170C-1BBD-4A70-9FA4-B71A12F87485","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cba950e6f363e5a3ef0316ac1fe0b448e1cee46","datavalue":{"value":{"entity-type":"item","numeric-id":4021609,"id":"Q4021609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952399$0CDB8083-8A9E-4A73-9228-7E5742CA09EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6689b1688263321e8ad6e221d6c1210c794334b","datavalue":{"value":{"entity-type":"item","numeric-id":2757502,"id":"Q2757502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952399$B7DEE608-8228-47BE-9F5D-27D878E5EDFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29d9ee6afbc084e14a614388992e2b800dfd4a17","datavalue":{"value":{"entity-type":"item","numeric-id":855026,"id":"Q855026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952399$72053CDD-8323-4630-A3B8-F4D3B5A8FC4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f27adbaaa6e0b39e4d1a3fd6c804f5476675c520","datavalue":{"value":{"entity-type":"item","numeric-id":815265,"id":"Q815265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952399$83825F89-935E-4FA3-ADAF-A6CFA46C2A09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"378789ac6498a71146d3120c01e7fdac1f07d01d","datavalue":{"value":{"entity-type":"item","numeric-id":5289008,"id":"Q5289008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952399$6FAA984A-5716-4987-BF4C-27A4EB709D4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7897db40c373b264324508a4fe3dd241843cd753","datavalue":{"value":{"entity-type":"item","numeric-id":4038986,"id":"Q4038986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952399$8C5C974D-2AF8-443F-8BB6-78120B382329","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54c60f465420f690aac089c6005bd35bb3a46a88","datavalue":{"value":{"entity-type":"item","numeric-id":1581115,"id":"Q1581115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952399$3192702C-A30C-4D6F-BD2D-332A5648C4EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65ee3ec3da42b0348ff596776ea8a65a07a9e190","datavalue":{"value":{"entity-type":"item","numeric-id":952399,"id":"Q952399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q952399$21240D10-712F-4552-97C1-1E72ADE3AFA1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cc51c8808148fa07f070ea72cbe886c905921010","datavalue":{"value":"10.1016/J.ACHA.2007.12.002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q952399$7D4D0E88-7AA8-402E-9300-DCAE5DED429F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25132c2ea47195124f2f42a0d324c767dc04d2be","datavalue":{"value":{"entity-type":"item","numeric-id":617703,"id":"Q617703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea8291428d588a2f995375639b0064ded4b19f37","datavalue":{"value":{"amount":"+0.9482985734939576","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q952399$76B60FD5-03C7-4AD9-BCBA-28F4F2703C56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46d30487bf03b57c2f3c5a28e95123899a05c409","datavalue":{"value":{"entity-type":"item","numeric-id":3165168,"id":"Q3165168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1e89636c968351c8b0e4d279344ed455acb36cd","datavalue":{"value":{"amount":"+0.921424686908722","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q952399$A2D43BEA-5ADB-4315-9191-6BAF2CA93F43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"885ce53ef0659ef88aec1ac9315db642ad2d454f","datavalue":{"value":{"entity-type":"item","numeric-id":5470750,"id":"Q5470750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d6e536df8b1ad62425e88d344237e29907e8a98","datavalue":{"value":{"amount":"+0.9081149697303772","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q952399$525921B4-FC2F-4DF6-BFBF-74326997D7A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"758c0cda448661b4c3bd89683238e1a1e008118a","datavalue":{"value":{"entity-type":"item","numeric-id":5435673,"id":"Q5435673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"522ea6a3170c405e562f4858479e11d5532c51bd","datavalue":{"value":{"amount":"+0.9021379351615906","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q952399$3B3EFAD3-9EB1-4B5E-8D4F-84EB21B28384","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"957a32d3ca42c0e7c79f17ce234baa23cb10b3be","datavalue":{"value":{"entity-type":"item","numeric-id":3010073,"id":"Q3010073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9919f53db0a31cb04e92257df122de174e934091","datavalue":{"value":{"amount":"+0.896558940410614","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q952399$40C33480-EC10-4744-85FD-ABB7E95C8CA9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:952399","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:952399"}}}}}