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 Stefania Petra.

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.

How to get MATLAB

The task is to solve numerically the matrix completion problem via the Douglas-Rachford algorithm (see lecture notes) in the noiseless case and via FISTA in a Lagrangian formulation for the noisy case. For theoretical guarantees see Candes, Tao 2010. For a concrete problem instance see below. An subset of the netflix prize data set can also be used.

The task is to implement a fast version of FISTA Liang, Schönlieb 2019 and to compare results with the classical version of FISTA. The regulizer should be chosen as the l1-norm of the wavelet transformed signal. The linear operator should be given as a blurring operator, see below. Try several blurring masks!

The task is to compare the performance of FISTA to the Chambolle-Pock algorithm on face recognition. To apply FISTA you need to consider the Lagrangian formulation, see e.g. eq. (4.1) in Hovhannisyan et al, 2016. Summarize the convergence results of the more recent work Chambolle-Pock, 2016.

This project is appropriate for a team of two students. The task is to consider the various convex optimization problems from Sidky et al, 2012 and to apply the Chambolle-Pock algorithm for their numerical solution.

Consider 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.

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 presented in Beck, Teboulle, 2009

This project is appropriate for a team of two students. Generate probabilistic recovery plots similar to the ones in 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 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 Nguyen et al, 2019.

• Low rank matrices
• Deblurring
• Inpainting
• Radon
• MRI
• Face Recognition