tval3_thesis.pdf-资料库

dongguazhangdale-5274899-tval3_thesis.pdf-第1页.png

第1页 / 共92页

dongguazhangdale-5274899-tval3_thesis.pdf-第2页.png

第2页 / 共92页

dongguazhangdale-5274899-tval3_thesis.pdf-第3页.png

第3页 / 共92页

dongguazhangdale-5274899-tval3_thesis.pdf-第4页.png

第4页 / 共92页

dongguazhangdale-5274899-tval3_thesis.pdf-第5页.png

第5页 / 共92页

dongguazhangdale-5274899-tval3_thesis.pdf-第6页.png

第6页 / 共92页

dongguazhangdale-5274899-tval3_thesis.pdf-第7页.png

第7页 / 共92页

dongguazhangdale-5274899-tval3_thesis.pdf-第8页.png

第8页 / 共92页

RICE UNIVERSITY An Eﬃcient Algorithm For Total Variation Regularization with Applications to the Single Pixel Camera and Compressive Sensing by Chengbo Li A Thesis Submitted in Partial Fulfillment of the Requirements for the Degree Master of Arts Approved, Thesis Committee: Yin Zhang, Professor, Chair Computational and Applied Mathematics William W. Symes, Noah G. Harding Professor Computational and Applied Mathematics Wotao Yin, Assistant Professor Computational and Applied Mathematics Kevin Kelly, Associate Professor Electrical and Computer Engineering Houston, Texas September 2009

Abstract An Eﬃcient Algorithm For Total Variation Regularization with Applications to the Single Pixel Camera and Compressive Sensing by Chengbo Li In this thesis, I propose and study an eﬃcient algorithm for solving a class of compres- sive sensing problems with total variation regularization. This research is motivated by the need for eﬃcient solvers capable of restoring images to a high quality captured by the single pixel camera developed in the ECE department of Rice University. Based on the ideas of the augmented Lagrangian method and alternating minimization to solve subproblems, I develop an eﬃcient and robust algorithm called TVAL3. TVAL3 is compared favorably with other widely used algorithms in terms of reconstruction speed and quality. Convincing numerical results are presented to show that TVAL3 is suitable for the single pixel camera as well as many other applications.

Acknowledgements I would like to express my deep and sincere gratitude to my academic advisor, Pro- fessor Yin Zhang. His enthusiasm, profound knowledge, and upbeat personality have greatly inﬂuenced me. He has been helping me accumulate my research skills, tap into my full potential, as well as build up my conﬁdence step by step in conducting research. Without his wholehearted guidance, I might have already lost my interest in optimization. I really take pride in working with him. I would also like to extend my deepest appreciation to Dr. Wotao Yin, who led me to the united CAAM family at Rice University around two years ago. He has provided me tremendous help on both academic and living aspects. I owe many thanks to him for his encouragement, patience, and guidance. Besides, his intelligence and humor have deeply impressed me. He is not only my mentor, but also one of my best friends. Ting Sun, who is one of my collaborators in the ECE department of Rice Uni- versity, has shared large quantities of data with me and helped me fully understand the single pixel camera and other related electrical engineering knowledge. I would like to say that collaborating with Ting Sun has eﬀectively accelerated my research. I owe her many thanks. I feel so grateful for my dear friend Josh Bell and his family. They have helped me revise the draft of my thesis word by word—picking out all catachreses and sole- cisms. It is extremely a boring and painful process for those who know nothing about professional knowledge. What they have done for me will always be remembered. I also appreciate all my friends who are supportive and dedicated all the time. I need to thank Dr. Tapia who taught me that mathematicians could take on more than mathematics; Dr. Borcea, who was my mentor during my ﬁrst year at CAAM

iv and helped me adapt the new environment; Dr. Hewitt who oﬀered suggestions of my usage of the English Language and recommendations for my presentations on several occasions; my committee members Dr. Symes and Dr. Kelly who earnestly reviewed my thesis. Besides, I feel grateful for all other professors who have provided me knowledge and expertise during my undergraduate and graduate studies. Last but certainly not least, I am grateful for my parents, grandfather, and grand- mother for their selﬂess love and unconditional support throughout these years. You are the love of my entire life. I am willing to dedicate this thesis to my dear Yun to commemorate all things between us.

Contents Abstract Acknowledgements List of Figures 1 Introduction 1.1 Compressive Sensing Background . . . . . . . . . . . . . . . . . . . . 1.1.1 Greedy Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 1.1.2 ℓ1 Minimization . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.3 TV Minimization . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Single Pixel Camera . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Methodologies of TV Solvers . . . . . . . . . . . . . . . . . . . . . . . 2 TVAL3 Scheme and Algorithms 2.1 Augmented Lagrangian Method Review . . . . . . . . . . . . . . . . . 2.2 Augmented Lagrangian Algorithm for TV Minimization . . . . . . . . 2.3 Alternating Direction Algorithm for the Subproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Overall Algorithm and Extensions . . . . . . . . . . . . . . . . . . . . 2.3.1 2.3.2 One-step Steepest Descent Scheme Shrinkage-like Formulas 3 Fast Walsh Hadamard Transform 3.1 Hadamard Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Kronecker Product and Fast Walsh Hadamard Transform . . . . . . . 3.3 Comparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Numerical Results and Discussions 4.1 State-of-the-art Solvers and Test Platform . . . . . . . . . . . . . . . 4.2 Comparisons Based on Synthetic Data . . . . . . . . . . . . . . . . . 4.3 Comparisons Based on Measured Data . . . . . . . . . . . . . . . . . Initial Tests on Complex Signals and Nonnegativity Constraints . . . 4.4 4.5 Discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii iii vii 1 2 2 3 4 6 8 11 12 18 20 21 26 29 32 33 37 41 44 44 46 55 61 63

5 Future Work vi 65 66 66 68 5.1 Hyperspectral Imaging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Initial Formulation . . . . . . . . . . . . . . . . . . . . . . . . 5.1.1 Basic Concepts 5.1.2 5.1.3 Parallel Algorithms and Implementations on High Performance Computers 71 5.2 Exploration on Dual Method . . . . . . . . . . . . . . . . . . . . . . . 5.2.1 Derivation of Dual Problem . . . . . . . . . . . . . . . . . . . 5.2.2 Methodology on Dual Problem . . . . . . . . . . . . . . . . . Bibliography 72 73 76 78

List of Figures 1.1 Single pixel camera block diagram . . . . . . . . . . . . . . . . . . . . 3.1 Running time comparison between two FWHT implementations . . . 3.2 Running time comparison between FWHT and FFT . . . . . . . . . . 4.1 Reconstructed 1D staircase signal . . . . . . . . . . . . . . . . . . . . 4.2 Recoverability for 1D staircase signals . . . . . . . . . . . . . . . . . . 4.3 Recovered phantom image from orthonormal measurements . . . . . . 4.4 Recovered phantom image from non-orthonormal measurements . . . 4.5 Recovered MR brain image . . . . . . . . . . . . . . . . . . . . . . . . 4.6 Recoverability for MR brain image . . . . . . . . . . . . . . . . . . . 4.7 Real target in visible light . . . . . . . . . . . . . . . . . . . . . . . . 4.8 Recovered infrared RI image . . . . . . . . . . . . . . . . . . . . . . . 4.9 Recovered the transistor image . . . . . . . . . . . . . . . . . . . . . 4.10 Recovered 1D complex staircase signal . . . . . . . . . . . . . . . . . 4.11 Recovered CT thorax image . . . . . . . . . . . . . . . . . . . . . . . 6 42 43 46 47 49 50 52 53 56 58 59 62 62

Chapter 1 Introduction This thesis concentrates on developing an eﬃcient algorithm which solves a well- known compressive sensing (also known as compressed sensing or CS) problem with total variation (TV) regularization. The main application of this algorithm is to reconstruct the high-resolution image captured by a single pixel camera (SPC). The basic questions are: what is the background and motivation of this research, what methods are used, why is a new algorithm necessary, and how does this new algorithm behave compared with other existing solvers or algorithms? All of these questions will be answered step by step in this thesis. The basic background including compressive sensing and single pixel camera, ex- isting reconstruction algorithms, and the general methodology are introduced in this chapter. The second chapter, one of the most essential chapters in this thesis, de- scribes the main algorithm in detail and introduces the corresponding solver TVAL3 [98]. A structured measurement matrix correlating to the single pixel camera and how this measurement matrix is able to improve the algorithm will be discussed in the following chapter. The algorithm described in this thesis compares favorably with several state-of-the-art algorithms in the fourth chapter of this thesis. Numerical re- 1

资料库

tval3_thesis.pdf

相关推荐

开发技术

热门标签

最新资料