{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,21]],"date-time":"2025-10-21T15:27:35Z","timestamp":1761060455669,"version":"3.37.3"},"reference-count":99,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"6","license":[{"start":{"date-parts":[[2018,6,1]],"date-time":"2018-06-01T00:00:00Z","timestamp":1527811200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"},{"start":{"date-parts":[[2018,6,1]],"date-time":"2018-06-01T00:00:00Z","timestamp":1527811200000},"content-version":"am","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"},{"start":{"date-parts":[[2018,6,1]],"date-time":"2018-06-01T00:00:00Z","timestamp":1527811200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2018,6,1]],"date-time":"2018-06-01T00:00:00Z","timestamp":1527811200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF CISE Expeditions","doi-asserted-by":"publisher","award":["CCF-1139158"],"award-info":[{"award-number":["CCF-1139158"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006235","name":"LBNL","doi-asserted-by":"crossref","award":["7076018"],"award-info":[{"award-number":["7076018"]}],"id":[{"id":"10.13039\/100006235","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000185","name":"DARPA XData","doi-asserted-by":"publisher","award":["FA8750-12-2-0331"],"award-info":[{"award-number":["FA8750-12-2-0331"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100008536","name":"Amazon Web Services","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100008536","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"name":"SAP"},{"name":"The Thomas and Stacey Siebel Foundation"},{"name":"Adatao"},{"name":"Adobe"},{"name":"Apple, Inc."},{"name":"Blue Goji"},{"DOI":"10.13039\/100012884","name":"Bosch","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100012884","id-type":"DOI","asserted-by":"crossref"}]},{"name":"C3Energy"},{"name":"Cisco"},{"DOI":"10.13039\/100008297","name":"Cray","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100008297","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Cloudera"},{"name":"EMC2"},{"name":"Ericsson"},{"DOI":"10.13039\/100005801","name":"Facebook","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100005801","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Guavus"},{"name":"HP"},{"name":"Huawei"},{"name":"Informatica"},{"DOI":"10.13039\/100002418","name":"Intel","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100002418","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004318","name":"Microsoft","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004318","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NetApp"},{"name":"Pivotal"},{"DOI":"10.13039\/100004358","name":"Samsung","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004358","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Schlumberger"},{"name":"Splunk"},{"name":"Virdata"},{"name":"VMware"},{"name":"Simons Institute for the Theory of Computing"},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1217058"],"award-info":[{"award-number":["CCF-1217058"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"ONR","doi-asserted-by":"publisher","award":["N00014-11-1-0723","N00014-13-1-0129"],"award-info":[{"award-number":["N00014-11-1-0723","N00014-13-1-0129"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1148243","CCF-1217058"],"award-info":[{"award-number":["CCF-1148243","CCF-1217058"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"AFOSR","doi-asserted-by":"publisher","award":["FA9550-13-1-0138"],"award-info":[{"award-number":["FA9550-13-1-0138"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Sloan Research Fellowship"},{"DOI":"10.13039\/100005014","name":"Northrop Grumman Cybersecurity Research Consortium","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100005014","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research Young Investigator Program","doi-asserted-by":"publisher","award":["FA9550-18-1-0078"],"award-info":[{"award-number":["FA9550-18-1-0078"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006785","name":"Google Faculty Research Award","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEEE Trans. Inform. Theory"],"published-print":{"date-parts":[[2018,6]]},"DOI":"10.1109\/tit.2017.2773497","type":"journal-article","created":{"date-parts":[[2017,11,14]],"date-time":"2017-11-14T19:11:45Z","timestamp":1510686705000},"page":"4129-4158","source":"Crossref","is-referenced-by-count":35,"title":["Sharp Time\u2013Data Tradeoffs for Linear Inverse Problems"],"prefix":"10.1109","volume":"64","author":[{"given":"Samet","family":"Oymak","sequence":"first","affiliation":[]},{"given":"Benjamin","family":"Recht","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2101-6418","authenticated-orcid":false,"given":"Mahdi","family":"Soltanolkotabi","sequence":"additional","affiliation":[]}],"member":"263","reference":[{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0502269102"},{"key":"ref38","doi-asserted-by":"crossref","first-page":"9452","DOI":"10.1073\/pnas.0502258102","article-title":"Neighborliness of randomly projected simplices in high dimensions","volume":"102","author":"donoho","year":"2005","journal-title":"Proc Nat Acad Sci USA"},{"journal-title":"Accurate Prediction of Phase Transitions in Compressed Sensing Via A Connection to Minimax Denoising","year":"2011","author":"donoho","key":"ref33"},{"journal-title":"Dimensionality reduction with subgaussian matrices A unified theory","year":"2014","author":"dirksen","key":"ref32"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2007.901238"},{"key":"ref30","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1190\/1.1440378","article-title":"Robust modeling with erratic data","volume":"38","author":"claerbout","year":"1973","journal-title":"Geophysics"},{"key":"ref37","doi-asserted-by":"crossref","first-page":"18914","DOI":"10.1073\/pnas.0909892106","article-title":"Message-passing algorithms for compressed sensing","volume":"106","author":"donoho","year":"2009","journal-title":"Proc Nat Acad Sci USA"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-005-1220-0"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.871582"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1098\/rsta.2009.0152"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827596304010"},{"key":"ref27","first-page":"3252","article-title":"Structured matrix recovery via the generalized dantzig selector","author":"chen","year":"2016","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1137\/120896773"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-009-9045-5"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.885507"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.862083"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2010.5707106"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1302293110"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2008.4518498"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-012-9135-7"},{"journal-title":"Guaranteed rank minimization via singular value projection","year":"2009","author":"jain","key":"ref50"},{"key":"ref51","first-page":"685","article-title":"On iterative hard thresholding methods for high-dimensional M-estimation","author":"jain","year":"2014","journal-title":"Proc Adv Neural Inf Process Syst"},{"journal-title":"Learning without concentration","year":"2014","author":"mendelson","key":"ref59"},{"key":"ref58","first-page":"2287","article-title":"Spectral regularization algorithms for learning large incomplete matrices","volume":"11","author":"mazumder","year":"2010","journal-title":"J Mach Learn Res"},{"key":"ref57","first-page":"476","article-title":"Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima","author":"loh","year":"2013","journal-title":"Proc Adv Neural Inf Process Syst"},{"journal-title":"A geometric view on constrained M-estimators","year":"2015","author":"li","key":"ref56"},{"key":"ref55","volume":"23","author":"ledoux","year":"1991","journal-title":"Probability in banach Spaces of ergebnisse der mathematik und ihrer grenzgebiete (3)[Results in Mathematics and Related Areas (3)"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21504"},{"key":"ref53","first-page":"952","article-title":"Matrix completion from noisy entries","author":"keshavan","year":"2009","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1145\/1553374.1553434"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1109\/CISS.2006.286462"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2012.07.004"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iau005"},{"journal-title":"Universality in Polytope Phase Transitions and Message Passing Algorithms","year":"2012","author":"bayati","key":"ref6"},{"key":"ref5","first-page":"1556","article-title":"Estimation with norm regularization","author":"banerjee","year":"2014","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2174612"},{"key":"ref49","first-page":"417","article-title":"Aperture synthesis with a non-regular distribution of interferometer baselines","volume":"15","author":"hogbom","year":"1974","journal-title":"Astron Astrophys Suppl"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2094817"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1137\/080716542"},{"key":"ref46","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0081737","article-title":"On Milman’s inequality and random subspaces which escape through a mesh in \n$R^{n}$","volume":"1317","author":"gordon","year":"1988","journal-title":"Geometric Aspects of Functional Analysis"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1145\/1553374.1553417"},{"key":"ref48","first-page":"1180","article-title":"Unified view of matrix completion under general structural constraints","author":"gunasekar","year":"2015","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2104999"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1109\/JSTSP.2007.910281"},{"journal-title":"Decomposable norm minimization with proximal-gradient homotopy algorithm","year":"2015","author":"eghbali","key":"ref41"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-8176-4948-7_12"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2010.04.004"},{"journal-title":"Fast and reliable parameter estimation from nonlinear observations","year":"2016","author":"oymak","key":"ref73"},{"journal-title":"Isometric sketching of any set via the restricted isometry property","year":"2015","author":"oymak","key":"ref72"},{"journal-title":"Sharp Mse Bounds for Proximal Denoising","year":"2013","author":"oymak","key":"ref71"},{"key":"ref70","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2011.6033977"},{"journal-title":"Universality laws for randomized dimension reduction with applications","year":"2015","author":"oymak","key":"ref76"},{"journal-title":"The generalized Lasso with non-linear observations","year":"2015","author":"plan","key":"ref77"},{"journal-title":"Simple Bounds for Noisy Linear Inverse Problems with Exact Side Information","year":"2013","author":"oymak","key":"ref74"},{"journal-title":"The squarederror of generalized LASSO A precise analysis","year":"2013","author":"oymak","key":"ref75"},{"journal-title":"High-dimensional estimation with geometric constraints","year":"2014","author":"plan","key":"ref78"},{"key":"ref79","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2011.6033942"},{"key":"ref60","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-007-0618-7"},{"journal-title":"Iterative Methods in Statistical Estimation","year":"2012","author":"montanari","key":"ref62"},{"journal-title":"From denoising to compressed sensing","year":"2014","author":"metzler","key":"ref61"},{"key":"ref63","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2008.07.002"},{"key":"ref64","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-008-9031-3"},{"key":"ref65","first-page":"1348","article-title":"A unified framework for high-dimensional analysis of M-estimators with decomposable regularizers","author":"negahban","year":"2009","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref66","first-page":"372","article-title":"A method of solving a convex programming problem with convergence rate o (1\/k2)","volume":"27","author":"nesterov","year":"1983","journal-title":"Soviet Mathematics Dokl"},{"key":"ref67","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4419-8853-9","volume":"87","author":"nesterov","year":"2004","journal-title":"Introductory Lectures on Convex Optimization"},{"article-title":"Gradient methods for minimizing composite objective function","year":"2007","author":"nesterov","key":"ref68"},{"key":"ref2","first-page":"37","article-title":"Fast global convergence rates of gradient methods for high-dimensional statistical recovery","author":"agarwal","year":"2010","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref69","doi-asserted-by":"publisher","DOI":"10.1137\/040605412"},{"article-title":"Computational trade-offs in statistical learning","year":"2012","author":"agarwal","key":"ref1"},{"key":"ref95","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2009.2016018"},{"key":"ref94","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2009.2032816"},{"journal-title":"Estimation in High Dimensions A Geometric Perspective","year":"2014","author":"vershynin","key":"ref93"},{"key":"ref92","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.909108"},{"key":"ref91","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1996.tb02080.x"},{"journal-title":"The Generic Chaining Upper and Lower Bounds of Stochastic Processes","year":"2006","author":"talagrand","key":"ref90"},{"journal-title":"Does $\\ell_ p $-minimization outperform $\\ell_ 1 $-minimization?","year":"2015","author":"zheng","key":"ref98"},{"key":"ref99","doi-asserted-by":"crossref","first-page":"1013","DOI":"10.1109\/TNNLS.2012.2197412","article-title":"$L_{1\/2}$\n regularization: A thresholding representation theory and a fast solver","volume":"23","author":"xu","year":"2012","journal-title":"IEEE Trans Neural Netw Learn Syst"},{"key":"ref96","doi-asserted-by":"publisher","DOI":"10.1137\/120869997"},{"key":"ref97","doi-asserted-by":"publisher","DOI":"10.1137\/070703983"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1137\/090756855"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2009.04.002"},{"key":"ref12","first-page":"1664","article-title":"Time–data tradeoffs by aggressive smoothing","author":"bruer","year":"2014","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1109\/JSTSP.2015.2400412"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1137\/080738970"},{"journal-title":"Geometric inference for general high-dimensional linear inverse problems","year":"2014","author":"cai","key":"ref15"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-012-0540-0"},{"key":"ref82","doi-asserted-by":"publisher","DOI":"10.1137\/070697835"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2014.09.004"},{"key":"ref81","first-page":"1","article-title":"Compressive sensing and structured random matrices","volume":"9","author":"rauhut","year":"2010","journal-title":"Theoretical Foundations and Numerical Methods for Sparse Recovery"},{"journal-title":"Phase retrieval via Wirtinger flow Theory and algorithms","year":"2014","author":"cand\u00e9s","key":"ref18"},{"key":"ref84","doi-asserted-by":"publisher","DOI":"10.1109\/CISS.2006.286463"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2161794"},{"key":"ref83","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-010-0422-2"},{"key":"ref80","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2619365"},{"journal-title":"Upper-bounding $\\ell _ 1 $ -optimization weak thresholds","year":"2013","author":"stojnic","key":"ref89"},{"key":"ref85","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2008.4518502"},{"journal-title":"Various thresholds for $\\ell _ 1 $ -optimization in compressed sensing","year":"2009","author":"stojnic","key":"ref86"},{"journal-title":"A Framework to Characterize Performance of LASSO Algorithms","year":"2013","author":"stojnic","key":"ref87"},{"journal-title":"A Performance Analysis Framework for SOCP Algorithms in Noisy Compressed Sensing","year":"2013","author":"stojnic","key":"ref88"}],"container-title":["IEEE Transactions on Information Theory"],"original-title":[],"link":[{"URL":"https:\/\/ieeexplore.ieee.org\/ielaam\/18\/8361085\/8107507-aam.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/18\/8361085\/08107507.pdf?arnumber=8107507","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,8]],"date-time":"2022-04-08T18:55:16Z","timestamp":1649444116000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/8107507\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6]]},"references-count":99,"journal-issue":{"issue":"6"},"URL":"https:\/\/doi.org\/10.1109\/tit.2017.2773497","relation":{},"ISSN":["0018-9448","1557-9654"],"issn-type":[{"type":"print","value":"0018-9448"},{"type":"electronic","value":"1557-9654"}],"subject":[],"published":{"date-parts":[[2018,6]]}}}