The largest coordinates attain the best s-term ℓ1 error

If $T=\mathrm{\varnothing }$, its retained mass is zero and is no larger than the nonnegative sum on $S$. Otherwise write the ranks of the elements of $T$ in increasing order as $r_1<\cdots <r_k$, where $k=\mathrm{\mid }T\mathrm{\mid }\le s$. Then $r_{\mathrm{\ell }}\ge \mathrm{\ell }$, so the specified ordering gives $\mathrm{\mid }{x}_{j_{r_{\mathrm{\ell }}}}\mathrm{\mid }\le \mathrm{\mid }{x}_{j_{\mathrm{\ell }}}\mathrm{\mid }$ for each $\mathrm{\ell }$. The coordinate sum in [F2] may be reordered by successive adjacent swaps, each preserving the sum by associativity and commutativity of real addition; zero terms may be omitted. Thus $\mathrm{\parallel }{x}_T{\mathrm{\parallel }}_1={\sum }_{\mathrm{\ell }=1}^k\mathrm{\mid }{x}_{j_{r_{\mathrm{\ell }}}}\mathrm{\mid }\le {\sum }_{\mathrm{\ell }=1}^k\mathrm{\mid }{x}_{j_{\mathrm{\ell }}}\mathrm{\mid }\le {\sum }_{\mathrm{\ell }=1}^s\mathrm{\mid }{x}_{j_{\mathrm{\ell }}}\mathrm{\mid }=\mathrm{\parallel }{x}_S{\mathrm{\parallel }}_1$, using termwise monotonicity and then the contiguous split at $k$ with a nonnegative remainder.

For every $U\subseteq [n]$ and $j\in [n]$, the zero-extended restrictions satisfy $\mathrm{\mid }{x}_j\mathrm{\mid }=\mathrm{\mid }(x_U{)}_j\mathrm{\mid }+\mathrm{\mid }(x_{U^c}{)}_j\mathrm{\mid }$. Summing over the original full coordinate range and applying [F2] and the same-range additivity in [F3] gives $\mathrm{\parallel }x{\mathrm{\parallel }}_1=\mathrm{\parallel }{x}_U{\mathrm{\parallel }}_1+\mathrm{\parallel }{x}_{U^c}{\mathrm{\parallel }}_1$. Taking $U=T$ and $U=S$ and subtracting the retained masses, step 1.1 implies $\mathrm{\parallel }{x}_{S^c}{\mathrm{\parallel }}_1\le \mathrm{\parallel }{x}_{T^c}{\mathrm{\parallel }}_1$. Applying this inequality to every admissible $T$, while $S$ itself is admissible, shows that the finite minimum in [F1] equals $\mathrm{\parallel }{x}_{S^c}{\mathrm{\parallel }}_1$.