Necessary and sufficient conditions of solution uniqueness in l1 minimization

H. Zhang, W. Yin, L. Cheng

Submitted for publication

Technical report

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~ |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, Rice CAAM technical report 12-18, 2012.

« Back