Proving a trivial bound on $L_2$ norm of the error in a sparse approximation of a vector

392 Views Asked by At

Trying to understand this supposedly 'trivial' bound from a paper:

If $\theta_N$ denotes the vector $\theta$ with everything except $N$ largest coefficients set to $0$ then we have

$$ || \theta - \theta_N ||_2 \leq C_{2,p} \cdot ||\theta||_p \cdot (N+1)^{1/2 - 1/p} $$

for $N=0,1,2,...$ and constant $C_{2,p}$ depending only on $p \in (0,2)$.