Analyses of Successful Sparse Signal Recovery via Tail-$\ell_{2}$ Minimization

Recovery guarantee analyses of sparse signals by the tail-<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\ell_{2}$</tex-math></inline-formula> minimization approach are presented. Known for the lack of sparse recovery capacity by traditional <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\ell_{2}$</tex-math></inline-formula> minimization, its variation by an iterative tail-<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\ell_{2}$</tex-math></inline-formula> penalty procedure, however, is shown to be exceedingly effective in sparse selections. The analytical close-form solutions of the tail-<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\ell_{2}$</tex-math></inline-formula> formulation also reveal its superb efficiency. This article is focused on the analyses of the successful recovery by the tail-<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\ell_{2}$</tex-math></inline-formula> technique. A necessary and sufficient condition for the uniqueness of the tail-<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\ell_{2}$</tex-math></inline-formula> minimizer is established, which is seen inherently different from that of a similar tail-<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\ell_{1}$</tex-math></inline-formula> minimization problem. The inherent differences lead to further analyses of sufficient conditions for the uniqueness, and a notion of admissible solutions. Successful probability analysis is then carried out based on these conditions. The estimated probability of successful recovery <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathbb{P}_{T}$</tex-math></inline-formula> is righteously related to the cardinality of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$T^{c} \cap S$</tex-math></inline-formula>, where <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</i> is an estimated support of the solution index <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">S</i>. The smaller the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$|T^{c} \cap S|$</tex-math></inline-formula> is, the greater the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathbb{P}_{T}$</tex-math></inline-formula> will be, and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathbb{P}_{T}$</tex-math></inline-formula> naturally approaches 1 as <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$|T^{c} \cap S|$</tex-math></inline-formula> approaches 0. Numerical experiments sufficiently validate the efficiency and the successful probability of the sparse signal recovery by the tail-<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\ell_{2}$</tex-math></inline-formula> minimization procedure.