{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,4]],"date-time":"2026-07-04T14:17:55Z","timestamp":1783174675937,"version":"3.54.6"},"reference-count":49,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T00:00:00Z","timestamp":1790812800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T00:00:00Z","timestamp":1790812800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T00:00:00Z","timestamp":1790812800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T00:00:00Z","timestamp":1790812800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T00:00:00Z","timestamp":1790812800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T00:00:00Z","timestamp":1790812800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T00:00:00Z","timestamp":1790812800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"funder":[{"DOI":"10.13039\/501100004731","name":"Zhejiang Province Natural Science Foundation","doi-asserted-by":"publisher","award":["LQN25A010002"],"award-info":[{"award-number":["LQN25A010002"]}],"id":[{"id":"10.13039\/501100004731","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100010906","name":"NSAF Joint Fund","doi-asserted-by":"publisher","award":["U21A20426"],"award-info":[{"award-number":["U21A20426"]}],"id":[{"id":"10.13039\/501100010906","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12471096"],"award-info":[{"award-number":["12471096"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12401124"],"award-info":[{"award-number":["12401124"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Journal of Complexity"],"published-print":{"date-parts":[[2026,10]]},"DOI":"10.1016\/j.jco.2026.102056","type":"journal-article","created":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T02:36:51Z","timestamp":1778812611000},"page":"102056","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Nonconvex deterministic matrix completion by projected gradient descent methods"],"prefix":"10.1016","volume":"96","author":[{"given":"Hang","family":"Xu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Song","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Junhong","family":"Lin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/j.jco.2026.102056_br0290","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1109\/LSP.2017.2780983","article-title":"On deterministic sampling patterns for robust low-rank matrix completion","volume":"25","author":"Ashraphijuo","year":"2017","journal-title":"IEEE Signal Process. Lett."},{"key":"10.1016\/j.jco.2026.102056_br0440","doi-asserted-by":"crossref","first-page":"1849","DOI":"10.1109\/TSP.2019.2899315","article-title":"Low-rank data completion with very low sampling rate using Newton's method","volume":"67","author":"Ashraphijuo","year":"2019","journal-title":"IEEE Trans. Signal Process."},{"key":"10.1016\/j.jco.2026.102056_br0260","series-title":"Int. Conf. Mach. Learn.","first-page":"1881","article-title":"Universal matrix completion","author":"Bhojanapalli","year":"2014"},{"key":"10.1016\/j.jco.2026.102056_br0150","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/s10107-002-0352-8","article-title":"A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization","volume":"95","author":"Burer","year":"2003","journal-title":"Math. Program."},{"key":"10.1016\/j.jco.2026.102056_br0380","series-title":"Deterministic Matrix Completion Using Ramanujan Graphs","author":"Burnwal","year":"2021"},{"key":"10.1016\/j.jco.2026.102056_br0300","doi-asserted-by":"crossref","first-page":"3834","DOI":"10.1109\/TSP.2020.2997180","article-title":"Deterministic completion of rectangular matrices using asymmetric Ramanujan graphs: exact and stable recovery","volume":"68","author":"Burnwal","year":"2020","journal-title":"IEEE Trans. Signal Process."},{"key":"10.1016\/j.jco.2026.102056_br0230","doi-asserted-by":"crossref","first-page":"1956","DOI":"10.1137\/080738970","article-title":"A singular value thresholding algorithm for matrix completion","volume":"20","author":"Cai","year":"2010","journal-title":"SIAM J. Optim."},{"key":"10.1016\/j.jco.2026.102056_br0050","doi-asserted-by":"crossref","first-page":"925","DOI":"10.1109\/JPROC.2009.2035722","article-title":"Matrix completion with noise","volume":"98","author":"Cand\u00e8s","year":"2010","journal-title":"Proc. IEEE"},{"key":"10.1016\/j.jco.2026.102056_br0040","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1007\/s10208-009-9045-5","article-title":"Exact matrix completion via convex optimization","volume":"9","author":"Cand\u00e8s","year":"2009","journal-title":"Found. Comput. Math."},{"key":"10.1016\/j.jco.2026.102056_br0130","doi-asserted-by":"crossref","first-page":"2053","DOI":"10.1109\/TIT.2010.2044061","article-title":"The power of convex relaxation: near-optimal matrix completion","volume":"56","author":"Cand\u00e8s","year":"2010","journal-title":"IEEE Trans. Inf. Theory"},{"key":"10.1016\/j.jco.2026.102056_br0450","doi-asserted-by":"crossref","first-page":"1985","DOI":"10.1109\/TIT.2015.2399924","article-title":"Phase retrieval via Wirtinger flow: theory and algorithms","volume":"61","author":"Cand\u00e8s","year":"2015","journal-title":"IEEE Trans. Inf. Theory"},{"key":"10.1016\/j.jco.2026.102056_br0180","doi-asserted-by":"crossref","first-page":"5806","DOI":"10.1109\/TIT.2020.2992234","article-title":"Nonconvex rectangular matrix completion via gradient descent without \u21132,\u221e regularization","volume":"66","author":"Chen","year":"2020","journal-title":"IEEE Trans. Inf. Theory"},{"key":"10.1016\/j.jco.2026.102056_br0220","doi-asserted-by":"crossref","first-page":"2909","DOI":"10.1109\/TIT.2015.2415195","article-title":"Incoherence-optimal matrix completion","volume":"61","author":"Chen","year":"2015","journal-title":"IEEE Trans. Inf. Theory"},{"key":"10.1016\/j.jco.2026.102056_br0410","author":"Chen"},{"key":"10.1016\/j.jco.2026.102056_br0090","doi-asserted-by":"crossref","first-page":"5239","DOI":"10.1109\/TSP.2019.2937282","article-title":"Nonconvex optimization meets low-rank matrix factorization: an overview","volume":"67","author":"Chi","year":"2019","journal-title":"IEEE Trans. Signal Process."},{"key":"10.1016\/j.jco.2026.102056_br0070","doi-asserted-by":"crossref","first-page":"608","DOI":"10.1109\/JSTSP.2016.2539100","article-title":"An overview of low-rank matrix recovery from incomplete observations","volume":"10","author":"Davenport","year":"2016","journal-title":"IEEE J. Sel. Top. Signal Process."},{"key":"10.1016\/j.jco.2026.102056_br0370","series-title":"Elementary Number Theory, Group Theory, and Ramanujan Graphs, vol. 55","author":"Davidoff","year":"2003"},{"key":"10.1016\/j.jco.2026.102056_br0020","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevLett.105.150401","article-title":"Quantum state tomography via compressed sensing","volume":"105","author":"Gross","year":"2010","journal-title":"Phys. Rev. Lett."},{"key":"10.1016\/j.jco.2026.102056_br0110","doi-asserted-by":"crossref","first-page":"635","DOI":"10.1142\/S0219530522500130","article-title":"Compressed data separation via unconstrained l 1-split analysis","volume":"21","author":"Gu","year":"2023","journal-title":"Anal. Appl."},{"key":"10.1016\/j.jco.2026.102056_br0010","doi-asserted-by":"crossref","first-page":"1118","DOI":"10.1137\/23M1555387","article-title":"Stochastic variance reduced gradient for affine rank minimization problem","volume":"17","author":"Han","year":"2024","journal-title":"SIAM J. Imaging Sci."},{"key":"10.1016\/j.jco.2026.102056_br0250","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1002\/rsa.20483","article-title":"Deterministic algorithms for matrix completion","volume":"45","author":"Heiman","year":"2014","journal-title":"Random Struct. Algorithms"},{"key":"10.1016\/j.jco.2026.102056_br0470","author":"Hou"},{"key":"10.1016\/j.jco.2026.102056_br0460","series-title":"Int. Conf. Mach. Learn.","first-page":"1724","article-title":"How to escape saddle points efficiently","author":"Jin","year":"2017"},{"key":"10.1016\/j.jco.2026.102056_br0060","doi-asserted-by":"crossref","first-page":"2980","DOI":"10.1109\/TIT.2010.2046205","article-title":"Matrix completion from a few entries","volume":"56","author":"Keshavan","year":"2010","journal-title":"IEEE Trans. Inf. Theory"},{"key":"10.1016\/j.jco.2026.102056_br0270","first-page":"1391","article-title":"The algebraic combinatorial approach for low-rank matrix completion","volume":"16","author":"Kir\u00e1ly","year":"2015","journal-title":"J. Mach. Learn. Res."},{"key":"10.1016\/j.jco.2026.102056_br0400","doi-asserted-by":"crossref","first-page":"660","DOI":"10.1137\/18M1224738","article-title":"Nonconvex robust low-rank matrix recovery","volume":"30","author":"Li","year":"2020","journal-title":"SIAM J. Optim."},{"key":"10.1016\/j.jco.2026.102056_br0420","series-title":"Conference on Learning Theory","first-page":"2","article-title":"Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations","author":"Li","year":"2018"},{"key":"10.1016\/j.jco.2026.102056_br0100","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1016\/j.acha.2013.06.005","article-title":"Convergence of projected Landweber iteration for matrix rank minimization","volume":"36","author":"Lin","year":"2014","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"10.1016\/j.jco.2026.102056_br0240","author":"Lin"},{"key":"10.1016\/j.jco.2026.102056_br0330","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1109\/TPAMI.2019.2937869","article-title":"Matrix completion with deterministic sampling: theories and methods","volume":"43","author":"Liu","year":"2019","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"10.1016\/j.jco.2026.102056_br0030","doi-asserted-by":"crossref","first-page":"1235","DOI":"10.1137\/090755436","article-title":"Interior-point method for nuclear norm approximation with application to system identification","volume":"31","author":"Liu","year":"2010","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"10.1016\/j.jco.2026.102056_br0340","first-page":"4079","article-title":"A fast noniterative algorithm for compressive sensing using binary measurement matrices","volume":"66","author":"Lotfi","year":"2018","journal-title":"IEEE Trans. Signal Process."},{"key":"10.1016\/j.jco.2026.102056_br0350","doi-asserted-by":"crossref","first-page":"3008","DOI":"10.1109\/TSP.2020.2990154","article-title":"Compressed sensing using binary matrices of nearly optimal dimensions","volume":"68","author":"Lotfi","year":"2020","journal-title":"IEEE Trans. Signal Process."},{"key":"10.1016\/j.jco.2026.102056_br0480","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/BF02126799","article-title":"Ramanujan graphs","volume":"8","author":"Lubotzky","year":"1988","journal-title":"Combinatorica"},{"key":"10.1016\/j.jco.2026.102056_br0310","article-title":"Matrix completion from power-law distributed samples","volume":"22","author":"Meka","year":"2009","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"10.1016\/j.jco.2026.102056_br0360","first-page":"1","article-title":"Ramanujan graphs","volume":"18","author":"Murty","year":"2003","journal-title":"J. Ramanujan Math. Soc."},{"key":"10.1016\/j.jco.2026.102056_br0120","series-title":"Proc. Intl. Sympo. Information Theory (ISIT)","first-page":"2318","article-title":"A simplified approach to recovery conditions for low rank matrices","author":"Oymak","year":"2011"},{"key":"10.1016\/j.jco.2026.102056_br0280","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1109\/JSTSP.2016.2537145","article-title":"A characterization of deterministic sampling patterns for low-rank matrix completion","volume":"10","author":"Pimentel-Alarc\u00f3n","year":"2016","journal-title":"IEEE J. Sel. Top. Signal Process."},{"key":"10.1016\/j.jco.2026.102056_br0140","article-title":"A simpler approach to matrix completion","volume":"12","author":"Recht","year":"2011","journal-title":"J. Mach. Learn. Res."},{"key":"10.1016\/j.jco.2026.102056_br0210","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1137\/070697835","article-title":"Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization","volume":"52","author":"Recht","year":"2010","journal-title":"SIAM Rev."},{"key":"10.1016\/j.jco.2026.102056_br0320","article-title":"Collaborative filtering in a non-uniform world: learning with the weighted trace norm","volume":"23","author":"Srebro","year":"2010","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"10.1016\/j.jco.2026.102056_br0160","doi-asserted-by":"crossref","first-page":"6535","DOI":"10.1109\/TIT.2016.2598574","article-title":"Guaranteed matrix completion via non-convex factorization","volume":"62","author":"Sun","year":"2016","journal-title":"IEEE Trans. Inf. Theory"},{"key":"10.1016\/j.jco.2026.102056_br0430","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1016\/j.acha.2015.08.003","article-title":"Low rank matrix completion by alternating steepest descent methods","volume":"40","author":"Tanner","year":"2016","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"10.1016\/j.jco.2026.102056_br0190","article-title":"Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent","volume":"22","author":"Tong","year":"2021","journal-title":"J. Mach. Learn. Res."},{"key":"10.1016\/j.jco.2026.102056_br0390","series-title":"Int. Conf. Mach. Learn., vol. 48","first-page":"964","article-title":"Low-rank solutions of linear matrix equations via procrustes flow","author":"Tu","year":"2016"},{"key":"10.1016\/j.jco.2026.102056_br0490","series-title":"Int. Conf. Mach. Learn.","first-page":"964","article-title":"Low-rank solutions of linear matrix equations via procrustes flow","author":"Tu","year":"2016"},{"key":"10.1016\/j.jco.2026.102056_br0200","first-page":"5985","article-title":"Preconditioned gradient descent for over-parameterized nonconvex matrix factorization","volume":"34","author":"Zhang","year":"2021","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"10.1016\/j.jco.2026.102056_br0170","author":"Zheng"},{"key":"10.1016\/j.jco.2026.102056_br0080","doi-asserted-by":"crossref","first-page":"3614","DOI":"10.1109\/TSP.2018.2835403","article-title":"Global optimality in low-rank matrix optimization","volume":"66","author":"Zhu","year":"2018","journal-title":"IEEE Trans. Signal Process."}],"container-title":["Journal of Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0885064X26000415?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0885064X26000415?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,7,4]],"date-time":"2026-07-04T13:30:40Z","timestamp":1783171840000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0885064X26000415"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,10]]},"references-count":49,"alternative-id":["S0885064X26000415"],"URL":"https:\/\/doi.org\/10.1016\/j.jco.2026.102056","relation":{},"ISSN":["0885-064X"],"issn-type":[{"value":"0885-064X","type":"print"}],"subject":[],"published":{"date-parts":[[2026,10]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Nonconvex deterministic matrix completion by projected gradient descent methods","name":"articletitle","label":"Article Title"},{"value":"Journal of Complexity","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.jco.2026.102056","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.","name":"copyright","label":"Copyright"}],"article-number":"102056"}}