Sparse Optimization Theory and Methods

Note that S^* and S_εj are compact convex sets and the projection operator Π_s^* (x) is continuous in ℝⁿ. The superimum in (6.71) can be attained for every polytope S_εj. Thus there exists a point in S_εj, denoted by x_εj, such that

$d^{\mathscr{H}}\left(S^{*},S_{{\epsilon }_j}\right)={\Vert x_{{\epsilon }_j}-{\Pi }_{S^{*}}\left(x_{{\epsilon }_j}\right)\Vert }_2.$

Note that S^* ⊆ S_εj+1 ⊆ S_εj for any j ≥ 1. The sequence {d^ℋ(S^*,S_εj)}_j≥1 is non-increasing and non-negative, and hence the limit lim_j→∞ d^ℋ (S^*, S_εj) exists. Passing through to a subsequence if necessary, we may assume that the sequence {x_εj}_j≥1 tends to x̂ Note that x_εj ∈ S_εj which indicates that ‖x_εj‖₁ ≤ ρ^* and hence ‖x̂‖₁ ≤ ρ^*. By Lemma 6.6.1, x̂ must satisfy that ϕ(M^T(Ax̂ – y)) ≤ ε which, together with the fact ‖x‖₁ ≤ ρ^*, implies that x̂ ∈ S^*. Therefore, Π_s^* (x̂) = x̂ and hence

$\underset{j\to \infty }{\lim }{d}^{\mathscr{H}}(S^{}$