Suppose a non-random portion of a data vector is missing. With some minimal prior knowledge about the data vector, can we recover the missing portion from the available one? In this paper, we consider a linear programming approach to this problem, present numerical evidence suggesting the effectiveness and limitation of this approach, and give deterministic conditions that guarantee a successful recovery. Our theoretical results, though related to recent results in compressive sensing, do not rely on randomization.