Optimizations to the Orthogonal Matching Pursuit Algorithm for Sparse Basis Representations of Photometric Redshift PDFs

Chan, Christopher

Permalink

https://hdl.handle.net/2142/107786 Copy

Description

Title

Optimizations to the Orthogonal Matching Pursuit Algorithm for Sparse Basis Representations of Photometric Redshift PDFs

Author(s)

Chan, Christopher

Contributor(s)

Smaragdis, Paris

Issue Date

2016-05

Keyword(s)

• Signal processing
• PDF compression
• Photometric redshift estimation
• NumPy
• SciPy

Abstract

This thesis investigates potential optimizations for the K-SVD algorithm (using Orthogonal Matching Pursuit) to create a sparse basis representation of probability density functions (PDFs), as implemented by NCSA research affiliate Matias Carrasco Kind and Professor Robert J. Brunner. The implementation these scientists engineered is currently being used to compress PDFs of photometric redshifts (i.e., distance estimates) for galaxies by about 90%. This implementation allows end-users to easily reconstruct the original PDF with accuracies better than 98%. As we continue to mine large, photometric sky surveys, photometric redshift PDF storage will need to scale appropriately; thus, meaningful advances in this algorithm's implementation will serve to demonstrably benefit our scientific ability to explore the Universe and to expand our cosmological understanding. However, the existing implementation of the algorithm is limited by run time—an issue that continues to grow more important as the number of data surveys acquired becomes larger. The existing implementation utilizes SciPy, a scientific computing Python library. Explored this past semester was the implementation by developing and testing alternative approaches to the core algorithms in C++, beginning with different linear algebra libraries. In the initial tests, limitations in Eigen, a C++ linear algebra library, were found making it difficult to accurately reproduce both the results and the exaction speeds due to the optimizations that NumPy, the Python numerical library, already has implemented. By next pivoting to Armadillo, another C++ linear algebra library, it was discovered that the primary algorithm runs slightly quicker than its Python counterpart. This research is an ongoing project, with continuing exciting investigations into hardware assists, specifically in testing the efficiency of GPU-accelerated computation (NVBLAS). Once an optimization has been identified, the next step is implementing Batch Orthogonal Matching Pursuit, an algorithm more suited for large sets of PDFs over a single dictionary, and, if time permits, an algorithm that can be extended to support two-dimensional PDF representations.

Type of Resource

text

Language

en

Permalink

http://hdl.handle.net/2142/107786

Owning Collections