×

The alternating descent conditional gradient method for sparse inverse problems. (English) Zbl 1365.90195

Summary: We propose a variant of the classical conditional gradient method for sparse inverse problems with differentiable observation models. Such models arise in many practical problems including superresolution microscopy, time-series modeling, and matrix completion. Our algorithm combines nonconvex and convex optimization techniques: we propose global conditional gradient steps alternating with nonconvex local search exploiting the differentiable observation model. This hybridization gives the theoretical global optimality guarantees and stopping conditions of convex optimization along with the performance and modeling flexibility associated with nonconvex optimization. Our experiments demonstrate that our technique achieves state-of-the-art results in several applications.

MSC:

90C25 Convex programming
90C30 Nonlinear programming
90C34 Semi-infinite programming
90C49 Extreme-point and pivoting methods
90C52 Methods of reduced gradient type
90C90 Applications of mathematical programming
49M37 Numerical methods based on nonlinear programming
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] A. Agarwal, A. Anandkumar, P. Jain, and P. Netrapalli, {\it Learning sparsely used overcomplete dictionaries via alternating minimization}, SIAM J. Optim., 26 (2016), pp. 2775-2799. · Zbl 1358.90104
[2] S. Arora, R. Ge, T. Ma, and A. Moitra, {\it Simple, Efficient, and Neural Algorithms for Sparse Coding}, preprint, arXiv:1503.00778, 2015.
[3] D. Arthur and S. Vassilvitskii, {\it k-means++: The advantages of careful seeding}, in Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2007, pp. 1027-1035. · Zbl 1302.68273
[4] F. Bach, {\it Convex relaxations of structured matrix factorizations}, arXiv:1309.3117, 2013, pp. 1355-1362.
[5] F. Bach, S. Lacoste-Julien, and G. Obozinski, {\it On the equivalence between herding and conditional gradient algorithms}, in ICML, Omnipress, Madison, WI, 2012, pp. 1355-1362.
[6] W. Bajwa, J. Haupt, A. Sayeed, and R. Nowak., {\it Compressed channel sensing: A new approach to estimating sparse multipath channels}, Proc. IEEE, 98 (2010), pp. 1058-1076.
[7] R. Baraniuk and P. Steeghs., {\it Compressive radar imaging}, In IEEE Radar Conference, Waltham, MA, IEEE, Piscataway, NJ, 2007, pp. 128-133.
[8] K. Bredies and H. K. Pikkarainen, {\it Inverse problems in spaces of measures}, ESAIM Control Optim. Calc. Var., 19 (2013), pp. 190-218, . · Zbl 1266.65083
[9] S. Burer and R. D. Monteiro, {\it A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization}, Math. Program., 95 (2003), pp. 329-357, . · Zbl 1030.90077
[10] E. Candes and C. Fernandez-Granda., {\it Towards a mathematical theory of super resolution}, Comm. Pure Appl. Math, 67 (2014), pp. 906-956. · Zbl 1350.94011
[11] E. Candès and B. Recht, {\it Exact matrix completion via convex optimization}, Commun. ACM, 55 (2012), pp. 111-119. · Zbl 1219.90124
[12] V. Chandrasekaran, B. Recht, P. A. Parrilo, and A. S. Willsky, {\it The convex geometry of linear inverse problems}, Found. Comput. Math., 12 (2012), pp. 805-849. · Zbl 1280.52008
[13] B. L. R. De Moor, ed., {\it DaISy}, .
[14] B. G. R. de Prony, {\it Essai experimental et analytique: Sur les lois de la dilatabilite de fluides elastique et sur celles de la force expansive de la vapeur de l’alkool, a differentes temperatures}, J. Éc. Polytech., 1 (1795), pp. 24-76.
[15] V. Demyanov and A. Rubinov, {\it Approximate methods in optimization problems}, in Modern Analytic and Computational Methods in Science and Mathematics, Elsevier, New York, 1970.
[16] M. Duarte and R. Baraniuk, {\it Spectral compressive sensing}, Appl. Comput. Harmon. Anal., 35 (2013), pp. 111-129. · Zbl 1336.94016
[17] N. Dunford, J. T. Schwartz, W. G. Bade, and R. G. Bartle, {\it Linear Operators, Part} 1, Wiley-interscience New York, 1958. · Zbl 0146.12601
[18] J. Dunn and S. Harshbarger, {\it Conditional gradient algorithms with open loop step size rules}, J. Math. Anal. Appl., 62 (1978), pp. 432-444. · Zbl 0374.49017
[19] C. Ekanadham, D. Tranchina, and E. P. Simoncelli, {\it Neural spike identifcation with continuous basis pursuit}, Computational and Systems Neuroscience (CoSyNe), Salt Lake City, Utah, 2011. · Zbl 1392.94192
[20] D. Evanko, {\it Primer: Fluorescence imaging under the diffraction limit}, Nature Methods, 6 (2009), pp. 19-20.
[21] A. C. Fannjiang, T. Strohmer, and P. Yan, {\it Compressed remote sensing of sparse objects}, SIAM J. Imaging Sci., 3 (2010), pp. 595-618. · Zbl 1201.45017
[22] G. B. Folland, {\it Real Analysis}, Wiley, New York, 1999. · Zbl 0924.28001
[23] B. I. Group, {\it Single-Molecule Localization Microscopy Benchworking Software}, (2013).
[24] A. Hansson, Z. Liu, and L. Vandenberghe, {\it Subspace System Identification via Weighted Nuclear Norm Optimization}, preprint, arXiv:1207.0023, 2012.
[25] Z. Harchaoui, A. Juditsky, and A. Nemirovski, {\it Conditional gradient algorithms for norm-regularized smooth convex optimization}, Math. Program., 152 (2014), pp. 75-112. · Zbl 1336.90069
[26] M. Herman and T. Strohmer, {\it High-resolution radar via compressed sensing}, IEEE Trans. Signal Process., 57 (2009), pp. 2275-2284. · Zbl 1391.94236
[27] R. Hettich and K. O. Kortanek, {\it Semi-infinite programming: Theory, methods, and applications}, SIAM Rev., 35 (1993), pp. 380-429. · Zbl 0784.90090
[28] H. Hindi, {\it A tutorial on optimization methods for cancer radiation treatment planning}, in American Control Conference (ACC), IEEE, Piscataway, NJ, 2013, pp. 6804-6816, .
[29] M. Jaggi, {\it Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization}, in ICML, 2013, Curran, Red Hook, NY, pp. I-427-I-435.
[30] M. Jaggi and M. Sulovský, {\it A simple algorithm for nuclear norm regularized problems}, in Proceedings of the 27th International Conference on Machine Learning (ICML-10), Omnipress, Madison, WI, 2010, pp. 471-478.
[31] P. Jain, P. Netrapalli, and S. Sanghavi, {\it Low-rank matrix completion using alternating minimization}, in Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, ACM, New York, 2013, pp. 665-674. · Zbl 1293.65073
[32] S. G. Johnson, {\it NLopt}, (2011).
[33] R. H. Keshavan, {\it Efficient Algorithms for Collaborative Filtering}, Ph.D. thesis, Stanford University, Palo Alto, CA, 2012.
[34] D. Koller and N. Friedman, {\it Probabilistic Graphical Models: Principles and Techniques - Adaptive Computation and Machine Learning}, The MIT Press, Cambridge, MA, 2009.
[35] S. Lacoste-Julien, F. Lindsten, and F. Bach, {\it Sequential kernel herding: Frank-Wolfe optimization for particle filtering}, J. Mach. Learn. Res. W&CP, 38 (2015), pp. 544-552.
[36] S. Laue, {\it A hybrid algorithm for convex semidefinite optimization}, in Proceedings of the 29th International Conference on Machine Learning (ICML-12), J. Langford and J. Pineau, eds., New York, 2012, Omnipress, Madison, WI, 2012, pp. 177-184.
[37] H.-Y. Liu, E. Jonas, L. Tian, J. Zhong, B. Recht, and L. Waller, {\it \(3\) d imaging in volumetric scattering media using phase-space measurements}, Opt. Express, 23 (2015), pp. 14461-14471, .
[38] D. Malioutov, M. Çetin, and A. S. Willsky, {\it A sparse signal reconstruction perspective for source localization with sensor arrays}, IEEE Trans. Signal Process., 53 (2005), pp. 3010-3022. · Zbl 1370.94191
[39] P. Netrapalli, P. Jain, and S. Sanghavi, {\it Phase retrieval using alternating minimization}, in Advances in Neural Information Processing Systems, 26 (2013), pp. 2796-2804. · Zbl 1293.65073
[40] R. Ostrovsky, Y. Rabani, L. J. Schulman, and C. Swamy, {\it The effectiveness of \(L\) loyd-type methods for the \(k\)-means problem}, J. ACM, 59 (2012), 28. · Zbl 1281.68229
[41] F. Pukelsheim, {\it Optimal Design of Experiments}, Classics Appl. Math. 50, SIAM, Philadelphia, 2006. · Zbl 1101.62063
[42] K. G. Puschmann and F. Kneer, {\it On super-resolution in astronomical imaging}, Astron. Astrophys., 436 (2005), pp. 373-378.
[43] N. Rao, P. Shah, and S. Wright, {\it Forward-Backward Greedy Algorithms for Atomic Norm Regularization}, prprint, arXiv:1404.5692, 2014. · Zbl 1394.94471
[44] H. Rauhut, {\it Random sampling of sparse trigonometric polynomials}, Appl. Comput. Harmon. Anal., 22 (2007), pp. 16-42. · Zbl 1123.94004
[45] B. Recht and C. Ré, {\it Parallel stochastic gradient algorithms for large-scale matrix completion}, Math. Program. Comput., 5 (2013), pp. 201-226. · Zbl 1275.90039
[46] R. T. Rockafellar, {\it Convex Analysis}, Princeton University Press, Princeton, NJ, 1970. · Zbl 0193.18401
[47] M. Rust, M. Bates, and X. Zhuang, {\it Sub-diffraction-limit imaging by stochastic optical reconstruction microscopy (storm)}, Nature Methods, 3 (2006), pp. 793-796.
[48] D. Sage, H. Kirshner, T. Pengo, N. Stuurman, J. Min, S. Manley, and M. Unser, {\it Quantitative evaluation of software packages for single-molecule localization microscopy}, Nature Methods, 12 (2015), pp. 717-724, .
[49] P. Shah, B. Bhaskar, G. Tang, and B. Recht, {\it Linear System Identification via Atomic Norm Regularization}, preprint, arXiv:1204.0590, 2012.
[50] A. Shapiro, {\it Semi-infinite programming, duality, discretization and optimality conditions}, Optimization, 58 (2009), pp. 133-161. · Zbl 1158.90410
[51] J. Skaf and S. Boyd, {\it Techniques for exploring the suboptimal set}, Optim. Eng., 11 (2010), pp. 319-337. · Zbl 1273.65089
[52] G. Tang, B. Bhaskar, and B. Recht, {\it Sparse recovery over continuous dictionaries: Just discretize}, in 2013 Asilomar Conference on Signals, Systems, and Computers, IEEE, Piscataway, NJ, 2013, pp. 1043-1047.
[53] G. Tang, B. N. Bhaskar, P. Shah, and B. Recht, {\it Compressed sensing off the grid}, IEEE Trans. Inform. Theory, 59 (2013), pp. 7465-7490. · Zbl 1364.94168
[54] R. J. Tibshirani, {\it A general framework for fast stagewise algorithms}, J. Mach. Learn. Res., 16 (2015), pp. 2543-2588. · Zbl 1351.62141
[55] E. van den Berg and M. P. Friedlander, {\it Sparse optimization with least-squares constraints}, SIAM J. Optim., 21 (2011), pp. 1201-1229. · Zbl 1242.49061
[56] X. Zhang, Y. Yu, and D. Schuurmans, {\it Accelerated training for matrix-norm regularization: A boosting approach}, in Advances in Neural Information Processing Systems 25, 2012, pp. 2906-2914.
[57] L. Zhu, W. Zhang, D. Elnatanand., and B. Huang, {\it Faster storm using compressed sensing}, Nature Methods, 9 (2012), pp. 721-723.
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.