  In this paper, we study the problem of decomposing a superposition of a
low-rank matrix and a sparse matrix when a relatively few linear measurements
are available. This problem arises in many data processing tasks such as
aligning multiple images or rectifying regular texture, where the goal is to
recover a low-rank matrix with a large fraction of corrupted entries in the
presence of nonlinear domain transformation. We consider a natural convex
heuristic to this problem which is a variant to the recently proposed Principal
Component Pursuit. We prove that under suitable conditions, this convex program
guarantees to recover the correct low-rank and sparse components despite
reduced measurements. Our analysis covers both random and deterministic
measurement models.
