  Suppose that a solution $\widetilde{\mathbf{x}}$ to an underdetermined linear
system $\mathbf{b} = \mathbf{A} \mathbf{x}$ is given. $\widetilde{\mathbf{x}}$
is approximately sparse meaning that it has a few large components compared to
other small entries. However, the total number of nonzero components of
$\widetilde{\mathbf{x}}$ is large enough to violate any condition for the
uniqueness of the sparsest solution. On the other hand, if only the dominant
components are considered, then it will satisfy the uniqueness conditions. One
intuitively expects that $\widetilde{\mathbf{x}}$ should not be far from the
true sparse solution $\mathbf{x}_0$. We show that this intuition is the case by
providing an upper bound on $\| \widetilde{\mathbf{x}} - \mathbf{x}_0\|$ which
is a function of the magnitudes of small components of $\widetilde{\mathbf{x}}$
but independent from $\mathbf{x}_0$. This result is extended to the case that
$\mathbf{b}$ is perturbed by noise. Additionally, we generalize the upper
bounds to the low-rank matrix recovery problem.
