Packing Bounds for Outer Products with Applications to Compressive Sensing
Semper S., and Hotz T.
Geometric Science of Information, 2019
https://doi.org/10.1007/978-3-030-26980-7_15Abstract
In order to obtain good reconstruction guarantees for typical compressive sensing scenarios, we translate the search for good compression matrices into a ball packing problem in a suitable projective space. We then derive such reconstruction guarantees for two relevant scenarios, one where the matrices are unstructured and one where they have to be Khatri-Rao products. Finally, we demonstrate how the proposed method can be implemented with a physically motivated numerical optimization scheme, and how it compares to a conventional scheme of random compression matrices.