= Solution
The <singular values> discarded by the threshold in (i) satisfy $\lambda^2<c/2$, so their contribution to the fourth moment is at most $(c/2)S_2\leq cn/2$. The selected <singular values> consequently satisfy
$$
\sum_{p=1}^r n_p\lambda_p^4\geq cn/2.
$$
Because $\lambda_p\leq1$, this implies $m=\sum_pn_p\geq cn/2$. On the other hand, $\lambda_p^2\geq c/2$, and hence
$$
\frac c2\,m\leq\sum_pn_p\lambda_p^2\leq S_2\leq n.
$$
Thus
$$
\boxed{\frac{cn}{2}\leq m\leq\frac{2n}{c}}.
$$
The lower bound also shows that the selected list is nonempty. Both endpoints are inclusive, as required.
Back to article page
