{"entities":{"Q617703":{"pageid":619479,"ns":120,"title":"Item:Q617703","lastrevid":51162413,"modified":"2026-01-17T00:34:01Z","type":"item","id":"Q617703","labels":{"en":{"language":"en","value":"A randomized algorithm for the decomposition of matrices"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5835730"}},"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":"Q617703$1D552D91-B283-45DE-9D45-71789EB1560F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"38943d41f06844bb12dbee646cae682a77b60bdd","datavalue":{"value":{"text":"A randomized algorithm for the decomposition of matrices","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q617703$FD231EFC-20B8-4671-9EA1-33B6748F34C1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"743f0ff7d046906a08d157ef37deb4dea5c76fe3","datavalue":{"value":"1210.65095","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q617703$B5E348AE-7580-4A01-AE08-76C5AA8B3532","rank":"normal"}],"P16":[{"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":"Q617703$9FCD9F80-2625-41A5-8651-847BB114A580","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":"Q617703$A8415A9B-C685-4C40-A603-7D1E4E8B27B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"328096366503e0dc10951a0082e3123d680b6d04","datavalue":{"value":{"entity-type":"item","numeric-id":693188,"id":"Q693188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q617703$1F411392-6BEA-4849-B8F8-1F936BA3C955","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":"Q617703$9005B9F9-2A93-40D1-9085-38333DF7540F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a97c1d6fc2599d06259094f1abb3cc946622f97a","datavalue":{"value":{"time":"+2011-01-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q617703$BFB694DF-3BCE-43A9-8131-DF5CA8C8C74F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"07673736a6467aedee1a70ce16d85b870d1caac6","datavalue":{"value":"Given a large real matrix \\(A\\in{\\mathbb R}^{m\\times n}\\), the idea is to approximate it with a rank-\\(k\\) matrix that is as close as possible in the spectral norm. The authors analyse a method that starts from a random matrix \\(G\\in{\\mathbb R}^{l\\times m}\\), \\(k<l<\\min(m,n)\\) with entries that are \\(N(0,1)\\) Gaussian distributed. By constructing a particular rank-\\(k\\) approximation to \\(GA\\), it is possible to select \\(k\\) columns from \\(A\\) that are stored in a matrix \\(B\\).  From these computations it is also possible to construct a matrix \\(P\\in{\\mathbb R}^{k\\times n}\\). Together they lead to a rank-\\(k\\) matrix \\(Z=BP\\) that approximates \\(A\\). Usually \\(l\\) is moderately larger than \\(k\\). For example if \\(l=k+20\\) then \\(\\|A-Z\\|\\leq 10\\sqrt{k(k+20)nm}\\;\\sigma_{k+1}\\), with probability at least \\(1-10^{-17}\\). Here \\(\\sigma_{k+1}\\) is the \\((k+1)\\)st singular value of \\(A\\). This \\(\\sigma_{k+1}\\) is the error for the classical optimal rank-\\(k\\) approximation obtained by keeping only the \\(k\\) largest singular values in the the SVD of \\(A\\). Not only the rank-\\(k\\) approximant for \\(A\\) is computable using simple matrix-vector multiplications with \\(A\\) and \\(A^T\\), also the approximating singular value decomposition (SVD) can be obtained. The computational complexity is in general comparable to a Lanczos procedure.","type":"string"},"datatype":"string"},"type":"statement","id":"Q617703$A18DD925-AD65-48F2-8658-CC06076DEC8A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"fc8a96e7da0a25d97c6c3415d8dffbc5c07a46e1","datavalue":{"value":{"entity-type":"item","numeric-id":283199,"id":"Q283199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q617703$DD53D478-8D57-4D88-8BDD-A6E8FA456B8D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"72309745094959b676ca20810c7af21a33fe24b5","datavalue":{"value":"65F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q617703$4B522AF0-7B84-45D6-AA3F-967E85CFC4F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"717e5d30d5ff12a8eec4b001d2230e0fa8c12f49","datavalue":{"value":"65F20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q617703$7F5ACE33-6E60-47B0-9BD8-8537CDC58A67","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"81ba3b9ff4618b7628a5c7490956ed2ef8940171","datavalue":{"value":"5835730","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q617703$2A18EE38-3EF2-4091-84A6-0AA824873B81","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f2832e5ae4fc414c772c86f6023e26d563dd35e6","datavalue":{"value":"randomized algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q617703$ADA0D040-3678-4CF4-A044-2530B8C68650","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6d95e47c4a5cd8f0ec75e8af38639bd94543e58b","datavalue":{"value":"Lanczos algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q617703$5D639D19-C6F2-44C2-8D73-EA061780A4EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"538b484a5a128b52124c03373521df8950795cd5","datavalue":{"value":"singular value decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q617703$E38A4DFC-8643-4C26-B401-720897B69E4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"660970007a697d773cb5cbcfcb5a1913898a9304","datavalue":{"value":"low rank approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q617703$40E71ACE-8A0B-4A44-9CDD-5511F5B54107","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":"Q617703$BB480313-BAB7-4B80-B505-8BA5496A07C7","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":"Q617703$13211B8D-72BA-4204-9C2A-AD1F180C0BEA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1100d44e6ffff25cfc3ac5d8d0c7fa85f0c94199","datavalue":{"value":"https://doi.org/10.1016/j.acha.2010.02.003","type":"string"},"datatype":"url"},"type":"statement","id":"Q617703$132926D9-79D1-4F1F-88B9-A91EA8B23B82","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cde820b95666cd07dd33f3a3e636e5ea4bac1736","datavalue":{"value":"W2057261601","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q617703$EA0C16DB-8410-458A-8B66-9DF6A4351E5C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"13fa0eb7200d679132c1e6056bfea60870eb2c51","datavalue":{"value":{"entity-type":"item","numeric-id":5461232,"id":"Q5461232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q617703$E0D92CEB-5B60-43BA-8171-A73F86877B18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cd20149f34707bcd403622a437851ec43100442","datavalue":{"value":{"entity-type":"item","numeric-id":1319993,"id":"Q1319993"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q617703$EB0AF135-AB8F-423D-A7C7-E6D57DBF9489","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":"Q617703$A92A9DFE-4341-4F52-907F-94CFD18B0432","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96705c7a888a0c8d518c05c0da5f39cc1ebd1812","datavalue":{"value":{"entity-type":"item","numeric-id":5470480,"id":"Q5470480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q617703$10C2540E-E9D1-450A-9A15-0903652EEE71","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":"Q617703$C0CAD83C-2CA5-45EF-B55C-15381C0B596B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b6fb5a316965b5102df31288b20f9d9d3784966","datavalue":{"value":{"entity-type":"item","numeric-id":5805296,"id":"Q5805296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q617703$1A6F351C-46F0-40B6-B5FD-23C3E074A31C","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":"Q617703$66DCCF0C-7164-4574-8B73-13342CA807C4","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":"Q617703$B0B35735-3C0E-4C49-AAB7-03F4E17E336A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a74498ae0db1086a81a5bafdbe3c5f1eb04fcf0","datavalue":{"value":{"entity-type":"item","numeric-id":1277563,"id":"Q1277563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q617703$E2DF05A7-2F06-4E8A-B1AA-29818A69E78D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea0f0af3954b0011bc07dbcdfa869b11b709966e","datavalue":{"value":{"entity-type":"item","numeric-id":1362649,"id":"Q1362649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q617703$98BDA183-8A84-4CD9-9D49-4172B6CAD955","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":"Q617703$5D3AE60D-CAA2-4C47-B046-A92BDBD5ABC6","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":"Q617703$D046249E-4BC6-4056-9531-876D876DC471","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":"Q617703$DA5853B4-1C1A-4D75-899A-BC3FD53B568E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04c3f62fe703f33749ddd4570db526e38dccdd07","datavalue":{"value":{"entity-type":"item","numeric-id":1591153,"id":"Q1591153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q617703$5C5A15D3-6AF7-4DFD-8DF7-5D7667B2618B","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":"Q617703$D072FA91-216A-42F4-982E-316FD90219B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ac7ab30b4d06f17d96cca32ee01720d15b26b38","datavalue":{"value":{"entity-type":"item","numeric-id":1806006,"id":"Q1806006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q617703$DEAA231A-BA24-4847-A452-E32C5488EADC","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":"Q617703$4B59075B-C028-4584-A86A-E33EE25B417F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b4a3c5e894623ed6c86b2d00f23c20c5ccdee6c","datavalue":{"value":{"entity-type":"item","numeric-id":5674306,"id":"Q5674306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q617703$D3225DAD-BF43-4B44-8858-E1704B0FC744","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9e80a851225e3af5f977cdda1ee6572a387df532","datavalue":{"value":"10.1016/J.ACHA.2010.02.003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q617703$62EBD71D-8FE4-421E-BC46-1151C154C533","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2fd9e0b43fe0947273e97629e47e0c06e5e1990","datavalue":{"value":{"entity-type":"item","numeric-id":952399,"id":"Q952399"},"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":"Q617703$20DBC456-D658-48ED-9B7C-857831872CDA","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":"c35a01acf10280ec096cd7b666fdf0cf4731201e","datavalue":{"value":{"amount":"+0.8995007872581482","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":"Q617703$9884CE22-7E78-4328-9281-0F6B1C5DAA88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b27fe52c23c94cda1996c0d1a3f49e816db16c67","datavalue":{"value":{"entity-type":"item","numeric-id":4327492,"id":"Q4327492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"158088b2b7a01e49770e303ed7620796a2b0fe18","datavalue":{"value":{"amount":"+0.8927048444747925","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":"Q617703$159912F8-30C8-44C8-AC72-9E509A8F3A58","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":"4cb8da4ec2909aaa09eea6631a360243c5109a6b","datavalue":{"value":{"amount":"+0.8688991069793701","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":"Q617703$25A7ECD0-417A-4772-B9E9-0CA0B4C4993D","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":"a004bfa7636abde739fe157632b7caed4344903c","datavalue":{"value":{"amount":"+0.8672948479652405","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":"Q617703$53008468-B859-4894-87D1-4117D7434437","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:617703","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:617703"}}}}}