{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T13:07:38Z","timestamp":1790773658237,"version":"4.1.0"},"reference-count":49,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"name":"Hong Kong Research Grant Council","award":["16300616"],"award-info":[{"award-number":["16300616"]}]},{"name":"Hong Kong Research Grant Council","award":["16306317"],"award-info":[{"award-number":["16306317"]}]},{"name":"Shanghai Sailing Program","award":["18YF1401600"],"award-info":[{"award-number":["18YF1401600"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>Let $x\\in\\mathbb{C}^n$ be a spectrally sparse signal consisting of $r$ complex sinusoids with or without damping. We consider the spectral compressed sensing problem, which concerns reconstructing $x$ from its partially revealed entries. By utilizing the low rank structure of the Hankel matrix corresponding to $x$, we develop a computationally efficient algorithm for this problem. The algorithm starts from an initial guess computed via one-step hard thresholding followed by projection, and then proceeds by applying projected gradient descent iterations to a nonconvex functional. Based on the sampling with replacement model, we prove that $O(r^2\\log(n))$ observed entries are sufficient for our algorithm to achieve the successful recovery of a spectrally sparse signal. Moreover, extensive empirical performance comparisons show that our algorithm is competitive with other state-of-the-art spectral compressed sensing algorithms in terms of phase transitions and overall computational time.<\/jats:p>","DOI":"10.1137\/17m1141394","type":"journal-article","created":{"date-parts":[[2018,9,20]],"date-time":"2018-09-20T10:06:42Z","timestamp":1537438002000},"page":"2625-2653","source":"Crossref","is-referenced-by-count":55,"title":["Spectral Compressed Sensing via Projected Gradient Descent"],"prefix":"10.1137","volume":"28","author":[{"given":"Jian-Feng","family":"Cai","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tianming","family":"Wang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ke","family":"Wei","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,9,20]]},"reference":[{"key":"atypb1","unstructured":"S. Bhojanapalli, B. Neyshabur, and N. Srebro,\n                      Global Optimality of Local Search for Low Rank Matrix Recovery\n                      , preprint,https:\/\/arxiv.org\/abs\/1605.07221, 2016."},{"key":"atypb2","first-page":"289","volume":"4","author":"Blanchard J.","year":"2015","journal-title":"Inf. Inference"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2014.2379665"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2009.04.002"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1109\/JSTSP.2010.2042411"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"J.F. Cai, S. Liu, and W. Xu,\n                      A fast algorithm for reconstruction of spectrally sparse signals in super-resolution\n                      , in Wavelets and Sparsity XVI, Proc. SPIE Opt. Eng. Appl. 9597, Society of Photo-optical Instrumentation Engineers, Bellingham, WA, 2015, 95970A.","DOI":"10.1117\/12.2188489"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2016.02.003"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"J.F. Cai, T. Wang, and K. Wei,\n                      Fast and provable algorithms for spectrally sparse signal reconstruction via low-rank Hankel matrix completion\n                      , Appl. Comput. Harmon. Anal. (2017),https:\/\/doi.org\/10.1016\/j.acha.2017.04.004.","DOI":"10.1117\/12.2272919"},{"key":"atypb9","unstructured":"J.F. Cai, T. Wang, and K. Wei,\n                      Supplementary Material for \u201cSpectral Compressed Sensing via Projected Gradient Descent,''\n                      http:\/\/www.sdspeople.fudan.edu.cn\/weike\/docs\/PGD_supp.pdf, 2017."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2399924"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-009-9045-5"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.862083"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450037906X"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21638"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2343623"},{"key":"atypb16","unstructured":"Y. Chen and M. J. Wainwright,\n                      Fast Low-Rank Estimation by Projected Gradient Descent: General Statistical and Algorithmic Guarantees\n                      , preprint,https:\/\/arxiv.org\/abs\/1509.03025, 2015."},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2011.2112650"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2009.2016006"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.871582"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/110853996"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20089"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1137\/100806278"},{"key":"atypb23","unstructured":"R. Ge, F. Huang, C. Jin, and Y. Yuan,\n                      Escaping From Saddle Points-Online Stochastic Gradient for Tensor Decomposition\n                      , preprint,https:\/\/arxiv.org\/abs\/1503.02101, 2015."},{"key":"atypb24","unstructured":"R. Ge, C. Jin, and Y. Zhang,\n                      No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis\n                      , preprint,https:\/\/arxiv.org\/abs\/1704.00708, 2017."},{"key":"atypb25","first-page":"2973","author":"Ge R.","year":"2016","journal-title":"NY"},{"key":"atypb26","unstructured":"M. Grant and S. Boyd,\n                      CVX: Matlab Software for Disciplined Convex Programming, Version \u016dshape2.1\n                      ,http:\/\/cvxr.com\/cvx(March 2014)."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1109\/JSTSP.2009.2039170"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2046205"},{"key":"atypb29","unstructured":"R. Larsen,\n                      PROPACK-Software for Large and Sparse SVD Calculations, Version \u016dshape2.1\n                      ,http:\/\/sun.stanford.edu\/~rmunk\/PROPACK(April 2005)."},{"key":"atypb30","unstructured":"X. Li, S. Ling, T. Strohmer, and K. Wei,\n                      Rapid, Robust, and Reliable Blind Deconvolution via Nonconvex Optimization\n                      , preprint,https:\/\/arxiv.org\/abs\/1606.04933, 2016."},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2014.12.003"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1002\/mrm.21391"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1007\/BF01647331"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2008.07.002"},{"key":"atypb35","unstructured":"D. Park, A. Kyrillidis, C. Caramanis, and S. Sanghavi,\n                      Non-Square Matrix Sensing Without Spurious Local Minima via the Burer-Monteiro Approach\n                      , preprint,https:\/\/arxiv.org\/abs\/1609.03240, 2016."},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2009.2037526"},{"key":"atypb37","first-page":"852","volume":"54","author":"Qu X.","year":"2015","journal-title":"Ed.)"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1083\/jcb.201002018"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2632162"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2277451"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-011-9099-z"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2009.2034811"},{"key":"atypb44","unstructured":"S. Tu, R. Boczar, M. Simchowitz, M. Soltanolkotabi, and B. Recht,\n                      Low-Rank Solutions of Linear Matrix Equations via Procrustes Flow\n                      , preprint,https:\/\/arxiv.org\/abs\/1507.03566, 2015."},{"key":"atypb45","unstructured":"K. Wei, J. F. Cai, T. F. Chan, and S. Leung,\n                      Guarantees of Riemannian Optimization for Low Rank Matrix Completion\n                      , preprint,https:\/\/arxiv.org\/abs\/1603.06610, 2016."},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1137\/15M1050525"},{"key":"atypb47","unstructured":"X. Yi, D. Park, Y. Chen, and C. Caramanis,\n                      Fast Algorithms for Robust PCA via Gradient Descent\n                      , preprint,https:\/\/arxiv.org\/abs\/1605.07784, 2016."},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2017.2695566"},{"key":"atypb49","unstructured":"Q. Zheng and J. Lafferty,\n                      A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements\n                      , preprint,https:\/\/arxiv.org\/abs\/1506.06081, 2015."},{"key":"atypb50","unstructured":"Q. Zheng and J. Lafferty,\n                      Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent\n                      , preprint,https:\/\/arxiv.org\/abs\/1605.07051, 2016."}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1141394","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:19:38Z","timestamp":1787339978000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1141394"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":49,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1141394"],"URL":"https:\/\/doi.org\/10.1137\/17m1141394","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}