{"entities":{"Q1760392":{"pageid":1771134,"ns":120,"title":"Item:Q1760392","lastrevid":57540078,"modified":"2026-03-31T08:06:51Z","type":"item","id":"Q1760392","labels":{"en":{"language":"en","value":"An elementary proof of the restricted invertibility theorem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6105502"}},"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":"Q1760392$DDEA4718-C0BD-43C8-970C-EB28103B5984","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b01fbc564ce3e445704ca5ac082f112e8a649925","datavalue":{"value":{"text":"An elementary proof of the restricted invertibility theorem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1760392$DAF01E8A-6500-47B3-9A7B-1A538A120B29","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"08e311ff50f65b57fe7cfef921534007a51efb32","datavalue":{"value":"1261.46007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1760392$CAC588D2-BDC5-4388-A904-CAB01184D453","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ce695d83af1ce7f26884308615d4302d3c2f8988","datavalue":{"value":{"entity-type":"item","numeric-id":623361,"id":"Q623361"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1760392$5A1931AF-045D-4D5B-8A8B-832BCF698C0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"53c8029fd31886dd0423aade1b5586771ee9782c","datavalue":{"value":{"entity-type":"item","numeric-id":378787,"id":"Q378787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1760392$AF9723F9-48D9-4682-AAF0-18E9549C0E24","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1d50f9b953eac0b2404563f86ad398ee3823cb48","datavalue":{"value":{"entity-type":"item","numeric-id":173732,"id":"Q173732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1760392$F7D5ED35-8D6A-4F91-A6E9-E31F208EBC82","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5c80839e4a0921a35f61ead63f84da81a31ae4c5","datavalue":{"value":{"time":"+2012-11-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":"Q1760392$06D8FCCF-0A3F-4F06-AB83-7A5C00C65330","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"471559bd0f1d90a67e657c59d13cc7c8d211d2e0","datavalue":{"value":"https://arxiv.org/abs/0911.1114","type":"string"},"datatype":"url"},"type":"statement","id":"Q1760392$0EBD422F-0ECA-4A72-9F58-B83D18CFDB42","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5f9219e742be4bf8b545f2d488663dd214f5652f","datavalue":{"value":"In a seminal and oft-quoted paper [Isr. J. Math. 57, 137--224 (1987; Zbl 0631.46017)], \\textit{J. Bourgain} and \\textit{L.Tzafriri} proved their ``restricted invertibility theorem'' for operators on finite-dimensional \\(\\ell_p\\)-spaces. The case \\(p=2\\) is of special interest; in this case, their theorem reads as follows. There exist constants \\(c,d>0\\) such that, whenever \\(T: \\ell_2^n \\to \\ell_2^n\\) is a linear operator satisfying the normalisation \\(\\|Te_i\\|=1\\) for all~\\(i\\), there is a subset \\(\\sigma\\subset \\{1,\\dots,n\\}\\) of proportional size, i.e., of cardinality \\(|\\sigma|\\geq cn/\\|T\\|^2\\), such that \\(T\\) is well invertible on \\(\\text{span}\\{e_i: i\\in\\sigma\\}\\) in that \\(\\|Tx\\|\\geq d\\|x\\|\\) for all vectors supported on~\\(\\sigma\\). The point is, of course, that \\(c\\) and \\(d\\) are independent of~\\(n\\).  In their paper, Bourgain and Tzafriri gave a beautiful proof that was, however, not constructive and was based on deep probabilistic and combinatorial reasoning. (In fact, they even gave two proofs.) Also, they did not pay any attention to the size of the constants.  The paper under review presents a new proof that is elementary in that it only uses linear algebra, it is algorithmic in that the desired set \\(\\sigma\\) is found by an iterative process, and it gives better constants; in fact, for \\(0<\\alpha<1\\), one can achieve \\(c=\\alpha^2\\) and \\(d=(1-\\alpha)^2\\) so that for \\(\\alpha\\approx 0\\), \\(d\\) is close to~\\(1\\), and for \\(\\alpha\\approx 1\\), \\(c\\) is close to~\\(1\\). Actually, the authors prove a generalisation of the Bourgain-Tzafriri theorem from which that result follows readily.  Reviewer's remark: An even simpler version of the proof giving slightly worse constants, based on the arguments of the present paper, was provided by \\textit{P. G. Casazza} [``The simplified version of the Spielman and Srivastava algorithm for proving the Bourgain-Tzafriri restricted invertiblity theorem'' (2012), \\url{arXiv:1208.4013}].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1760392$A4A7A848-6FA7-448F-96E3-35D60AAD4B56","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"098587d627d11b69ddd36652699d57f211999689","datavalue":{"value":{"entity-type":"item","numeric-id":203344,"id":"Q203344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1760392$D95924EF-57E0-4B2C-83B7-4190E089FD28","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"79f8d64a9a918483c4e5229e22c3ea6d9711b362","datavalue":{"value":"46B07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1760392$EA8869A9-8932-464E-A3C4-933FDBE0E257","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"257fb80f6fe220f70a8864b3e9143137481c0d32","datavalue":{"value":"47A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1760392$FE604388-5C8D-4A07-AAD8-9BF32F9D3C9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"de015211c641081855981090b49964fceb04e0c6","datavalue":{"value":"15A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1760392$37943D03-4E08-4E81-B747-6201366E3952","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f9366f971a2e74ee8ea4e63974e09e9d85a8aefc","datavalue":{"value":"6105502","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1760392$F19EEC71-81FC-4F26-82FF-F41BE9F1CECB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aa25f3349927f2ece799cb7b8566644f296180b4","datavalue":{"value":"restricted invertibility theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1760392$199B9F94-CE0C-48F1-ADD4-F8C609F814DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4a294b4bea27cb84785e8096e75f75b5a9f8a2c6","datavalue":{"value":"restricted invertibility of matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1760392$D112823C-B859-4052-AC0E-4A6C99B4D864","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4b2957e4d2f23158868993e931aeb0324294f765","datavalue":{"value":"Kadison-Singer problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1760392$00B9224B-2828-4703-A413-30AAA6FBF909","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":"Q1760392$5684F471-9E06-40CF-AAE2-727CBB3B7B29","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c3574a1047ed7635b7fd909e30303ab8a1b6c137","datavalue":{"value":"W2034070643","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1760392$5227302A-5A2C-4B71-B634-A4003DB037D4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3835019ecd9972bdae50af94e6db43bb91fe6b33","datavalue":{"value":{"entity-type":"item","numeric-id":5172719,"id":"Q5172719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1760392$C29F40C4-28D2-4FE4-AA63-CC953707D7E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8c7889082c03af207582ecf0c4d7c61c52b73f9","datavalue":{"value":{"entity-type":"item","numeric-id":3791716,"id":"Q3791716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1760392$BAEE5878-F677-43FD-A1EB-6B883E25046F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31f572d8581e911140a27033eaa6acf745dc4959","datavalue":{"value":{"entity-type":"item","numeric-id":1094628,"id":"Q1094628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1760392$308FF1F7-7A27-451C-B741-AF2DFBCF5E7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d64654fd3266cbe258ff387a76d96463b6faa275","datavalue":{"value":{"entity-type":"item","numeric-id":3353637,"id":"Q3353637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1760392$4675F2CC-0969-4150-9F96-D73E56ED5671","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbe09f1239793f2bf24dded7f7519e5eabf71243","datavalue":{"value":{"entity-type":"item","numeric-id":3622654,"id":"Q3622654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1760392$9B1ACFE1-1077-4574-9504-A5C549E472B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"189badd413ee3575f3e4a352c01f0731d8ea8f40","datavalue":{"value":{"entity-type":"item","numeric-id":5935812,"id":"Q5935812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1760392$0DC8C6B5-6005-4971-97B2-E5F3D85245C9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a2fff3dc0e7fb8dc9033778a71bbaf6e03af93db","datavalue":{"value":"10.1007/S11856-011-0194-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1760392$4C365205-2FAA-4F8A-895A-E193B5DA4889","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"568d6e23eb7d841ef750cc42e843cfea92fa04b1","datavalue":{"value":{"entity-type":"item","numeric-id":2143246,"id":"Q2143246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"519bbd6d2978b4edc9637e9e7849bdae96e4e0d4","datavalue":{"value":{"amount":"+0.8361822962760925","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":"Q1760392$6F66225F-9E75-4FBC-B10E-C3C0E2CD395F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a8d545227d19aaa5c0a07e7b04bdce38304d2ad","datavalue":{"value":{"entity-type":"item","numeric-id":3475879,"id":"Q3475879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef859d6f51d24bf365f075931aa29d95a9f5fd66","datavalue":{"value":{"amount":"+0.8258351683616638","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":"Q1760392$7DB30B03-3213-4BE0-B0DD-16E77D0D4618","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7bce87ced0273b781bee077dbf8579b047caa52a","datavalue":{"value":{"entity-type":"item","numeric-id":4604394,"id":"Q4604394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fec0d5c6b52cd7c57a5e0f658ba28435d13c7782","datavalue":{"value":{"amount":"+0.8136060237884521","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":"Q1760392$D79305E8-3516-47A2-8C46-54385E681A63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a09f535420c33249b04b4ad37b9e7a5891bb6c53","datavalue":{"value":{"entity-type":"item","numeric-id":3622654,"id":"Q3622654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d2504ba355f79ebd15fe3214dcd55c9674eda05","datavalue":{"value":{"amount":"+0.808509111404419","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":"Q1760392$29192712-C626-494E-AFBC-B40E17B46AAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8fcb6861c2e5fe050b3216745ebc4f9268eb5e6b","datavalue":{"value":{"entity-type":"item","numeric-id":2935162,"id":"Q2935162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd9727ba92aa60de978e2bdac2af065d78e99dc5","datavalue":{"value":{"amount":"+0.8008127808570862","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":"Q1760392$06B7F4E2-21B8-43A7-86B6-84D7AA2482BE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1760392","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1760392"}}}}}