Chenyang Cao, Jun He, Marco Apolinario, Tewbesta Alemayehu
In this final report to group project of course CS 520 at Purdue University, we investigated a few algorithms in the field of compressed sensing (CS) [2, 3, 6, 10] including orthogonal matching pursuit (OMP), tree-based OMP [7, 9], Gradient Projection for Sparse Reconstruction (GPSR) [4], Separable Approximation (SpaRSA)[11]. These algorithms are well-developed for an l_1-optimization problem proposed by compressed sensing. We will introduce the details of these algorithms and present some applications and examples in practice by using these algorithms. Next, we implement them from scratch and compare the results in each example among these algorithms to see which algorithm suits the example properly. Finally, we discuss some conclusions of the project.
All our experiments are in the Jupyter Notebook: comparison.ipynb
[1] Steven L Brunton and J Nathan Kutz. Data-driven science and engineering: Machine learning, dynamical systems, and control. Cambridge University Press, 2022.
[2] Emmanuel J Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis? Journal of the ACM (JACM), 58(3):1–37, 2011.
[3] Emmanuel J Candes, Justin K Romberg, and Terence Tao. Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 59(8):1207–1223, 2006.
[4] Mário AT Figueiredo, Robert D Nowak, and Stephen J Wright. Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems. IEEE Journal of selected topics in signal processing, 1(4):586–597, 2007.
[5] Mahdi Khosravy. Recovery in compressive sensing: a review. 2017.
[6] Seung-Jean Kim, Kwangmoo Koh, Michael Lustig, Stephen Boyd, and Dimitry Gorinevsky. An interior-point method for large-scale ℓ1-regularized least squares. IEEE journal of selected topics in signal processing, 1(4):606–617, 2007.
[7] Chinh La and Minh N Do. Signal reconstruction using sparse tree representations. In Wavelets XI, volume 5914, pages 273–283. SPIE, 2005.
[8] Mohamed Shaban. Orthogonal matching pursuit algorithm (omp). 2022.
[9] Joel A Tropp. Greed is good: Algorithmic results for sparse approximation. IEEE Transactions on Information theory, 50(10):2231–2242, 2004.
[10] John Wright, Allen Y Yang, Arvind Ganesh, S Shankar Sastry, and Yi Ma. Robust face recognition via sparse representation. IEEE transactions on pattern analysis and machine intelligence, 31(2):210–227, 2008.
[11] Stephen J Wright, Robert D Nowak, and Mário AT Figueiredo. Sparse reconstruction by separable approximation. IEEE Transactions on signal processing, 57(7):2479–2493, 2009.
[12] Zheng Zhang, Yong Xu, Jian Yang, Xuelong Li, and David Zhang. A survey of sparse representation: Algorithms and applications. IEEE Access, 3:490–530, 2015.