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.

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.

Reçu le :
Accepté le :
DOI : 10.1051/cocv/2018061
Classification : 65K05, 90C05, 90C25, 90C30, 90C46
Mots-clés : Solution existence and uniqueness, convex polyhedral function, ℓ1 minimization, basis pursuit, LASSO
Mousavi, Seyedahmad 1 ; Shen, Jinglai 1

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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/articles/10.1051/cocv/2018061/

[1] K.M. Anstreicher, Linear programming in $$ operations. SIAM J. Optim. 9 (1999) 803–812 | DOI | MR | Zbl

[2] D.P. Bertsekas, Nonlinear Programming. 2nd edn. Athena Scientific, Belmont, MA (1999) | MR | Zbl

[3] D.P. Bertsekas, Convex Optimization Theory. Athena Scientific, Belmont, MA (2009) | MR | Zbl

[4] E. J. Candes and Y. Plan, A probabilistic and RIPless theory of compressed sensing. IEEE Trans. Inf. Theory 57 (2011) 7235–7254 | DOI | MR | Zbl

[5] E. Candes and T. Tao, The Dantzig selector: statistical estimation when p is much larger than n. Ann. Stat. 35 (2007) 2313–2351 | MR | Zbl

[6] F. Facchinei and J.-S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems. Spring-Verlag, New York (2003) | MR | Zbl

[7] S. Foucart and D. Koslicki, Sparse recovery by means of nonnegative least squares. IEEE Signal Process. Lett. 21 (2014) 498–502 | DOI

[8] S. Foucart and H. Rauhut, A Mathematical Introduction to Compressive Sensing. Birkhäuser, Basel, Switzerland (2013) | DOI | MR | Zbl

[9] J.J. Fuchs, On sparse representations in arbitrary redundant bases. IEEE Trans. Inf. Theory 50 (2004) 1341–1344 | DOI | MR | Zbl

[10] J.C. Gilbert, On the solution uniqueness characterization in the L1 norm and polyhedral gauge recovery. J. Optim. Theory Appl. 172 (2017) 70–101 | DOI | MR | Zbl

[11] Y. Itoh, M.F. Duarte and M. Parente. Perfect recovery conditions for non-negative sparse modeling. IEEE Trans. Signal Process. 65 (2017) 69–80 | DOI | MR | Zbl

[12] S.J. Kim, K. Koh, S. Boyd and D. Gorinevsky, ℓ1 trend filtering. SIAM Rev. 51 (2009) 339–360 | DOI | MR | Zbl

[13] O.L. Mangasarian, Uniqueness of solution in linear programming. Linear Algebra Appl. 25 (1979) 151–162 | DOI | MR | Zbl

[14] A. Rinaldo, Properties and refinements of the fused lasso. Ann. Stat. 37 (2009) 2922–2952 | DOI | MR | Zbl

[15] R.T. Rockafellar, Convex Analysis. Princeton University Press (1970) | DOI | MR | Zbl

[16] A.P. Ruszczynski, Nonlinear Optimization. Princeton University Press (2006) | DOI | MR | Zbl

[17] S. Scholtes, Introduction to Piecewise Differentiable Equations. Habilitation thesis, Institut für Statistik und Mathematische Wirtschaftstheorie, Universität Karlsruhe (1994)

[18] J. Shen, Robust non-Zenoness of piecewise affine systems with applications to linear complementarity systems. SIAM J. Optim. 24 (2014) 2023–2056 | DOI | MR | Zbl

[19] J. Shen and T.M. Lebair, Shape restricted smoothing splines via constrained optimal control and nonsmooth Newton’s methods. Automatica 53 (2015) 216–224 | DOI | MR | Zbl

[20] J. Shen and S. Mousavi, Least sparsity of p-norm based optimization problems with p > 1. SIAM J. Optim. 28 (2018) 2721–2751 | DOI | MR | Zbl

[21] J. Shen and X. Wang, Estimation of monotone functions via P-splines: a constrained dynamical optimization approach. SIAM J. Control Optim. 49 (2011) 646–671 | DOI | MR | Zbl

[22] J. Shen, L. Han and J.-S. Pang, Switching and stability properties of conewise linear systems. ESAIM: COCV 16 (2010) 764–793 | Numdam | MR | Zbl

[23] R.J. Tibshirani, The Lasso problem and uniqueness. Electron. J. Stat. 7 (2013) 1456–1490 | DOI | MR | Zbl

[24] R. J. Tibshirani, The Solution Path of the Generalized LASSO. Ph.D. thesis, Stanford University (2011) | MR

[25] R. Tibshirani and J. Taylor, Degrees of freedom in Lasso problems. Ann. Stat. 40 (2012) 1198–1232 | DOI | MR | Zbl

[26] R. Tibshirani, M. Saunders, S. Rosset, J. Zhu and K. Knight, Sparsity and smoothness via the fused Lasso. J. R. Stat. Soc.: B (Statistical Methodology) 67 (2005) 91–108 | DOI | MR | Zbl

[27] M. Wang, W. Xu and A. Tang, A unique “nonnegative” solution to an underdetermined system: from vectors to matrices. IEEE Trans. Signal Process. 59 (2011) 1007–1016 | DOI | MR | Zbl

[28] H. Zhang, W. Yin and L. Cheng, Necessary and sufficient conditions of solution uniqueness in 1-norm minimization. J. Optim. Theory Appl. 164 (2015) 109–122 | DOI | MR | Zbl

[29] H. Zhang, M. Yan and W. Yin, One condition for solution uniqueness and robustness of both ℓ1-synthesis and ℓ1-analysis minimizations. Adv. Comput. Math. 42 (2016) 1381–1399 | DOI | MR | Zbl

[30] Y.-B. Zhao, RSP-based analysis for sparest and least ℓ1-norm solutions to underdetermined linear systems. IEEE Trans. Signal Process. 61 (2013) 5777–5788 | DOI | MR | Zbl

[31] Y.-B. Zhao, 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 | DOI | MR | Zbl

[32] Y.-B. Zhao, Sparse Optimization Theory and Methods. CRC Press, Taylor & Francis, NY (2018) | DOI | MR

[33] Y.-B. Zhao and C. Xu, 1-bit compressive sensing: reformulation and RRSP-based sign recovery theory. Sci. China Math. 59 (2016) 2049–2074 | DOI | MR | Zbl

Cité par Sources :