×

A fast homotopy algorithm for gridless sparse recovery. (English) Zbl 1460.94005

Summary: In this paper, we study the solving of the gridless sparse optimization problem and its application to 3D image deconvolution. Based on the recent works of Q. Denoyelle et al. [ibid. 36, No. 1, Article ID 014001, 42 p. (2020; Zbl 1434.65082)] introducing the sliding Frank-Wolfe algorithm to solve the Beurling LASSO problem, we introduce an accelerated algorithm, denoted BSFW, that preserves its convergence properties, while removing most of the costly local descents. Besides, as the solving of BLASSO still relies on a regularization parameter, we introduce a homotopy algorithm to solve the constrained BLASSO that allows to use a more practical parameter based on the image residual, e.g. its standard deviation. Both algorithms benefit from a finite termination property, i.e. they are guaranteed to find the solution in a finite number of step under mild conditions. These methods are then applied on the problem of 3D tomographic diffractive microscopy images, with the purpose of explaining the image by a small number of atoms in convolved observations. Numerical results on synthetic and real images illustrates the improvement provided by the BSFW method, the homotopy method and their combination.

MSC:

94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
62J07 Ridge regression; shrinkage estimators (Lasso)
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
65K10 Numerical optimization and variational techniques
90C25 Convex programming

Citations:

Zbl 1434.65082

Software:

SPGL1; LBFGS-B
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Asif M S and Romberg J 2014 Sparse recovery of streaming signals using IEEE Trans. Signal Process.62 4209-23
[2] Azais J-M, De Castro Y and Gamboa F 2015 Spike detection from inaccurate samplings Appl. Comput. Harmon. Anal.38 177-95
[3] Babcock H P, Moffitt J R, Cao Y and Zhuang X 2013 Fast compressed sensing analysis for super-resolution imaging using l1-homotopy Opt. Express21 28583-96
[4] Barbero A and Sra S 2018 Modular proximal optimization for multidimensional total-variation regularization J. Mach. Learn. Res.19 2232-313
[5] Beck A and Teboulle M 2009 A fast iterative shrinkage-thresholding algorithm for linear inverse problems SIAM J. Imaging Sci.2 183-202
[6] Beck A and Teboulle M 2009 Gradient-based algorithms with applications to signal recovery Convex Optimization in Signal Processing and Communications (Cambridge: Cambridge University Press) pp 42-88
[7] Boyd N, Schiebinger G and Recht B 2017 The alternating descent conditional gradient method for sparse inverse problems SIAM J. Optim.27 616-39
[8] Bredies K and Pikkarainen H K 2013 Inverse problems in spaces of measures ESAIM: Control Opt. Calculus Var.19 190-218
[9] Byrd R H, Lu P, Nocedal J and Zhu C 1995 A limited memory algorithm for bound constrained optimization SIAM J. Sci. Comput.16 1190-208
[10] Candès E J and Fernandez-Granda C 2014 Towards a mathematical theory of super-resolution Commun. Pure Appl. Math.67 906-56
[11] Courbot J-B and Colicchio B 2020 Boosting the sliding Frank-Wolfe solver for 3D deconvolution iTWIST 2020: International-Traveling Workshop on Interactions between Sparse Models and Technology
[12] Courbot J-B, Duval V and Legras B 2020 Sparse analysis for mesoscale convective systems tracking Signal Process.: Image Commun.85 115854
[13] De Castro Y and Gamboa F 2012 Exact reconstruction using Beurling minimal extrapolation J. Math. Anal. Appl.395 336-54
[14] Denoyelle Q, Duval V, Peyré G and Soubies E 2019 The sliding Frank-Wolfe algorithm and its application to super-resolution microscopy Inverse Problems36 014001
[15] Donoho D L and Tsaig Y 2008 Fast solution of l1-norm minimization problems when the solution may be sparse IEEE Trans. Inf. Theory54 4789-812
[16] Dünner C, Forte S, Takác M and Jaggi M 2016 Primal-dual rates and certificates Proc. 33rd Int. Conf. Machine Learning, ICML 783-92
[17] Duval V and Peyré G 2015 Exact support recovery for sparse spikes deconvolution Found. Comput. Math.15 1315-55
[18] Ekanadham C, Tranchina D and Simoncelli E P 2011 Recovery of sparse translation-invariant signals with continuous basis pursuit IEEE Trans. Signal Process.59 4735-44
[19] Hale E T, Yin W and Zhang Y 2007 A fixed-point continuation method for L1-regularized minimization with applications to compressed sensing CAAM TR07-07vol 43 p 44
[20] Johnston P R and Gulrajani R M 2000 Selecting the corner in the L-curve approach to Tikhonov regularization IEEE Trans. Biomed. Eng.47 1293-6
[21] Krauze W, Makowski P, Kujawińska M and Kuś A 2016 Generalized total variation iterative constraint strategy in limited angle optical diffraction tomography Opt. Express24 4924-36
[22] Lim J, Ayoub A B, Antoine E E and Psaltis D 2019 High-fidelity optical diffraction tomography of multiple scattering samples Light: Sci. Appl.8 1-12
[23] Mairal J and Yu B 2012 Complexity analysis of the lasso regularization path Proc. 29th Int. Conf. Machine Learning (ICML 2012)
[24] Nocedal J and Wright S 2006 Numerical Optimization (Berlin: Springer)
[25] Osborne M R, Presnell B and Turlach B A 2000 A new approach to variable selection in least squares problems IMA J. Numer. Anal.20 389-403
[26] Osborne M R, Presnell B and Turlach B A 2000 On the lasso and its dual J. Comput. Graph. Stat.9 319-37
[27] Parikh N and Boyd S 2014 Proximal algorithms Found. Trends Opt.1 127-239
[28] Park C, Shin S and Park Y 2018 Generalized quantification of three-dimensional resolution in optical diffraction tomography using the projection of maximal spatial bandwidths J. Opt. Soc. Am. A 35 1891-8
[29] Simon B and Haeberlé O 2019 Tomographic diffractive microscopy: principles, implementations, and applications in biology Label-Free Super-Resolution Microscopy (Berlin: Springer) pp 85-112
[30] Soussen C, Idier J, Duan J and Brie D 2015 Homotopy based algorithms for 10-regularized least-squares IEEE Trans. Signal Process.63 3301-16
[31] Tang G, Bhaskar B N, Shah P and Recht B 2013 Compressed sensing off the grid IEEE Trans. Inf. Theory59 7465-90
[32] Van Den Berg E and Friedlander M P 2009 Probing the Pareto frontier for basis pursuit solutions SIAM J. Sci. Comput.31 890-912
[33] Vandenberghe L 2010 Fast proximal gradient methods 236 EE236C course notes online www.seas.ucla.edu/vandenbeC
[34] Xiao L and Zhang T 2013 A proximal-gradient homotopy method for the sparse least-squares problem SIAM J. Optim.23 1062-91
[35] Zhang L, Yang T, Jin R and Zhou Z-H 2015 A simple homotopy algorithm for compressive sensing Artificial Intelligence and Statistics pp 1116-24
[36] Zhao Y-B 2018 Sparse Optimization Theory and Methods (Boca Raton, FL: CRC Press)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.