The geometry of sparse analysis regularization. (English) Zbl 1528.90188
Motivated by applications in machine learning and inverse problems, the authors investigate the geometry of the solution set (when nontrivial) of the sum of an \(\ell^1\) regularization with an \(\ell^2\) data fidelity term. A connection between the support of a solution and the minimal face of the solution polyhedron containing it is revealed, having as a consequence the fact that the extreme points of the latter can be recovered via an algebraic test. A connection between the sign pattern of a solution and the ambient dimension of the smallest face containing it is provided as well. Moreover, an arbitrary subpolyhedra of the level set turns out to be writable as a solution set of sparse analysis regularization with explicit parameters.
Reviewer: Sorin-Mihai Grad (Paris)
References:
| [1] | Ali, A. and Tibshirani, R. J., The Generalized Lasso Problem and Uniqueness, preprint, arXiv:1805.07682, 2018. · Zbl 1473.62247 |
| [2] | Barbara, A., Jourani, A., and Vaiter, S., Maximal solutions of sparse analysis regularization, J. Optimiz. Theory Appl., 180 (2019), pp. 374-396, doi:10.1007/s10957-018-1385-3. · Zbl 1409.90136 |
| [3] | Beck, A. and Teboulle, M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2 (2009), pp. 183-202. · Zbl 1175.94009 |
| [4] | Billera, L. J. and Lee, C. W., Sufficiency of McMullen’s conditions for \(f\) -vectors of simplicial polytopes, Bull. Amer. Math. Soc. (N.S.), 2 (1980), pp. 181-185. · Zbl 0431.52009 |
| [5] | Björner, A., Las Vergnas, M., Sturmfels, B., White, N., and Ziegler, G. M., Oriented Matroids, Vol. 46, Cambridge University Press, 1999. · Zbl 0944.52006 |
| [6] | Bolker, E. D., A class of convex bodies, Trans. Am. Math. Soc., 145 (1969), pp. 323-345. · Zbl 0194.23102 |
| [7] | Boyer, C., Chambolle, A., Castro, Y., Duval, V., de Gournay, F., and Weiss, P., On representer theorems and convex regularization, SIAM J. Optimiz., 29 (2019), pp. 1260-1281, doi:10.1137/18M1200750. · Zbl 1423.49036 |
| [8] | Burke, J. and Ferris, M. C., Characterization of solution sets of convex programs, Oper. Res. Lett., 10 (1991), pp. 57-60. · Zbl 0719.90055 |
| [9] | Chambolle, A. and Pock, T., A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Vis. Imaging, 40 (2011), pp. 120-145. · Zbl 1255.68217 |
| [10] | Efron, B., Hastie, T., Johnstone, I., and Tibshirani, R., Least angle regression, Ann. Stat., 32 (2004), pp. 407-499, doi:10.1214/009053604000000067. · Zbl 1091.62054 |
| [11] | Elad, M., Milanfar, P., and Rubinstein, R., Analysis versus synthesis in signal priors, Inverse Probl., 23 (2007), pp. 947-968, doi:10.1088/0266-5611/23/3/007. · Zbl 1138.93055 |
| [12] | Ewald, K. and Schneider, U., On the distribution, model selection properties and uniqueness of the lasso estimator in low and high dimensions, Electron. J. Stat., 14 (2020), pp. 944-969. · Zbl 1440.62060 |
| [13] | Guyon, I., Gunn, S., Ben-Hur, A., and Dror, G., Result analysis of the NIPS 2003 feature selection challenge, NeurIPS, 17 (2004). |
| [14] | Hiriart-Urruty, J.-B. and Lemaréchal, C., Convex analysis and minimization algorithms I: Fundamentals, Vol. 305, Springer Science & Business Media, New York, 2013. |
| [15] | Jeyakumar, V. and Yang, X., On characterizing the solution sets of pseudolinear programs, J. Optimiz. Theory Appl., 87 (1995), pp. 747-755. · Zbl 0840.90118 |
| [16] | Kimeldorf, G. and Wahba, G., Some results on Tchebycheffian spline functions, J. Math. Anal. Appl., 33 (1971), pp. 82-95, doi:10.1016/0022-247X(71)90184-3. · Zbl 0201.39702 |
| [17] | Mairal, J. and Yu, B., Complexity Analysis of the Lasso Regularization Path, preprint, arXiv:1205.0079, 2012. |
| [18] | Mangasarian, O., Minimum-support solutions of polyhedral concave programs, Optimization, 45 (1999), pp. 149-162. · Zbl 0945.90042 |
| [19] | Mangasarian, O. L., A simple characterization of solution sets of convex programs, Oper. Res. Lett., 7 (1988), pp. 21-26. · Zbl 0653.90055 |
| [20] | McMullen, P., The maximum numbers of faces of a convex polytope, Mathematika, 17 (1970), pp. 179-184. · Zbl 0217.46703 |
| [21] | Nam, S., Davies, M. E., Elad, M., and Gribonval, R., The cosparse analysis model and algorithms, Appl. Comput. Harmon. Anal., 34 (2013), pp. 30-56, doi:10.1016/j.acha.2012.03.006. · Zbl 1261.94018 |
| [22] | Rockafellar, R. T., Convex Analysis, , Princeton University Press, Princeton, NJ, 1970. · Zbl 0193.18401 |
| [23] | Rudin, L. I., Osher, S., and Fatemi, E., Nonlinear total variation based noise removal algorithms, Phys. D Nonlinear Phenom., 60 (1992), pp. 259-268. doi:10.1016/0167-2789(92)90242-F. · Zbl 0780.49028 |
| [24] | Schneider, U. and Tardivel, P., The Geometry of Uniqueness, Sparsity and Clustering in Penalized Estimation, preprint, arXiv:2004.09106, 2020. |
| [25] | Schölkopf, B., Herbrich, R., and Smola, A. J., A generalized representer theorem, in International Conference on Computational Learning Theory, , Springer, New York, 2001, pp. 416-426. · Zbl 0992.68088 |
| [26] | Sharpnack, J., Singh, A., and Rinaldo, A., Sparsistency of the edge lasso over graphs, in Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, Lawrence, N. D. and Girolami, M., eds., , La Palma, Canary Islands, PMLR, 2012, pp. 1028-1036, https://proceedings.mlr.press/v22/sharpnack12.html. |
| [27] | She, Y., Sparse regression with exact clustering, Electron. J. Stat., 4 (2010), pp. 1055-1096, doi:10.1214/10-EJS578. · Zbl 1329.62327 |
| [28] | Steidl, G., Weickert, J., Brox, T., Mrázek, P., and Welk, M., On the equivalence of soft wavelet shrinkage, total variation diffusion, total variation regularization, and sides, SIAM J. Numer. Anal., 42 (2004), pp. 686-713, doi:10.1137/S0036142903422429. · Zbl 1083.94001 |
| [29] | Tardivel, P. J. C., Skalski, T., Graczyk, P., and Schneider, U., The Geometry of Model Recovery by Penalized and Thresholded Estimators, in process, 2021, https://hal.archives-ouvertes.fr/hal-03262087. |
| [30] | Tibshirani, R., Regression shrinkage and selection via the lasso, J. R. Stat. Soc. Ser. B (Methodol.), 58 (1996), pp. 267-288. · Zbl 0850.62538 |
| [31] | Tibshirani, R., Saunders, M., Rosset, S., Zhu, J., and Knight, K., Sparsity and smoothness via the fused lasso, J. R. Stat. Soc. Ser. B (Stat. Methodol.), 67 (2005), pp. 91-108, doi:10.1111/j.1467-9868.2005.00490.x. · Zbl 1060.62049 |
| [32] | Tibshirani, R. J., The lasso problem and uniqueness, Electron. J. Statist., 7 (2013), pp. 1456-1490, doi:10.1214/13-EJS815. · Zbl 1337.62173 |
| [33] | Tibshirani, R. J. and Taylor, J., The solution path of the generalized lasso, Ann. Statist., 39 (2011), pp. 1335-1371, doi:10.1214/11-AOS878. · Zbl 1234.62107 |
| [34] | Unser, M., A Unifying Representer Theorem for Inverse Problems and Machine Learning, preprint, arXiv:1903.00687, 2019. · Zbl 1479.46088 |
| [35] | Vaiter, S., Deledalle, C., Peyré, G., Dossal, C., and Fadili, J. M., Local behavior of sparse analysis regularization: Applications to risk estimation, Appl. Comput. Harmon. Anal., 35 (2013), pp. 433-451, doi:10.1016/j.acha.2012.11.006. · Zbl 1291.65189 |
| [36] | Vaiter, S., Peyre, G., Dossal, C., and Fadili, J., Robust sparse analysis regularization, IEEE Trans. Inform. Theory, 59 (2013), pp. 2001-2016, doi:10.1109/TIT.2012.2233859. · Zbl 1364.94172 |
| [37] | Virtanen, P., Gommers, R., Oliphant, T. E., Haberland, M., Reddy, T., et al., SciPy 1.0: Fundamental algorithms for scientific computing in python, Nat. Methods, 17 (2020), pp. 261-272, doi:10.1038/s41592-019-0686-2. |
| [38] | Zhang, H., Yan, M., and Yin, W., One condition for solution uniqueness and robustness of both l1-synthesis and l1-analysis minimizations, Adv. Comput. Math., 42 (2016), pp. 1381-1399, doi:10.1007/s10444-016-9467-y. · Zbl 1362.65064 |
| [39] | Ziegler, G. M., Lectures on Polytopes, Vol. 152, Springer Science & Business Media, New York, 1995. · Zbl 0823.52002 |
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.
