  We propose a framework for compressive sensing of images with local
distinguishable objects, such as stars, and apply it to solve a problem in
celestial navigation. Specifically, let x be an N-pixel real-valued image,
consisting of a small number of local distinguishable objects plus noise. Our
goal is to design an m-by-N measurement matrix A with m << N, such that we can
recover an approximation to x from the measurements Ax.
  We construct a matrix A and recovery algorithm with the following properties:
(i) if there are k objects, the number of measurements m is O((k log N)/(log
k)), undercutting the best known bound of O(k log(N/k)) (ii) the matrix A is
very sparse, which is important for hardware implementations of compressive
sensing algorithms, and (iii) the recovery algorithm is empirically fast and
runs in time polynomial in k and log(N).
  We also present a comprehensive study of the application of our algorithm to
attitude determination, or finding one's orientation in space. Spacecraft
typically use cameras to acquire an image of the sky, and then identify stars
in the image to compute their orientation. Taking pictures is very expensive
for small spacecraft, since camera sensors use a lot of power. Our algorithm
optically compresses the image before it reaches the camera's array of pixels,
reducing the number of sensors that are required.
