Compressive sensing with local geometric features

DOI10.1145/1998196.1998211MaRDI QIDQ5404412zbMATH OpenOpenAlexFDO

Authors Rishi Gupta, Eric Price, Yaron Rachlin, Piotr Indyk

Publication date 24 March 2014

Published in Proceedings of the twenty-seventh annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1208.2447, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.208.4193

zbMATH Keywords

sparse matricescompressive sensingattitude determinationstar tracking

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: 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.

Recommendations

• Compressive sensing using locality-preserving matrices
• Compressed sensing
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Compressive sampling
• The Geometry of Compressed Sensing

Cited in

(7)

• A geometrical stability condition for compressed sensing
• The Geometry of Compressed Sensing
• Compressed sensing by iterative thresholding of geometric wavelets: a comparing study
• Compressive sensing using locality-preserving matrices
• Two-stage geometric information guided image reconstruction
• On low-risk heavy hitters and sparse recovery schemes
• Compressive imaging and characterization of sparse light deflection maps

This page was built for publication: Compressive sensing with local geometric features

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5404412)