{"entities":{"Q639988":{"pageid":641836,"ns":120,"title":"Item:Q639988","lastrevid":57105531,"modified":"2026-03-26T15:56:02Z","type":"item","id":"Q639988","labels":{"en":{"language":"en","value":"Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5956860"}},"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":"Q639988$871D533D-36AE-466C-824D-480AFED1020B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1038784127c4d6f772e70fe11285cd3cbf576292","datavalue":{"value":{"text":"Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q639988$981184CF-1967-489B-AEAF-DAC5241D639B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3ebda32b7eb80b9eebc92117132401a8901b886e","datavalue":{"value":"1230.65051","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q639988$2AE96AB3-CF94-4759-8DEC-851CD1AFE9CA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bfa43a8cb17de146e15f27851a27a83c6c1a7aa9","datavalue":{"value":{"entity-type":"item","numeric-id":236217,"id":"Q236217"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q639988$25F83956-B466-449B-89A0-AC5692378495","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6988d972c3cb4976ac0f9a5554c271769f1685b2","datavalue":{"value":{"entity-type":"item","numeric-id":245507,"id":"Q245507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q639988$5F2271D9-30F1-40AD-A1E4-77CDCC48BE3C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"95f4a47752e6dde2f4d6f910dcba94ba8b5377c0","datavalue":{"value":{"entity-type":"item","numeric-id":57895,"id":"Q57895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q639988$6F7D7305-3574-42D8-B96B-8A3DCCEDDD2D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"38bd0b0b5d86722d0e22771ee04c5b1ab8a51fc8","datavalue":{"value":{"time":"+2011-10-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q639988$548EA8A0-7374-42D6-93D6-D2060B18EBEF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9d483e460a85ca0a2a66a54d2afecea880d9f646","datavalue":{"value":"https://arxiv.org/abs/1008.4397","type":"string"},"datatype":"url"},"type":"statement","id":"Q639988$5711F235-08E1-41DA-B846-E947BC88C5B6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8f613263cac5707d934dd2b84e91931b477633a7","datavalue":{"value":"To solve the system \\(Ax=b\\), \\(A\\in{\\mathbb R}^{m\\times n}\\), the Kaczmarz algorithm updates in iteration \\(k\\) the vector \\(x\\) by projecting it orthogonally onto the hyperplane \\(a_i^Tx=b_i\\) where \\(a_i\\) is the \\(i\\)th row of \\(A\\). Hereby \\(i\\) changes cyclically. In the randomized version, \\(i\\) is chosen with a probability proportional to the relative norm of \\(a_i\\) [see \\textit{T. Strohmer} and \\textit{R. Vershynin}, J. Fourier Anal. Appl. 15, No.~2, 262--278 (2009; Zbl 1169.68052)].  In this paper the same idea is generalized by projecting the rows of \\(A\\) onto a lower dimensional subspace (Johnson-Lindenstrauss technique), which makes it more efficient to compute the optimal choice of \\(i\\). It is proved that the convergence rate is expected to be at least as fast as the classical randomized Kaczmarz method and it is experimentally shown to be much faster in most cases [cf. \\textit{S. Kaczmarz}, Bull. Int. Acad. Polon. Sci. A 1937, 355--357 (1937; Zbl 0017.31703)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q639988$DAF047FF-CB72-47C9-8D0C-3FDC2F58D9B7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"717e5d30d5ff12a8eec4b001d2230e0fa8c12f49","datavalue":{"value":"65F20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q639988$C3A869D2-3843-4201-91FF-861D9021D59A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e402ef99c8e0f5ecec9caa212271be1d3e4c4885","datavalue":{"value":"92C55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q639988$8613FDE5-4675-4ED8-BBC4-AD5EB80A6155","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4db3fc3244f368e49336c7e23443d11b7d69297d","datavalue":{"value":"94A12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q639988$59F6BF85-EFFC-4611-80BB-5DAB11B77317","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"48cc35e0be48e288417deeb89c7d1178774ea340","datavalue":{"value":"5956860","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q639988$FBE60888-7BCF-4A92-B3F5-9CBEC4C79F16","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"058bc8902466f4b0149be0ca60d039c058cd1bea","datavalue":{"value":"Kaczmarz method","type":"string"},"datatype":"string"},"type":"statement","id":"Q639988$85CB6D30-C709-483C-B12D-85F4DC88C9DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8dfd6f27a85d60c19080a4c5d0fbe79d85e6b2ab","datavalue":{"value":"randomized Kaczmarz method","type":"string"},"datatype":"string"},"type":"statement","id":"Q639988$37576F07-92EF-4370-AD06-46836B47CA05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e4883427db8570c873e36c17dcffb3161b89d8b4","datavalue":{"value":"computer tomography","type":"string"},"datatype":"string"},"type":"statement","id":"Q639988$85B4E8D4-5909-4D00-9EB7-90C43741AB50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"25c524373260d818416d14fbb13c3012dee2a05c","datavalue":{"value":"signal processing","type":"string"},"datatype":"string"},"type":"statement","id":"Q639988$F57D06B9-C958-4740-9B2E-3F9FA1594E6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d74cb5419439f42eb1ba8891c8722bd3702922d","datavalue":{"value":"numerical examples","type":"string"},"datatype":"string"},"type":"statement","id":"Q639988$724B0FFF-03F8-4452-878E-46764D3856B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f864650165271b5ab17822fae4421faa85555999","datavalue":{"value":"Johnson-Lindenstrauss technique","type":"string"},"datatype":"string"},"type":"statement","id":"Q639988$50DC7172-9F6E-41DF-8657-A0C8E9E27CFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"03ee0109af41ad406ecd743518061baaa9e5e3ff","datavalue":{"value":"convergence","type":"string"},"datatype":"string"},"type":"statement","id":"Q639988$4C07BADA-C7E7-414A-A7BC-5C8E3517A386","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":"Q639988$B8195207-4271-4F1F-824C-52FB9D84BACF","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":"Q639988$6AC2DC3C-0F16-4C8C-A2E6-9BE19695E094","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"849775a35aef635369702d42b46b980162bafa0d","datavalue":{"value":"W2036835849","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q639988$713A918C-6982-42E0-8F16-C44833877EDD","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"b15f90a81cc00bfbf8e2b3ddfab31e27e9ba1675","datavalue":{"value":"Q124810364","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q639988$154194CD-742D-4129-89A7-ECD5A2719223","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"57c469a7191699954a4c1fd22c1c14115625a996","datavalue":{"value":{"entity-type":"item","numeric-id":1401965,"id":"Q1401965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q639988$394D8CD8-15D1-432C-95DC-FF71F327E78C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca7e46e522bcbc93875edd2e1eea1062dbc4d5d6","datavalue":{"value":{"entity-type":"item","numeric-id":5189547,"id":"Q5189547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q639988$CF019C50-2DA0-4CF3-A31C-C1EEFB517DB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1a3f6eab334d9b82136fbf9a09d65f4a64cf582","datavalue":{"value":{"entity-type":"item","numeric-id":2933651,"id":"Q2933651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q639988$EA3DDCD4-5DAF-4BC1-8154-A0CD6B70926C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"91f120f22705115354746e46474e788dca4308c5","datavalue":{"value":{"entity-type":"item","numeric-id":4376247,"id":"Q4376247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q639988$0E4CD0BE-7ABC-46FC-B425-8D2FE2852D5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ccdb560637e2917efe1cd845a3d404c8e17a7961","datavalue":{"value":{"entity-type":"item","numeric-id":4798181,"id":"Q4798181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q639988$6ACC8013-CD35-4511-80A3-04F9E0CC965F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb4a1e0082ead00e986597b5112c3843a36570d6","datavalue":{"value":{"entity-type":"item","numeric-id":1353696,"id":"Q1353696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q639988$98114B56-AC39-45DD-9F38-DB7068B56551","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b429d53b2cf03d42ae921e1040859f1a5ccb2c45","datavalue":{"value":{"entity-type":"item","numeric-id":3583428,"id":"Q3583428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q639988$768DC7EA-D853-4020-956A-F61E9E1C2743","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"222ea198d2872096a38c5fff058802947a1fc888","datavalue":{"value":{"entity-type":"item","numeric-id":3624872,"id":"Q3624872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q639988$9D52300F-F1E7-4832-A0B1-8E3FA83FC65A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45d3bda78f466ab35799a72c239c87690d4da7ee","datavalue":{"value":{"entity-type":"item","numeric-id":4313431,"id":"Q4313431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q639988$1A4132BC-198A-4705-90B1-A1C712CF350A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0a7ae52b82ec37e5b0cdcbf526672fdd5bce55e","datavalue":{"value":{"entity-type":"item","numeric-id":2566096,"id":"Q2566096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q639988$D080FC62-A3E4-4141-8B37-24D8A6C82DC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97568052a786838a1150815aed72c395050b728c","datavalue":{"value":{"entity-type":"item","numeric-id":920573,"id":"Q920573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q639988$01B9587D-E6AA-4936-81A2-0A87857603CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b48de4389c433c917c96bf3a15912792b6dfea67","datavalue":{"value":{"entity-type":"item","numeric-id":3094609,"id":"Q3094609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q639988$5AA82DAB-EDDF-45EF-AF11-7CFAD86259B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94fa1eac81fabb1dca93d77337bfd0199e598ffc","datavalue":{"value":{"entity-type":"item","numeric-id":4542583,"id":"Q4542583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q639988$A9EA2F26-80F1-4404-B753-69711B234357","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90b6fe1e6ca9f0f96e89b69032dd74b5fee6b7a3","datavalue":{"value":{"entity-type":"item","numeric-id":3326256,"id":"Q3326256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q639988$12D15C97-69AD-4059-9AE2-62B62EA9D3E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"804bd614555cab0fc8a6b3c24cb514f7623187ec","datavalue":{"value":{"entity-type":"item","numeric-id":3754464,"id":"Q3754464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q639988$3536664D-92C2-4659-AAA9-13E3FCB8A473","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4b12fdd72449649e5cad5f421bdd9fd7a7cfe9a","datavalue":{"value":{"entity-type":"item","numeric-id":981677,"id":"Q981677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q639988$ACF5D0DD-F377-440F-BEA1-541FD7D2CE36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59e48e50906ce92f7c92c452573c121d992e8378","datavalue":{"value":{"entity-type":"item","numeric-id":2706432,"id":"Q2706432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q639988$D2174CED-A6BC-47AF-B9F0-FB5BD5002C99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92ea536970f439fdb7b21c47123f07ac8d143447","datavalue":{"value":{"entity-type":"item","numeric-id":3595400,"id":"Q3595400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q639988$383EC6C8-B6B4-40A3-9C15-6347EC54F44F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1286a026708c92b4921e8cde2ae710ddcd60bd9e","datavalue":{"value":{"entity-type":"item","numeric-id":1027734,"id":"Q1027734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q639988$3D88FAD6-9757-4375-9CCC-2B94DDA4497E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"eade9c936f4a48e34839fff5dd0e444ad2636666","datavalue":{"value":"10.1007/S11075-011-9451-Z","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q639988$30851C9E-3566-435F-8FAB-476740326DF6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea6ae8b8d3da2d14fc567bbeebc5b561951fdcf6","datavalue":{"value":{"entity-type":"item","numeric-id":5266140,"id":"Q5266140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb7a85e6eaa49893c79c605d0a321c1fcd0842b7","datavalue":{"value":{"amount":"+0.8692559003829956","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":"Q639988$23ECF8DC-B2FD-479C-9727-60D94B419423","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b115a8e0dc5834da93da931eb623ba0219bce96","datavalue":{"value":{"entity-type":"item","numeric-id":3450034,"id":"Q3450034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a41f4e855959d1ce16462419ecb8f2dd36f1c4d","datavalue":{"value":{"amount":"+0.8547854423522949","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":"Q639988$964706FB-2A33-4847-B826-F2DD380BB92A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a4eff8c4b540173bc754d38de38c6c1ef839770","datavalue":{"value":{"entity-type":"item","numeric-id":4956926,"id":"Q4956926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0031a3cdd020653cb8833742cab0369ee0aed83a","datavalue":{"value":{"amount":"+0.8528956174850464","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":"Q639988$1BF76B31-6A0C-4347-9599-75474E8116C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc680172d459161addab9cb8278b1b83a1b97835","datavalue":{"value":{"entity-type":"item","numeric-id":1027734,"id":"Q1027734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3cb87c08e183c20be84cbb27ce6be32fcf10074d","datavalue":{"value":{"amount":"+0.844543993473053","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":"Q639988$D619A35B-1EFF-432C-B6C1-19296CB2AB7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96d42f8f185d6a877f4278b00552fc7c5496ffa8","datavalue":{"value":{"entity-type":"item","numeric-id":2848636,"id":"Q2848636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dcdfec3971e3117b9b55d3e7112c0c4f1f647249","datavalue":{"value":{"amount":"+0.8409504294395447","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":"Q639988$2989311F-3C55-4B60-A059-768416DAA164","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:639988","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:639988"}}}}}