{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,7]],"date-time":"2026-07-07T20:14:34Z","timestamp":1783455274751,"version":"3.55.0"},"reference-count":55,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["NSF DMS-2023239"],"award-info":[{"award-number":["NSF DMS-2023239"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["OCENW.GROOT.2019.015"],"award-info":[{"award-number":["OCENW.GROOT.2019.015"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2026,9,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We study a sample complexity vs.\u00a0conditioning tradeoff in modern signal recovery problems (including sparse recovery, low-rank matrix sensing, covariance estimation, and abstract phase retrieval), where convex optimization problems are built from sampled observations. We begin by introducing a set of condition numbers related to sharpness in the [Formula: see text] or Schatten-1 norm of nonsmooth formulations for these problems. Then, we show that these condition numbers become dimension- independent constants in each of the example signal recovery problems once the sample size exceeds some constant multiple of the recovery threshold.\u00a0Structurally, this result ensures that the inaccuracy in the recovered signal due to both observation noise and optimization error is controlled. Algorithmically, such a result ensures that a new restarted mirror descent method achieves nearly dimension-independent linear convergence to the signal in terms of iterations. This new first-order method is general and applies to any sharp convex function in an [Formula: see text] or Schatten-[Formula: see text] norm for [Formula: see text].<\/jats:p>","DOI":"10.1137\/24m1678891","type":"journal-article","created":{"date-parts":[[2026,7,7]],"date-time":"2026-07-07T07:01:47Z","timestamp":1783407707000},"page":"1269-1296","source":"Crossref","is-referenced-by-count":0,"title":["Sharpness and Conditioning of Nonsmooth Convex Formulations in Statistical Signal Recovery"],"prefix":"10.1137","volume":"36","author":[{"given":"Lijun","family":"Ding","sequence":"first","affiliation":[{"name":"Department of Mathematics, University of California San Diego, La Jolla, CA 92093 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4293-0359","authenticated-orcid":true,"given":"Alex L.","family":"Wang","sequence":"additional","affiliation":[{"name":"Daniels School of Business, Purdue University, West Lafayette, IN 47907 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2026,7,7]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614432"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0449"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-55925-9_18"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s00365-007-9003-x"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s101070050083"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/asr043"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-1091-6"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1561\/2200000050"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1214\/14-AOS1267"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-013-9162-z"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2014.09.004"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2111771"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.20124"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21432"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.858979"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2044061"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-012-9135-7"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-020-09490-9"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iaaa027"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2429594"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-018-1372-8"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-022-01942-1"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1137\/15M1020770"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2017.0889"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1311-3"},{"key":"ref26","first-page":"471","volume":"8","author":"Duchi J. C.","year":"2019","journal-title":"Inf. Inference"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1137\/0609045"},{"key":"ref28","first-page":"994","volume-title":"Doklady Akademii Nauk 160","author":"Eremin I. I.","year":"1965"},{"key":"ref29","volume-title":"Advances in Neural Information Processing Systems 32","author":"Fan J.","year":"2019"},{"key":"ref30","unstructured":"M. C. Ferris, Weak Sharp Minima and Exact Penalty Functions, Technical report, University of Wisconsin-Madison Department of Computer Sciences, 1988, https:\/\/ftp.cs.wisc.edu\/pub\/techreports\/1988\/TR779.pdf."},{"key":"ref31","first-page":"1811","volume":"48","author":"Garber D.","year":"2022","journal-title":"Math. Oper. Res."},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584346"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1142\/9789812796936_0018"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-01361-0"},{"key":"ref35","unstructured":"A. S. Lewis, Nonsmooth optimization:\u00a0Conditioning, convergence and semi-algebraic models, in Proceedings of the International Congress of Mathematicians, Vol. 4, Seoul, 2014, pp. 872\u2013895."},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1137\/18M1224738"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1007\/s101070050070"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1232-1"},{"key":"ref39","first-page":"356","volume":"25","author":"Nemirovski A. S.","year":"1985","journal-title":"Zhurnal Vychislitel\u2019noi Matematiki i Matematicheskoi Fiziki"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1017\/S096249291300007X"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-013-9561-6"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(69)90061-5"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1214\/ss\/1030037960"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1137\/070697835"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-021-09502-2"},{"key":"ref46","series-title":"Princeton Landmarks in Mathematics and Physics 11","volume-title":"Convex Analysis","author":"Rockafellar R. T.","year":"1997"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iay020"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1137\/18M1224568"},{"key":"ref49","doi-asserted-by":"crossref","unstructured":"M. Rudelson and R. Vershynin, Sparse reconstruction by convex relaxation:\u00a0Fourier and gaussian measurements, in Proceedings of the 2006 40th Annual Conference on Information Sciences and Systems, IEEE, 2006, pp. 207\u2013212.","DOI":"10.1109\/CISS.2006.286463"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2017.2748590"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623498338606"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511794308.006"},{"key":"ref53","first-page":"236","volume":"19","author":"Yang T.","year":"2018","journal-title":"J. Mach. Learn. Res."},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1137\/S105262349834429X"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-1100-9"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,7,7]],"date-time":"2026-07-07T19:33:03Z","timestamp":1783452783000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1678891"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,7]]},"references-count":55,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,9,30]]}},"alternative-id":["10.1137\/24M1678891"],"URL":"https:\/\/doi.org\/10.1137\/24m1678891","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,7]]}}}