This is an old revision of the document!

====== Software Practical: Compressed Sensing ====== The software practical is suited for students attending the lecture on Compressed Sensing that additionally wish to apply the algorithms and concepts to concrete examples in order to get a deeper understanding. **Registration:** in the lecture, or mail to [[https://www.stpetra.com|Stefania Petra]]. ===== Assignment ===== After choosing a project, along with a concrete problem instance like image reconstruction (Radon, MRI), deblurring, inpainting or face recognition your task is to **implement the algorithm** in **MATLAB** or **PYTHON**. Write a small **report with 5-7 pages** to decribe the algorithm, convergence properties and your problem setup along with the results of your experiments. Additionally you should briefly **demonstrate your code**. **You can hand in your code+report during or after the semester break** but no later than 03.05.2020. [[https://urz.asknet.de/cgi-bin/product/P10015000!395330!HDSTUD|How to get MATLAB]] ===== Projects ===== === Matrix Completion with Nuclear Norm Minimization === The task is to solve numerically the matrix completion problem via the Douglas-Rachford algorithm (see lecture notes) in the noiseless case and via {{ :teaching:ft1920:vl:cs:files:fista.pdf |FISTA}} in a Lagrangian formulation for the noisy case. For theoretical guarantees see {{ :teaching:ft1920:vl:cs:files:matrixcompletion.pdf |Candes, Tao 2010}}. For a concrete problem instance see below. An subset of the [[http://academictorrents.com/details/9b13183dc4d60676b773c9e2cd6de5e5542cee9a|netflix prize data set ]] can also be used. === Faster FISTA for Wavelet Deblurring === The task ist to implement a fast version of FISTA {{ :teaching:ft1920:vl:cs:files:fasterfista.pdf | Liang, Schönlieb 2019}} and to compare results with the classical version of {{ :teaching:ft1920:vl:cs:files:fista.pdf |FISTA}}. The regulizer should be chosen as the l1-norm of the {{ :teaching:ft1920:vl:cs:files:wavelet.m.zip | wavelet}} transformed signal. The linear operator should be given as a blurring operator, see below. Try several blurring masks! === FISTA versus the Chambolle-Pock Algorithm for Face Recognition === The task ist to compare the performance of {{ :teaching:ft1920:vl:cs:files:fista.pdf |FISTA}} to the {{ :teaching:ft1920:vl:cs:files:chambollepock.pdf |Chambolle-Pock}} algorithm on face recognition. To apply FISTA you need to consider the Lagrangian formulation, see e.g. eq. (4.1) in {{ :teaching:ft1920:vl:cs:files:magma.pdf |Hovhannisyan et al, 2016}}. Summarize the convergence results of the more recent work {{ :teaching:ft1920:vl:cs:files:ergodicconvergencecp.pdf |Chambolle-Pock, 2016}}. === The Chambolle-Pock Framework for Tomography and Deblurring === This project is appropriate for a team of two students. The task is to consider the various convex optimization problems from {{ :teaching:ft1920:vl:cs:files:cp_prototyping.pdf |Sidky et al, 2012 }} and to apply the Chambolle-Pock algorithm for their numerical solution. === Wavelet Deblurring via the Chambolle-Pock Algorithm === Consider wavelet {{ :teaching:ft1920:vl:cs:files:wavelet.m.zip | wavelet}} deblurring. The linear operator should be given as a blurring operator for several blurring masks. As a regularizer choose the l1-norm of the wavlet transformed signal. Set up a recovery model and apply the Chambolle-Pock algorithm but in such a way that you avoid projecting onto the linear constraints. === Total Variation Inpainting and Deblurring via the Chambolle-Pock Algorithm === Consider anisotropic total variation minimization subject to linear constraints. The linear constraints correspond either to the pixel omission operation (inpainting) or the blurring operator for several blurring masks. Implement the Chambolle-Pock algorithm to solve the inverse problem. Be careful when implementing the proximal mapping corresponding to total variation. A good option is {{ :teaching:ft1920:vl:cs:files:tvprox.pdf |Beck, Teboulle, 2009}} === Phase Transitions for Tomography Recovery by Greedy Methods === This project is appropriate for a team of two students. Generate probabilistic recovery plots similar to the ones in {{ :teaching:ft1920:vl:cs:files:tomophasetransitions.pdf | Kuske, Petra 2019}} for all greedy methods from the lecture (orthogonal matching pursuit (OMP) - Alg. 2, matching pursuit (MP) - Alg. 3, iterative hard thresholding (IHT) - Alg. 5, compressive sampling matching pursuit (CoSaMP) - Alg. 7. basic thresholding (BT) - Alg. 4, hard thresholding pursuit (HTP) - Alg. 6, and subspace pursuit (SP)) using this {{ :teaching:ft1920:vl:cs:files:tomo_parallel_beam_binary.m.zip |tomographic projection matrix}}. Compare the results with l1-minimization. Can you modify the greedy methods to deal with nonnegative constraints? You might get some ideas from [[https://hal.archives-ouvertes.fr/hal-02049424/| Nguyen et al, 2019]]. ===== Data Sets ===== * {{ :teaching:ft1819:praktikum:01lowrank.zip |Low rank matrices}} * {{ :teaching:ft1819:praktikum:02deblurring.zip |Deblurring}} * {{ :teaching:ft1819:praktikum:03inpainting.zip |Inpainting}} * {{ :teaching:ft1819:praktikum:04radon.zip |Radon}} * {{ :teaching:ft1819:praktikum:05mri.zip |MRI}} * {{ :teaching:ft1819:praktikum:06facerecognition.zip |Face Recognition}}