{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,13]],"date-time":"2024-07-13T07:52:48Z","timestamp":1720857168532},"reference-count":43,"publisher":"Oxford University Press (OUP)","issue":"2","license":[{"start":{"date-parts":[[2021,1,15]],"date-time":"2021-01-15T00:00:00Z","timestamp":1610668800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,4,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider estimating a piecewise-constant image, or a gradient-sparse signal on a general graph, from noisy linear measurements. We propose and study an iterative algorithm to minimize a penalized least-squares objective, with a penalty given by the \u201c\u21130-norm\u201d of the signal\u2019s discrete graph gradient. The method uses a non-convex variant of proximal gradient descent, applying the alpha-expansion procedure to approximate the proximal mapping in each iteration, and using a geometric decay of the penalty parameter across iterations to ensure convergence. Under a cut-restricted isometry property for the measurement design, we prove global recovery guarantees for the estimated signal. For standard Gaussian designs, the required number of measurements is independent of the graph structure, and improves upon worst-case guarantees for total-variation (TV) compressed sensing on the 1-D line and 2-D lattice graphs by polynomial and logarithmic factors respectively. The method empirically yields lower mean-squared recovery error compared with TV regularization in regimes of moderate undersampling and moderate to high signal-to-noise, for several examples of changepoint signals and gradient-sparse phantom images.<\/jats:p>","DOI":"10.1111\/rssb.12407","type":"journal-article","created":{"date-parts":[[2021,1,16]],"date-time":"2021-01-16T06:32:11Z","timestamp":1610778731000},"page":"271-292","source":"Crossref","is-referenced-by-count":3,"title":["Iterative Alpha Expansion for Estimating Gradient-Sparse Signals from Linear Measurements"],"prefix":"10.1093","volume":"83","author":[{"given":"Sheng","family":"Xu","sequence":"first","affiliation":[{"name":"Department of Statistics and Data Science, Yale University , New Haven , USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhou","family":"Fan","sequence":"additional","affiliation":[{"name":"Department of Statistics and Data Science, Yale University , New Haven , USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2021,1,15]]},"reference":[{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1137\/080716542","article-title":"A fast iterative shrinkage-thresholding algorithm for linear inverse problems","volume":"2","author":"Beck","year":"2009","journal-title":"SIAM Journal on Imaging Sciences"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"813","DOI":"10.1214\/15-AOS1388","article-title":"Best subset selection via a modern optimization lens","volume":"44","author":"Bertsimas","year":"2016","journal-title":"The Annals of Statistics"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/j.acha.2009.04.002","article-title":"Iterative hard thresholding for compressed sensing","volume":"27","author":"Blumensath","year":"2009","journal-title":"Applied and Computational Harmonic Analysis"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"1124","DOI":"10.1109\/TPAMI.2004.60","article-title":"An experimental comparison of min-cut\/max-flow algorithms for energy minimization in vision","volume":"9","author":"Boykov","year":"2004","journal-title":"IEEE Transactions on Pattern Analysis & Machine Intelligence"},{"key":"2023022408370840200_","first-page":"377","volume-title":"Fast approximate energy minimization via graph cuts","author":"Boykov","year":"1999"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"1835","DOI":"10.1016\/j.jspi.2013.05.019","article-title":"Correlated variables in regression: clustering and sparse estimation","volume":"143","author":"B\u00fchlmann","year":"2013","journal-title":"Journal of Statistical Planning and Inference"},{"key":"2023022408370840200_","first-page":"328","article-title":"Guarantees of total variation minimization for signal recovery","volume":"4","author":"Cai","year":"2015","journal-title":"Information and Inference: A Journal of the IMA"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1109\/TIT.2005.862083","article-title":"Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information","volume":"52","author":"Cand\u00e8s","year":"2006","journal-title":"IEEE Transactions on Information Theory"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"1207","DOI":"10.1002\/cpa.20124","article-title":"Stable signal recovery from incomplete and inaccurate measurements","volume":"59","author":"Cand\u00e8s","year":"2006","journal-title":"Communications on Pure and Applied Mathematics"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/j.acha.2010.10.002","article-title":"Compressed sensing with coherent and redundant dictionaries","volume":"31","author":"Cand\u00e8s","year":"2011","journal-title":"Applied and Computational Harmonic Analysis"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"552","DOI":"10.3150\/15-BEJ756","article-title":"On the prediction performance of the Lasso","volume":"23","author":"Dalalyan","year":"2017","journal-title":"Bernoulli"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"1289","DOI":"10.1109\/TIT.2006.871582","article-title":"Compressed sensing","volume":"52","author":"Donoho","year":"2006","journal-title":"IEEE Transactions on Information Theory"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"947","DOI":"10.1088\/0266-5611\/23\/3\/007","article-title":"Analysis versus synthesis in signal priors","volume":"23","author":"Elad","year":"2007","journal-title":"Inverse Problems"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"3539","DOI":"10.1214\/17-AOS1679","article-title":"Restricted strong convexity implies weak submodularity","volume":"46","author":"Elenberg","year":"2018","journal-title":"The Annals of Statistics"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"3217","DOI":"10.1214\/17-AOS1656","article-title":"Approximate \u21130-penalized estimation of piecewise-constant signals on graphs","volume":"46","author":"Fan","year":"2018","journal-title":"The Annals of Statistics"},{"key":"2023022408370840200_","volume-title":"Space-alternating generalized EM algorithms for penalized maximum-likelihood image reconstruction","author":"Fessler","year":"1994"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"2612","DOI":"10.1088\/1361-6560\/aa5d40","article-title":"Low-dose dynamic myocardial perfusion CT image reconstruction using pre-contrast normal-dose CT scan induced structure tensor total variation regularization","volume":"62","author":"Gong","year":"2017","journal-title":"Physics in Medicine & Biology"},{"key":"2023022408370840200_","first-page":"1115","volume-title":"Optimal rates for total variation denoising","author":"H\u00fctter","year":"2016"},{"key":"2023022408370840200_","volume-title":"Bayesian model selection with graph structured sparsity","author":"Kim","year":"2019"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1137\/070690274","article-title":"\u21131 trend filtering","volume":"51","author":"Kim","year":"2009","journal-title":"SIAM Review"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"616","DOI":"10.1145\/585265.585268","article-title":"Approximation algorithms for classification problems with pairwise relationships: Metric labeling and markov random fields","volume":"49","author":"Kleinberg","year":"2002","journal-title":"Journal of the ACM (JACM)"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"612","DOI":"10.1109\/TIP.2013.2288004","article-title":"Stable and robust sampling strategies for compressive imaging","volume":"23","author":"Krahmer","year":"2014","journal-title":"IEEE Transactions on Image Processing"},{"key":"2023022408370840200_","first-page":"765","volume-title":"Recovering graph-structured activations using adaptive compressive measurements","author":"Krishnamuthy","year":"2013"},{"key":"2023022408370840200_","first-page":"740","volume-title":"Graph-based regularization for regression problems with highly-correlated designs","author":"Li","year":"2018"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"1182","DOI":"10.1002\/mrm.21391","article-title":"Sparse MRI: The application of compressed sensing for rapid MR imaging","volume":"58","author":"Lustig","year":"2007","journal-title":"Magnetic Resonance in Medicine: An Official Journal of the International Society for Magnetic Resonance in Medicine"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1016\/j.acha.2012.03.006","article-title":"The cosparse analysis model and algorithms","volume":"34","author":"Nam","year":"2013","journal-title":"Applied and Computational Harmonic Analysis"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/j.acha.2008.07.002","article-title":"CoSaMP: Iterative signal recovery from incomplete and inaccurate samples","volume":"26","author":"Needell","year":"2009","journal-title":"Applied and Computational Harmonic Analysis"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"3941","DOI":"10.1109\/TIP.2013.2264681","article-title":"Near-optimal compressed sensing guarantees for total variation minimization","volume":"22","author":"Needell","year":"2013","journal-title":"IEEE Transactions on Image Processing"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"1035","DOI":"10.1137\/120868281","article-title":"Stable image reconstruction using total variation minimization","volume":"6","author":"Needell","year":"2013","journal-title":"SIAM Journal on Imaging Sciences"},{"key":"2023022408370840200_","first-page":"6410","article-title":"The dfs fused lasso: Linear-time denoising over general graphs","volume":"18","author":"Padilla","year":"2017","journal-title":"The Journal of Machine Learning Research"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1561\/2400000003","article-title":"Proximal algorithms","volume":"1","author":"Parikh","year":"2014","journal-title":"Foundations and Trends\u00ae in Optimization"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"2922","DOI":"10.1214\/08-AOS665","article-title":"Properties and refinements of the fused lasso","volume":"37","author":"Rinaldo","year":"2009","journal-title":"The Annals of Statistics"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"1025","DOI":"10.1002\/cpa.20227","article-title":"On sparse reconstruction from Fourier and Gaussian measurements","volume":"61","author":"Rudelson","year":"2008","journal-title":"Communications on Pure and Applied Mathematics"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/0167-2789(92)90242-F","article-title":"Nonlinear total variation based noise removal algorithms","volume":"60","author":"Rudin","year":"1992","journal-title":"Physica D: Nonlinear Phenomena"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"4902","DOI":"10.1118\/1.3480985","article-title":"4D XCAT phantom for multimodality imaging research","volume":"37","author":"Segars","year":"2010","journal-title":"Medical Physics"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","DOI":"10.1214\/11-AOS878","volume-title":"The solution path of the generalized lasso","author":"Tibshirani","year":"2011"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1111\/j.1467-9868.2005.00490.x","article-title":"Sparsity and smoothness via the fused lasso","volume":"67","author":"Tibshirani","year":"2005","journal-title":"Journal of the Royal Statistical Society: Series B (Statistical Methodology)"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"4655","DOI":"10.1109\/TIT.2007.909108","article-title":"Signal recovery from random measurements via orthogonal matching pursuit","volume":"53","author":"Tropp","year":"2007","journal-title":"IEEE Transactions on Information Theory"},{"key":"2023022408370840200_","first-page":"3651","article-title":"Trend filtering on graphs","volume":"17","author":"Wang","year":"2016","journal-title":"The Journal of Machine Learning Research"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"1062","DOI":"10.1137\/120869997","article-title":"A proximal-gradient homotopy method for the sparse least-squares problem","volume":"23","author":"Xiao","year":"2013","journal-title":"SIAM Journal on Optimization"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1145\/2070781.2024208","article-title":"Image smoothing via l0 gradient minimization","volume":"30","author":"Xu","year":"2011","journal-title":"ACM Transactions on Graphics (TOG)"},{"key":"2023022408370840200_","doi-asserted-by":"crossref","first-page":"6215","DOI":"10.1109\/TIT.2011.2162263","article-title":"Sparse recovery with orthogonal matching pursuit under RIP","volume":"57","author":"Zhang","year":"2011","journal-title":"IEEE Transactions on Information Theory"},{"key":"2023022408370840200_","first-page":"921","volume-title":"Lower bounds on the performance of polynomial-time algorithms for sparse linear regression","author":"Zhang","year":"2014"}],"container-title":["Journal of the Royal Statistical Society Series B: Statistical Methodology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1111\/rssb.12407","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1111\/rssb.12407","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/academic.oup.com\/jrsssb\/article-pdf\/83\/2\/271\/49320858\/jrsssb_83_2_271.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/jrsssb\/article-pdf\/83\/2\/271\/49320858\/jrsssb_83_2_271.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,17]],"date-time":"2023-10-17T21:24:04Z","timestamp":1697577844000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/jrsssb\/article\/83\/2\/271\/7056035"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,15]]},"references-count":43,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2021,1,15]]},"published-print":{"date-parts":[[2021,4,1]]}},"URL":"https:\/\/doi.org\/10.1111\/rssb.12407","relation":{},"ISSN":["1369-7412","1467-9868"],"issn-type":[{"value":"1369-7412","type":"print"},{"value":"1467-9868","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,4]]},"published":{"date-parts":[[2021,1,15]]}}}