| Título: | Deterministic Compressed Sensing |
| Autores: | Jafarpour, Sina |
| Fecha: |
2011-11-18 2011-11-18 2011 |
| Publicador: | Universidad de Princenton |
| Fuente: |
 |
| Tipo: | Academic dissertations (Ph.D.) |
| Tema: |
Coding Theory Compressed Sensing Expander Graphs Game Theory Machine Learning Probabilistic Method Computer science Mathematics Electrical engineering |
| Descripción: | The central goal of compressed sensing is to capture attributes of a signal using very few measurements. The initial publications by Donoho and by Candes and Tao have been followed by applications to image compression, data streaming, medical signal processing, digital communication and many others. The emphasis has been on random sensing but the limitations of this framework include performance guarantees, storage requirements, and computational cost. This thesis will describe two deterministic alternatives. The first alternative is based on expander graphs. We first show how expander graphs are appropriate for compressed sensing in terms of providing explicit and efficient sensing matrices as well as simple and efficient recovery algorithms. We show that by reformulating signal reconstruction as a zero-sum game we can efficiently recover any sparse vector. We provide a saddle-point reformulation of the expander-based sparse approximation problem, and propose an efficient expander-based sparse approximation algorithm, called the GAME algorithm. We show that the restricted isometry property of expander matrices in the $\ell_1$-norm ensures that the GAME algorithm always recovers a sparse approximation to the optimal solution with an $\ell_1/\ell_1$ data-domain approximation guarantee. We also demonstrate resilience to Poisson noise. The Poisson noise model is appropriate for a variety of applications, including low-light imaging and digital streaming, where the signal-independent and/or bounded noise models used in the compressed sensing literature are no longer applicable. We develop a novel sensing paradigm based on expander graphs and propose a MAP algorithm for recovering sparse or compressible signals from Poisson observations. We support our results with experimental demonstrations of reconstructing average packet arrival rates and instantaneous packet counts at a router in a communication network, where the arrivals of packets in each flow follow a Poisson process. The second alternative is based on error correcting codes. We show that deterministic sensing matrices based on second order Reed Muller codes optimize average case performance. We also describe a very simple algorithm, one-step thresholding, that succeeds in average case model selection and sparse approximation, where more sophisticated algorithms, developed in the context of random sensing, fail completely. Finally, we provide an algorithmic framework for structured sparse recovery, where some extra prior knowledge about the sparse vector is also available. Our algorithm, called Nesterov Iterative Hard-Thresholding (NIHT) uses the gradient information in the convex data error objective to navigate over the non-convex set of structured sparse signals. Experiments show however that NIHT can empirically outperform $\ell_1$-minimization and other state-of-the-art convex optimization-based algorithms in sparse recovery. |
| Idioma: | Inglés |
1 Engineering solutions for a carbon-constrained world por Celia, M. A.,Nordbotten, J. M. | 6 Impact of capillary forces on large-scale migration of CO2 por Nordbotten, Jan M.,Dahle, Helge K. |
2 Analysis of Plume Extent using Analytical Solutions for CO2 Storage por Nordbotten, Jan M.,Celia, Michael A. | 7 Impact of geological heterogeneity on early-stage CO2 plume migration por Ashraf, Meisam,Lie, Knut-Andreas,Nilsen, Halvor M.,Nordbotten, Jan M.,Skorstad, Arne |
3 A model-oriented benchmark problem for CO2 storage por Dahle, Helge K.,Eigestad, Geir T.,Nordbotten, Jan M.,Pruess, K. | 8 CO2 trapping in sloping aqiufers: High resolution numerical simulations por Elenius, Maria,Tchelepi, Hamdi,Johannsen, Klaus |
4 Report from CO2 storage workshop por Dahle, Helge K.,Lien, Martha,Nordbotten, Jan M.,Lie, Knut-Andreas,Braathen, Alvar,Helmig, Rainer,Class, Holger,Celia, Michael A. | 9 Streamline methods for parabolic differential equations por Hafver, Jørn |
5 Summary of Princeton Workshop on Geological Storage of CO2 por Celia, Michael A.,Nordbotten, Jan M.,Bachu, Stefan,Kavetski, Dmitri,Gasda, Sarah | 10 Vertically Averaged Models for CO2 Storage in Porous Media por Hammer, Andreas |