  Wireless sensor networks are widely adopted in military, civilian and
commercial applications, which fuels an exponential explosion of sensory data.
However, a major challenge to deploy effective sensing systems is the presence
of {\em massive missing entries, measurement noise, and anomaly readings}.
Existing works assume that sensory data matrices have low-rank structures. This
does not hold in reality due to anomaly readings, causing serious performance
degradation. In this paper, we introduce an {\em LS-Decomposition} approach for
robust sensory data recovery, which decomposes a corrupted data matrix as the
superposition of a low-rank matrix and a sparse anomaly matrix. First, we prove
that LS-Decomposition solves a convex program with bounded approximation error.
Second, using data sets from the IntelLab, GreenOrbs, and NBDC-CTD projects, we
find that sensory data matrices contain anomaly readings. Third, we propose an
accelerated proximal gradient algorithm and prove that it approximates the
optimal solution with convergence rate $O(1/k^2)$ ($k$ is the number of
iterations). Evaluations on real data sets show that our scheme achieves
recovery error $\leq 5\%$ for sampling rate $\geq 50\%$ and almost exact
recovery for sampling rate $\geq 60\%$, while state-of-the-art methods have
error $10\% \sim 15\%$ at sampling rate $90\%$.
