Voir la notice de l'article provenant de la source Numdam
In this paper, we study the solution uniqueness of an individual feasible vector of a class of convex optimization problems involving convex piecewise affine functions and subject to general polyhedral constraints. This class of problems incorporates many important polyhedral constrained ℓ1 recovery problems arising from sparse optimization, such as basis pursuit, LASSO, and basis pursuit denoising, as well as polyhedral gauge recovery. By leveraging the max-formulation of convex piecewise affine functions and convex analysis tools, we develop dual variables based necessary and sufficient uniqueness conditions via simple and yet unifying approaches; these conditions are applied to a wide range of ℓ1 minimization problems under possible polyhedral constraints. An effective linear program based scheme is proposed to verify solution uniqueness conditions. The results obtained in this paper not only recover the known solution uniqueness conditions in the literature by removing restrictive assumptions but also yield new uniqueness conditions for much broader constrained ℓ1-minimization problems.
Mousavi, Seyedahmad 1 ; Shen, Jinglai 1
@article{COCV_2019__25__A56_0,
author = {Mousavi, Seyedahmad and Shen, Jinglai},
title = {Solution uniqueness of convex piecewise affine functions based optimization with applications to constrained \ensuremath{\ell}\protect\textsubscript{1} minimization},
journal = {ESAIM: Control, Optimisation and Calculus of Variations},
publisher = {EDP-Sciences},
volume = {25},
year = {2019},
doi = {10.1051/cocv/2018061},
zbl = {1461.65178},
mrnumber = {4023126},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/cocv/2018061/}
}
TY - JOUR AU - Mousavi, Seyedahmad AU - Shen, Jinglai TI - Solution uniqueness of convex piecewise affine functions based optimization with applications to constrained ℓ1 minimization JO - ESAIM: Control, Optimisation and Calculus of Variations PY - 2019 VL - 25 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/cocv/2018061/ DO - 10.1051/cocv/2018061 LA - en ID - COCV_2019__25__A56_0 ER -
%0 Journal Article %A Mousavi, Seyedahmad %A Shen, Jinglai %T Solution uniqueness of convex piecewise affine functions based optimization with applications to constrained ℓ1 minimization %J ESAIM: Control, Optimisation and Calculus of Variations %D 2019 %V 25 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/cocv/2018061/ %R 10.1051/cocv/2018061 %G en %F COCV_2019__25__A56_0
Mousavi, Seyedahmad; Shen, Jinglai. Solution uniqueness of convex piecewise affine functions based optimization with applications to constrained ℓ1 minimization. ESAIM: Control, Optimisation and Calculus of Variations, Tome 25 (2019), article no. 56. doi : 10.1051/cocv/2018061. http://geodesic.mathdoc.fr/articles/10.1051/cocv/2018061/
[1] , Linear programming in $$ operations. SIAM J. Optim. 9 (1999) 803–812 | Zbl | MR | DOI
[2] , Nonlinear Programming. 2nd edn. Athena Scientific, Belmont, MA (1999) | Zbl | MR
[3] , Convex Optimization Theory. Athena Scientific, Belmont, MA (2009) | Zbl | MR
[4] and , A probabilistic and RIPless theory of compressed sensing. IEEE Trans. Inf. Theory 57 (2011) 7235–7254 | Zbl | MR | DOI
[5] and , The Dantzig selector: statistical estimation when p is much larger than n. Ann. Stat. 35 (2007) 2313–2351 | Zbl | MR
[6] and , Finite-Dimensional Variational Inequalities and Complementarity Problems. Spring-Verlag, New York (2003) | Zbl | MR
[7] and , Sparse recovery by means of nonnegative least squares. IEEE Signal Process. Lett. 21 (2014) 498–502 | DOI
[8] and , A Mathematical Introduction to Compressive Sensing. Birkhäuser, Basel, Switzerland (2013) | Zbl | MR | DOI
[9] , On sparse representations in arbitrary redundant bases. IEEE Trans. Inf. Theory 50 (2004) 1341–1344 | Zbl | MR | DOI
[10] , On the solution uniqueness characterization in the L1 norm and polyhedral gauge recovery. J. Optim. Theory Appl. 172 (2017) 70–101 | Zbl | MR | DOI
[11] , and Perfect recovery conditions for non-negative sparse modeling. IEEE Trans. Signal Process. 65 (2017) 69–80 | Zbl | MR | DOI
[12] , , and , ℓ1 trend filtering. SIAM Rev. 51 (2009) 339–360 | Zbl | MR | DOI
[13] , Uniqueness of solution in linear programming. Linear Algebra Appl. 25 (1979) 151–162 | Zbl | MR | DOI
[14] , Properties and refinements of the fused lasso. Ann. Stat. 37 (2009) 2922–2952 | Zbl | MR | DOI
[15] , Convex Analysis. Princeton University Press (1970) | Zbl | MR | DOI
[16] , Nonlinear Optimization. Princeton University Press (2006) | Zbl | MR | DOI
[17] , Introduction to Piecewise Differentiable Equations. Habilitation thesis, Institut für Statistik und Mathematische Wirtschaftstheorie, Universität Karlsruhe (1994)
[18] , Robust non-Zenoness of piecewise affine systems with applications to linear complementarity systems. SIAM J. Optim. 24 (2014) 2023–2056 | Zbl | MR | DOI
[19] and , Shape restricted smoothing splines via constrained optimal control and nonsmooth Newton’s methods. Automatica 53 (2015) 216–224 | Zbl | MR | DOI
[20] and , Least sparsity of p-norm based optimization problems with p > 1. SIAM J. Optim. 28 (2018) 2721–2751 | Zbl | MR | DOI
[21] and , Estimation of monotone functions via P-splines: a constrained dynamical optimization approach. SIAM J. Control Optim. 49 (2011) 646–671 | Zbl | MR | DOI
[22] , and , Switching and stability properties of conewise linear systems. ESAIM: COCV 16 (2010) 764–793 | Zbl | MR | mathdoc-id
[23] , The Lasso problem and uniqueness. Electron. J. Stat. 7 (2013) 1456–1490 | Zbl | MR | DOI
[24] , The Solution Path of the Generalized LASSO. Ph.D. thesis, Stanford University (2011) | MR
[25] and , Degrees of freedom in Lasso problems. Ann. Stat. 40 (2012) 1198–1232 | Zbl | MR | DOI
[26] , , , and , Sparsity and smoothness via the fused Lasso. J. R. Stat. Soc.: B (Statistical Methodology) 67 (2005) 91–108 | Zbl | MR | DOI
[27] , and , A unique “nonnegative” solution to an underdetermined system: from vectors to matrices. IEEE Trans. Signal Process. 59 (2011) 1007–1016 | MR | Zbl | DOI
[28] , and , Necessary and sufficient conditions of solution uniqueness in 1-norm minimization. J. Optim. Theory Appl. 164 (2015) 109–122 | MR | Zbl | DOI
[29] , and , One condition for solution uniqueness and robustness of both ℓ1-synthesis and ℓ1-analysis minimizations. Adv. Comput. Math. 42 (2016) 1381–1399 | MR | Zbl | DOI
[30] , RSP-based analysis for sparest and least ℓ1-norm solutions to underdetermined linear systems. IEEE Trans. Signal Process. 61 (2013) 5777–5788 | MR | Zbl | DOI
[31] , Equivalence and strong equivalence between the sparsest and least ℓ1 -norm nonnegative solutions of linear systems and their applications. J. Oper. Res. Soc. China 2 (2014) 171–193 | MR | Zbl | DOI
[32] , Sparse Optimization Theory and Methods. CRC Press, Taylor & Francis, NY (2018) | MR | DOI
[33] and , 1-bit compressive sensing: reformulation and RRSP-based sign recovery theory. Sci. China Math. 59 (2016) 2049–2074 | MR | Zbl | DOI
Cité par Sources :