{"entities":{"Q927127":{"pageid":928975,"ns":120,"title":"Item:Q927127","lastrevid":42772205,"modified":"2025-07-10T14:55:13Z","type":"item","id":"Q927127","labels":{"en":{"language":"en","value":"The restricted isometry property and its implications for compressed sensing"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5277937"}},"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":"Q927127$AE218575-9EE4-4A18-B651-5B2E858E346B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ed1783302be2f7701bce51af310df9cb520a3ed3","datavalue":{"value":{"text":"The restricted isometry property and its implications for compressed sensing","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q927127$7AE6950C-6D24-4113-9F7D-4DFAB711467F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"df4caa588b65c791f6197c020d3bd4cf6ea77e86","datavalue":{"value":"1153.94002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q927127$5243A409-449C-4594-AC61-5394ACABCCCC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"08cd841cce9cb3a7d68785b6713670d79c9e3357","datavalue":{"value":{"entity-type":"item","numeric-id":237290,"id":"Q237290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q927127$CB7FB9BC-DC30-4D83-94EE-9DF877421D40","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"5a5c9e0c6a7a2a0cb7662cbf32d2a100f29f5641","datavalue":{"value":{"entity-type":"item","numeric-id":251665,"id":"Q251665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q927127$D65D49D9-AD69-41D6-B8BE-44C319A7E6F2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"767dc2dde9b80501254370ea98716c04e9449c65","datavalue":{"value":{"time":"+2008-05-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q927127$DD236BC8-52A3-45E3-ACD4-936581C94C50","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"86d9b4b26f693834facf5734f0cb1bd8523e8ef7","datavalue":{"value":"Conditions on a \\textit{sensing matrix} \\(\\Phi\\) are given such that the solution \\(x^\\star\\) of  \\[  \\min_{\\tilde{x}\\in \\mathbb{R}^n}\\| \\tilde{x}\\| _{\\ell^1} \\quad{\\text{ subject\\,\\, to}}\\quad \\Phi x =y \\leqno{(\\star)} \\]  recovers \\(x\\) exactly provided \\(x\\) is {\\textit{sparse}} and the sensing matrix satisfies a {\\textit{restricted isometry property}}. A vector \\(x\\in \\mathbb{R}^N\\) is \\(s\\)-sparse if at most \\(s\\) of its coordinates are nonzero. For each \\(s=1,2,\\dots\\) the \\(s\\)-isometry constant of a matrix \\(\\Phi\\) is the smallest number \\(\\delta_s\\) such that  \\[  (1-\\delta_s)\\| x\\| _{\\ell^2}^2\\leq \\| \\Phi x\\| _{\\ell^2}^2\\leq (1+\\delta_s) \\| x\\| _{\\ell^2}^2  \\]  whenever \\(x\\) is \\(s\\)-sparse.  The first result applies to noiseless recovery, and states that if \\(\\delta_{2s}<\\sqrt{2}-1\\) then there is a constant \\(C\\) such that the solution \\(x^\\star\\) of (\\(\\star\\)) satisfies \\(\\| x^\\star -x\\| _{\\ell^1}\\leq C\\| x-x_s\\| _{\\ell^1}\\) and \\(\\| x^\\star -x\\| _{\\ell^2}\\leq C s^{-1/2}\\| x-x_s\\| _{\\ell^1}\\). In particular, the recovery is exact if \\(x\\) is \\(s\\)-sparse. The second result applies to the minimizer of  \\[  \\min_{\\tilde{x}\\in \\mathbb{R}^n}\\| \\tilde{x}\\| _{\\ell^1} \\quad{\\text{subject\\,\\, to}}\\quad y=\\Phi x =z \\leqno{(\\star\\star)} \\]  where \\(\\| z\\| _{\\ell^2}\\leq \\varepsilon\\). Assuming again that \\(\\delta_{2s}<\\sqrt{2}-1\\) it is shown that the solution of (\\(\\star\\star\\)) satisfies \\(\\| x^\\star-x\\| _{\\ell^2} \\leq C s^{-1/2}\\| x\\| _{\\ell^1}+ K\\varepsilon\\) for a second constant \\(K\\). How \\(C\\) and \\(K\\) depend on \\(\\delta_s\\) can be inferred from the proofs.  The bounds here improve those first established by the author and \\textit{T.~Tao} in [``Decoding by linear programming'', IEEE Trans. Inform. Theory 51 (12), 4203--4215 (2005)] where it was first shown that the \\(\\ell^1\\) minimizer of \\(\\Phi \\tilde x=y\\) recovers \\(x\\) when \\(x\\) is sufficiently sparse.","type":"string"},"datatype":"string"},"type":"statement","id":"Q927127$C52CF8F1-A6FD-4B3D-8FA8-3736163F54D5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4db3fc3244f368e49336c7e23443d11b7d69297d","datavalue":{"value":"94A12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q927127$967081EF-7C21-41E4-BB42-AF4B6F81807E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1ae636e904e167cb856da140da6a515bad7beb4d","datavalue":{"value":"94A20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q927127$9E22044D-7AA8-4D52-92DA-497B4AABB7EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4264b8bf260e532ba12469970b36fcaf09f85467","datavalue":{"value":"68P30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q927127$EFDC05AA-58BC-4001-B0C9-FBBD65701F68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f9ba159373090134e66ced5cd614c2df0d4d4427","datavalue":{"value":"42C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q927127$DF06D7DC-BA7A-4873-91D4-2FD69566F2BB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"66108418e7f0029860ef9e11ae4d9b3e7a9f8d78","datavalue":{"value":"5277937","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q927127$23DC8E68-719C-4E40-A416-FCC7B172D3B0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5f202c6be4f21e7a20465106399dc78b113847da","datavalue":{"value":"compressed sensing","type":"string"},"datatype":"string"},"type":"statement","id":"Q927127$E4D5C205-8D7D-455C-991C-9B071B3700AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"71d1a591ee1d479ca9ca2879cd26ad9045f936e0","datavalue":{"value":"restricted isometry property","type":"string"},"datatype":"string"},"type":"statement","id":"Q927127$9EC0D237-E9EC-4D0F-861B-AF7A976E9703","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8809f0dc08b4186854322a3add3771166d1970e5","datavalue":{"value":{"entity-type":"item","numeric-id":213815,"id":"Q213815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q927127$48FCC4DD-A21D-4C54-9786-7A82E65EC9C4","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":"Q927127$71641FD0-2555-4C36-AD70-5C7BE2E12E6E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2bfa9b1ac2cbcc47377f8fc549269a0f783daa4a","datavalue":{"value":"https://doi.org/10.1016/j.crma.2008.03.014","type":"string"},"datatype":"url"},"type":"statement","id":"Q927127$9067CC99-4F7D-435B-884E-CAB59FBB22AE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"00c9cce70c50cb91f7b43c193ff65f11cb94542d","datavalue":{"value":"W2015418199","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q927127$F7F762B5-22D7-4B12-99A1-8E8A62E3934B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb947d6385341f0ecd4224322e1ab06ac613c11e","datavalue":{"value":{"entity-type":"item","numeric-id":5486267,"id":"Q5486267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q927127$C139A3C0-9559-4BB8-A732-5FEE3487386E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ca89af4c05ff43e9b738e85ebed6de794460900","datavalue":{"value":{"entity-type":"item","numeric-id":3546644,"id":"Q3546644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q927127$F056D130-A9C7-4578-BD9B-B3EBB0BEDD59","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7d3fa16a005b9d33366737764b9477f698e18aaa","datavalue":{"value":"10.1016/J.CRMA.2008.03.014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q927127$8D12965B-F026-4525-AB34-8C8A4421F326","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad626c99922f461ebe5ef9eb6cf43d35afa6919c","datavalue":{"value":{"entity-type":"item","numeric-id":2923309,"id":"Q2923309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d062df20bdc379da6f4f7b882e752d0206e94dc","datavalue":{"value":{"amount":"+0.97650516","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q927127$F27CB99E-EBDE-49AA-ABC7-239E5797D6D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"840bca4f01915cc2cedbe37abb34c1fb9102c496","datavalue":{"value":{"entity-type":"item","numeric-id":3507945,"id":"Q3507945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f07c8defe40046f9bf012ed1fa290dd5602b4926","datavalue":{"value":{"amount":"+0.9728642","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q927127$EC49ABB4-79BD-46D8-ACCE-0D3BC6182626","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2bb200b1353f70467838842d568f37044fdc81a6","datavalue":{"value":{"entity-type":"item","numeric-id":5383572,"id":"Q5383572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c20f758dd9041c6a3d49f7cd4b75af51919b3311","datavalue":{"value":{"amount":"+0.9709492","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q927127$77931DEF-411A-4216-9DD1-1FEC256789BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"585246ac4d913bdf07c701ca215b54e6bced3e00","datavalue":{"value":{"entity-type":"item","numeric-id":905910,"id":"Q905910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"624cb4fdbad21f7ebae1b24e3e7d829fa12f9ff1","datavalue":{"value":{"amount":"+0.95265806","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q927127$E3C13C27-2FB2-4A38-B896-9A93E40D931B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"80daca147aae6a28865a93eb4d44202d80fb6235","datavalue":{"value":{"entity-type":"item","numeric-id":5346126,"id":"Q5346126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2da64d615451485a461b41ae90f953244946275a","datavalue":{"value":{"amount":"+0.9466311","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q927127$C778CDCA-2660-4F9A-9855-B0BC37D6BAAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bfb5becf9e40ebd7401cb76931555a618c00e01e","datavalue":{"value":{"entity-type":"item","numeric-id":695638,"id":"Q695638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b3535aad585932159a4989e31162a1b35e4fb677","datavalue":{"value":{"amount":"+0.94599885","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q927127$08EF731D-3558-4644-B55B-87EEDCF7D8C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e823c6917239e48a158112455175c251d2d3f2f","datavalue":{"value":{"entity-type":"item","numeric-id":3084491,"id":"Q3084491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad325a1c4d7c309f870342ae3d6451c0883d6bd3","datavalue":{"value":{"amount":"+0.943174","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q927127$63C5E6EB-DB26-4A16-A8EE-6373238F296A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58757cf3d592ee88401b7519f05ece1c225b4070","datavalue":{"value":{"entity-type":"item","numeric-id":334406,"id":"Q334406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a4631d0f03df8ab535a9251d0b766afde0fb1d4","datavalue":{"value":{"amount":"+0.9294577","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q927127$9586FA22-0466-46CC-B83D-5F32202D960B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65f2cc8a482ea4053ebae1024f1feceae7a0ee6a","datavalue":{"value":{"entity-type":"item","numeric-id":4578591,"id":"Q4578591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd16add5a4353f909e15b0211b83f0554e7a306d","datavalue":{"value":{"amount":"+0.92600137","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q927127$91C7F2AA-360A-47F0-B501-F1AF92BCED34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b66d48745bff481a29dc0b4dfe18470721f6b78","datavalue":{"value":{"entity-type":"item","numeric-id":5266378,"id":"Q5266378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1911b91e80027bbcc9a22346aa62dc91371a33b7","datavalue":{"value":{"amount":"+0.91568583","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q927127$D4199ADC-C22E-404B-9ED0-9C95CE724D82","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:927127","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:927127"}}}}}