{"entities":{"Q2925527":{"pageid":2936247,"ns":120,"title":"Item:Q2925527","lastrevid":52112273,"modified":"2026-01-20T23:17:19Z","type":"item","id":"Q2925527","labels":{"en":{"language":"en","value":"Deterministic algorithms for matrix completion"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6356979"}},"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":"Q2925527$CA74BE92-3B2B-4CE1-81AF-71D4C234612B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7f889596efea6c1a2735ad8ae585e98cf8c95910","datavalue":{"value":{"text":"Deterministic algorithms for matrix completion","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2925527$ED7AE873-3E75-4D35-8CF9-98065AB1DC8A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"91fa3c7043b6941d1a83ac781d959072da4e1528","datavalue":{"value":"1306.15027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2925527$02FF6B07-6B0C-4C95-854E-05656428B21B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fc65834e2b42d275cad8dfe509f0dfa0376ce1a8","datavalue":{"value":{"entity-type":"item","numeric-id":2925526,"id":"Q2925526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2925527$B88C7058-26CE-46E0-86BF-05490472DD58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a1ed22a01186aa8963d7a247e014c8e94e93219e","datavalue":{"value":{"entity-type":"item","numeric-id":281488,"id":"Q281488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2925527$86FBA2EF-E0B6-4B16-8A0A-D5A71BCA5EC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1e3625d8a7bc166a763f5261368249a556bac7de","datavalue":{"value":{"entity-type":"item","numeric-id":626626,"id":"Q626626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2925527$0090B5EB-1188-439E-B1AB-E29DCE66D152","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8bf8bd8f9bc724703ae7642bd9fc1fa56d190149","datavalue":{"value":{"time":"+2014-10-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2925527$6144FB12-3317-42C0-BF8C-9FE2981F738E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a59854f7423b54f32c0e0afdff69df764e2e9fe7","datavalue":{"value":"15A83","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2925527$414D207D-A763-4A6C-8136-EADDA29C639A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2925527$251790A6-2529-48A3-AEA9-04EE6355CB67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b353ca9fa5871b5d283994bd1f10d77c55504354","datavalue":{"value":"15A18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2925527$F94C768B-770C-404E-9F1E-DC1D6FBB0ED2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"de015211c641081855981090b49964fceb04e0c6","datavalue":{"value":"15A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2925527$BCE81291-D024-4947-838A-50C2A7C6B610","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bfe75be4d2491a30ac7b001bc3465f16a7d58d17","datavalue":{"value":"6356979","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2925527$CF86FB50-BADC-400D-B06D-0FB6ACABF450","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"65fe26c6194fa278a1d7c269258be9405c3e29db","datavalue":{"value":"matrix completion","type":"string"},"datatype":"string"},"type":"statement","id":"Q2925527$B487AB6F-AD5C-419A-9E4F-6206060B84A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7eb7ce57864bad79eb8b1130037c18cbe7109e9b","datavalue":{"value":"expander graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2925527$516CF7BF-D0B3-440B-AC88-925AE0036B7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f838fa86743fc0808fbf748cde003e94b8b797e8","datavalue":{"value":"graph sparsifiers","type":"string"},"datatype":"string"},"type":"statement","id":"Q2925527$189A5470-D6A6-4293-9168-92025697B0EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f7dd4979c30b48a5a2b592215a8383247af917bd","datavalue":{"value":"factorization norms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2925527$6F943143-2B19-4B12-B20B-367680B6E5C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"541bcbb0716e5b298dfc488c84cedd2f10dd9418","datavalue":{"value":"deterministic guarantees","type":"string"},"datatype":"string"},"type":"statement","id":"Q2925527$3CB6384B-BAF9-4AAA-B021-5E6B0063F9E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2621a7f114359c15599320f635eb9b30e969bde4","datavalue":{"value":"eigenvalue","type":"string"},"datatype":"string"},"type":"statement","id":"Q2925527$5048A237-9796-40B5-A107-D13531254187","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6723883e050c3d834a51898f23b8f0064ff8657e","datavalue":{"value":"Frobenius norm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2925527$DC9339D3-20D1-4DE4-9B7D-1E5F712845BC","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":"Q2925527$1DD0119B-F70D-45E8-89ED-3B7FD879D8B5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d4705b4f8e08461fd0a7d47f0d404534910f5ec0","datavalue":{"value":"https://doi.org/10.1002/rsa.20483","type":"string"},"datatype":"url"},"type":"statement","id":"Q2925527$979FB85F-199B-43EC-8077-F33B263E5A39","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bdb4aec7da32580e9bdd646808bc883131b754ba","datavalue":{"value":"W2069652865","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2925527$DD947A3E-8585-4578-B107-8497699D2449","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":"Q2925527$0B2D8084-A7CF-4EF9-8652-EF5F27EDC5D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4cdd9ea1058aa803df34da47c73be3afe11b3e31","datavalue":{"value":{"entity-type":"item","numeric-id":2655288,"id":"Q2655288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2925527$83098579-346D-4A8E-AA12-0DEA18AF96B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30938bdab56f36beecd19d0a2e1a650805646eb4","datavalue":{"value":{"entity-type":"item","numeric-id":5281478,"id":"Q5281478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2925527$7CD1C921-32F2-4228-BF07-770534F7E904","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca4be033dc1e037b43c1538205386964bc6ef38a","datavalue":{"value":{"entity-type":"item","numeric-id":3514498,"id":"Q3514498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2925527$FBB6C4D2-9CE1-4580-A08F-7F658D29F254","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"004257620487ea3c7aeea61dfabfd3a5153a21a4","datavalue":{"value":{"entity-type":"item","numeric-id":3772707,"id":"Q3772707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2925527$E9FEF25C-B22D-490A-9785-CFA6E440D44E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92ee438e4331d2f3b16b6141dbc9f1963b4ed112","datavalue":{"value":{"entity-type":"item","numeric-id":2896128,"id":"Q2896128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2925527$2B748AE6-F806-48BE-8FE6-A80341BE7FAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d956f8d50994fbb74f61ee91547a07864c5ddc4","datavalue":{"value":{"entity-type":"item","numeric-id":661157,"id":"Q661157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2925527$D43626DE-819C-4331-8530-E4E6AE8BA94D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"10ccf4d42c4757827ddea695c7555934bd0854b7","datavalue":{"value":{"entity-type":"item","numeric-id":1112836,"id":"Q1112836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2925527$68A6A811-31A7-4D41-B188-1D395CD1552B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5361721c899c034b78894752028388868f9aad6d","datavalue":{"value":{"entity-type":"item","numeric-id":5396731,"id":"Q5396731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2925527$F089096A-319D-45B0-9E49-4604416888D0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3db499dafff696f7c2ca6e3decf3e337f71b8aa9","datavalue":{"value":"10.1002/RSA.20483","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2925527$D53E4D06-D3E2-4300-A5C6-8C25E09E6891","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"607ae7f7d11ced7a8909533172911c64cec6dcc4","datavalue":{"value":{"entity-type":"item","numeric-id":6486797,"id":"Q6486797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2925527$DEBA83F4-2923-4009-AE4C-297341F17F0A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b73dc9ca7e204583e69fe5197e0e715c97bcabb7","datavalue":{"value":"Let \\(Y\\) be a real \\(n\\times n\\) matrix for which we only know the entries at a set \\(S\\) of positions. The objective of the matrix completion problem is to find a matrix \\(X\\) lying within a restricted class (for example, \\(X\\) may be restricted by the rank or trace norm) such that \\(X\\) is close to \\(Y\\) in a suitable sense. In typical applications we predict preferences in movies from a knowledge of past viewing choices (the Netflix challenge) or predict unknown values from partial experimental data (see, for example [\\textit{N. Srebro} and \\textit{A. Shraibman}, Lect. Notes Comput. Sci. 3559, 545--560 (2005; Zbl 1137.68563)]). Since the appearance of the latter paper there have been various analyses of the completion problem under the assumption that \\(S\\) is a randomly chosen set of positions.NEWLINENEWLINEIn the current paper, the authors consider the case where we are allowed to choose \\(S\\) (before knowing the values of the corresponding entries of \\(Y\\)). They propose choosing a \\(d\\)-regular expander graph \\(G\\) on the set\\(\\left\\{ 1,\\dots,n\\right\\} \\) and then taking \\(S\\) as the set of edges of \\(G\\). The largest eigenvalue of the adjacency matrix of \\(G\\) is equal to \\(d\\); let \\(\\lambda\\) be the maximum in absolute value of the remaining eigenvalues. For a suitable choice of \\(G\\) (for example, if \\(G\\) is a Ramanujan expander), it is possible to choose \\(G\\) so that \\(\\lambda=O(\\sqrt{d})\\). In this case, the authors prove that it is possible to find \\(X\\) such that the Frobenius norm \\(\\left\\| Y-X\\right\\| \\;\\) is bounded by \\(O(nd^{-1/4}\\gamma_{2}(Y))\\), where \\(\\gamma_{2}(Y)\\) denotes the \\(\\gamma_{2}\\)-norm (the result stated in the paper is more precise). Further results and conjectures are included.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2925527$C70717E7-C209-41A2-9582-9644DF683D02","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"bac883d785667a63a92fc8927c00d4d1184f1321","datavalue":{"value":{"entity-type":"item","numeric-id":590084,"id":"Q590084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2925527$B66BE4F2-6711-4770-891B-FBD7D9DDB17F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"647ce0caf7e111569d9bb6f74df94933f3be0cbd","datavalue":{"value":{"entity-type":"item","numeric-id":2896128,"id":"Q2896128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c14c04d896ac84497e79b864839397532d5c2948","datavalue":{"value":{"amount":"+0.7749526500701904","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":"Q2925527$EEDB1366-1E05-4360-8043-2DDD91A84D8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d335f9f76ba1137ef9096b6d93fc7665a8822710","datavalue":{"value":{"entity-type":"item","numeric-id":2900327,"id":"Q2900327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc54774ac156c44cee5bb4dd913efee5184e8e18","datavalue":{"value":{"amount":"+0.769588828086853","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":"Q2925527$780DCCFD-3BF6-426D-A444-1A7C111D8139","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"948dcca256237ca3e94f1647b5eb0a2e2f31e820","datavalue":{"value":{"entity-type":"item","numeric-id":5396731,"id":"Q5396731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72f25a0be2ca64265cf40a219dd04036994cdf3e","datavalue":{"value":{"amount":"+0.766777515411377","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":"Q2925527$50022924-AE12-460C-9758-BC1D9DE691B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35f6bcc2ac14f2307654d918d2b8cdba07b70ee8","datavalue":{"value":{"entity-type":"item","numeric-id":2896145,"id":"Q2896145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af8a2157e5905d630ba21a55e41ab506284c550e","datavalue":{"value":{"amount":"+0.7601447105407715","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":"Q2925527$CC4C2E77-13D2-48FF-98B5-35491EF01C25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b62a7cebf2e4d27bf1259a0527ea214c5114494","datavalue":{"value":{"entity-type":"item","numeric-id":2655288,"id":"Q2655288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f348169f97d22dfbc77ef734a0b9019b6ecb4da6","datavalue":{"value":{"amount":"+0.7593081593513489","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":"Q2925527$0791D30A-EC25-4103-9EC1-9BEF6BE4F76C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2925527","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2925527"}}}}}