{"entities":{"Q5944137":{"pageid":8120939,"ns":120,"title":"Item:Q5944137","lastrevid":93613697,"modified":"2026-06-05T04:42:09Z","type":"item","id":"Q5944137","labels":{"en":{"language":"en","value":"A counter-example to the general convergence of partially greedy algorithms"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1652663"}},"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":"Q5944137$A8545B9D-F242-4FC1-A121-4DA8CDDEDBF6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e0f1becb112c9e4800b831271259dbc005174c4c","datavalue":{"value":{"text":"A counter-example to the general convergence of partially greedy algorithms","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5944137$79618D5E-244F-4259-B200-757B4DDF05CD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"94ef9433739a190f3b269bc18dc87901d4f7dbff","datavalue":{"value":"0991.65014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5944137$08DA6944-D825-4F1E-800B-9CA00AC9AA4B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1041088e54f26be00c40335d877668364f17d152","datavalue":{"value":{"entity-type":"item","numeric-id":629252,"id":"Q629252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5944137$DD5A7934-B56C-4CF1-9829-99F2FF19A46D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"516630d92eaedf7cfe9e823e532b86ae99614779","datavalue":{"value":{"entity-type":"item","numeric-id":171758,"id":"Q171758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5944137$410497B1-613B-4C8A-85A6-4C9321B43DA8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0004237905b7322cb3b10a20c84f2f03323c8c30","datavalue":{"value":{"time":"+2002-08-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5944137$5A506728-6206-4AFD-9137-7455D043F48C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1de67e8c9bdd014fbdd895341c72f16e387df71b","datavalue":{"value":"https://hal.inria.fr/inria-00576644/file/vwga.pdf","type":"string"},"datatype":"url"},"type":"statement","id":"Q5944137$DD27575B-3247-4E11-BF31-7E0891273F70","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0f24e5a1d8777e7304344fc5c751c169ded4359b","datavalue":{"value":{"entity-type":"item","numeric-id":189193,"id":"Q189193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5944137$467BCC3B-ED71-49C5-96D5-94E28BB243F0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2afc8b14470e661c10725547661d94fa1583b792","datavalue":{"value":"65D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5944137$6E862B7F-EAF7-41E7-B3F8-1F8AF657037E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"89346f20a6c5c6b864a211d37f17719b2851c4ad","datavalue":{"value":"41A65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5944137$96626BDE-5D23-4639-9308-4D39ADBD225A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a46d831259493f05707be1b8dc8ce3db73fd0637","datavalue":{"value":"41A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5944137$6E8D1C5B-9DA1-4755-B0D2-A3BFFDA318FC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"52041011be4194f29925875349ed4556b2f2239a","datavalue":{"value":"1652663","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5944137$8702729E-735D-451A-AFB7-BDAC590FB885","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e1e7eb452ae4c92c43fa47bb0afb8177365a429","datavalue":{"value":"greedy algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q5944137$1E2F3A09-8B35-4AEE-924C-193538713AF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"671bd1456fc47ff95062b294452d1d02fa5683ca","datavalue":{"value":"redundant dictionary","type":"string"},"datatype":"string"},"type":"statement","id":"Q5944137$3C8B3BA8-0110-4DC3-8F93-CA2A6D32D9CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"27db29e1545997752d0ba25fa3e41f101d1cfb85","datavalue":{"value":"Hilbert space","type":"string"},"datatype":"string"},"type":"statement","id":"Q5944137$8D47ADFE-BC1A-4ED9-82AA-C679C3940614","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"03ee0109af41ad406ecd743518061baaa9e5e3ff","datavalue":{"value":"convergence","type":"string"},"datatype":"string"},"type":"statement","id":"Q5944137$E33B1A10-9B52-4223-9D46-E62E7D78DD03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84ab1776b8c66a0a62f95c95244a95d24556b0ba","datavalue":{"value":"iterative processes","type":"string"},"datatype":"string"},"type":"statement","id":"Q5944137$694D36A7-5BB9-4343-A16E-373F997E5667","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a56e5793ea33870a204239ad40fe7f02bf24fac2","datavalue":{"value":"expansion","type":"string"},"datatype":"string"},"type":"statement","id":"Q5944137$3C405BE1-4891-4D04-9FC4-0AA2BBC9E343","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8498efe9200547b17fe201705731ef1eccefd826","datavalue":{"value":"counter example","type":"string"},"datatype":"string"},"type":"statement","id":"Q5944137$120C9D0C-46F9-4CA6-9138-6AF3F7DC10FA","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":"Q5944137$D4EB25D8-09C8-41EA-B06B-2B08ED5145B5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2da2d99c0476a97a89a6371ec63c8f01aea37e1c","datavalue":{"value":"W2049600182","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5944137$B793C14D-21DC-4DDA-96FA-43F499B731A2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f732e171f01b13e8b86aef5142dc01f586d5f2e9","datavalue":{"value":{"entity-type":"item","numeric-id":1352435,"id":"Q1352435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5944137$ED52CF84-B918-427E-A33E-EDF20813B9A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c5e36a388b9c1809825c781d98f338991497c8b","datavalue":{"value":{"entity-type":"item","numeric-id":1923887,"id":"Q1923887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5944137$F1BCBE79-C6D9-4DE9-863F-F34DB9EB9779","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1ae88881bb945d673c51a49f9a790ad5cc95203","datavalue":{"value":{"entity-type":"item","numeric-id":5353486,"id":"Q5353486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5944137$49DD3BE5-702D-4F32-BEC8-3683BFC9ECCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ca47f073e8a2b31eab790524896f83d596a9c83","datavalue":{"value":{"entity-type":"item","numeric-id":1077847,"id":"Q1077847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5944137$D926EA5C-6A65-418C-8814-F04C123A191B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"316ee831f4af35021f33f09ba2c9e294dc67c247","datavalue":{"value":{"entity-type":"item","numeric-id":1115065,"id":"Q1115065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5944137$1EAB5193-9EB9-46FE-8660-E7AF1BFC06BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06f1a4698803d2da68cedeb23201a099c684069c","datavalue":{"value":{"entity-type":"item","numeric-id":4878180,"id":"Q4878180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5944137$1E2228DD-A79A-44CC-97B8-C30FD97C6A2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a823e3fc2be574e6ea966ff11243e7f3d522b4da","datavalue":{"value":{"entity-type":"item","numeric-id":4005831,"id":"Q4005831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5944137$4BDAB62B-1108-45D3-AEF2-7B2B80667724","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b632704e8cecff51512352f8659e8b30cc25ad5","datavalue":{"value":{"entity-type":"item","numeric-id":1968628,"id":"Q1968628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5944137$46E6E3FA-E818-4EA4-873E-7685287DE911","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"accb5bfe4eb985009aafa956092db594d0ddd333","datavalue":{"value":"10.1006/JATH.2001.3566","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5944137$78DEF278-2DAA-42B3-AD20-6F0676326484","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"83d4bb0cab63c2fd604189df58364989c6214952","datavalue":{"value":"Greedy algorithms in a separable Hilbert space \\({\\mathcal H}\\) for approximating a given vector \\(R_1\\) with a complete dictionary \\({\\mathcal D}\\) are iterative processes of constructing an expansion of \\(R_1\\): NEWLINE\\[NEWLINE R_1=\\langle R_1,g_1\\rangle g_1+\\langle R_2,g_2\\rangle g_2+\\cdots+\\langle R_m,g_m\\rangle g_m+R_{m+1}.NEWLINE\\]NEWLINE Here \\(R_m\\in{\\mathcal H}\\), and \\(g_m\\in{\\mathcal D}\\) are chosen such that NEWLINE\\[NEWLINE R_m=\\langle R_m,g_m\\rangle g_m +R_{m+1}\\quad \\text{with} \\quad |\\langle R_m,g_m\\rangle|=\\sup_{g\\in{\\mathcal D}}|\\langle R_m,g\\rangle|. NEWLINE\\]NEWLINE If the dictionary \\({\\mathcal D}\\) is large, computation of \\(g_m\\) can be too costly. Partially greedy algorithms search for \\(g^*_m\\) in a compelte subdictionary \\({\\mathcal D}^*\\) of \\({\\mathcal D}\\) and further improve it with a ``locally optimal'' \\(g_m\\in {\\mathcal D}\\) such that NEWLINE\\[NEWLINE |\\langle R_m,g_m\\rangle|\\geq |\\langle R_m,g_m^*\\rangle|=\\sup_{g\\in{\\mathcal D}^*}|\\langle R_m,g\\rangle|. NEWLINE\\]NEWLINE A natural conjecture is that if \\({\\mathcal D}^*\\subset {\\mathcal D}\\) are two complete disctionaries, then the residual \\(\\|R_m\\|\\) should converge to zero. This paper disproves this conjecture with a counter example and discusses its implications.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5944137$95918D23-F090-49F9-86D3-310F5E831E6E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a343e6e3faec3a152e81dff08a52025cd6c45f8","datavalue":{"value":{"entity-type":"item","numeric-id":4825565,"id":"Q4825565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fcaa1b8fe17593174aad22e90933a458afa3d30a","datavalue":{"value":{"amount":"+0.9331603050231934","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":"Q5944137$627BF61A-C92F-427B-8D73-A8C67CEA9444","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f88d65f4b43773d7d29b42788f8c278803d863b4","datavalue":{"value":{"entity-type":"item","numeric-id":652444,"id":"Q652444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1fe8637d8aef10256f710343f2f9bc63f6c28a05","datavalue":{"value":{"amount":"+0.8347548246383667","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":"Q5944137$D4506CCB-3752-4961-8E37-AC9EB41EE8A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"80b17a9848251c7332c8a7a93d899d42f1ae424c","datavalue":{"value":{"entity-type":"item","numeric-id":2577360,"id":"Q2577360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c57c538a14946c90c8fe1af2a75cd36675f73772","datavalue":{"value":{"amount":"+0.8079928159713745","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":"Q5944137$01A687F4-1C16-4003-9C5B-F52986C2063F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"68b8771deb0f5a103ba2e11a177c1afddd6e1cbb","datavalue":{"value":{"entity-type":"item","numeric-id":5950886,"id":"Q5950886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5af2242608b152cdd7dff9918a6d4ec2259e766","datavalue":{"value":{"amount":"+0.8041916489601135","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":"Q5944137$A89DA55F-7972-4F39-A263-E30D8044658B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e72d963c66a3fcca9faa86485dd8ff9e576f695a","datavalue":{"value":{"entity-type":"item","numeric-id":2170508,"id":"Q2170508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"60b5e6e6172fed870ab2b26773291dd5996ad832","datavalue":{"value":{"amount":"+0.8034698367118835","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":"Q5944137$C4791C59-EF57-4E09-AD13-FB42237001B1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A counter-example to the general convergence of partially greedy algorithms","badges":[]}}}}}