Necessary and sufficient conditions of solution uniqueness in l1 minimization

H. Zhang, W. Yin, L. Cheng

Published in Journal of Optimization Theory and Applications

Overview

This paper presents one unified set of conditions, both necessary and sufficient, on whether any of the following ell_1 problems has a unique solution:

min_x~ |x|_1quadmbox{s.t.}~Ax=b,
min_x~ f_1(Ax-b) + lambda |x|_1,
min_x~ |x|_1quadmbox{s.t.}~f_2(Ax-b)lesigma,
min_x~ f_3(Ax-b)quadmbox{s.t.}~|x|_1letau,

where f_1,f_2,f_3 are strictly convex functions.

The paper also discusses how to numerically recognize unique solutions and verify the uniqueness conditions.

Citation

H. Zhang, W. Yin, and L. Cheng, Necessary and sufficient conditions of solution uniqueness in l1 minimization, Journal of Optimization Theory and Applications, 164(1), 109-122, 2015. DOI: 10.1007/s10957-014-0581-z


« Back