Blogito, ergo sum.

Math, Code, Philosophy, Food, and Memes

Packing Bounds for Outer Products with Applications to Compressive Sensing

Semper S., and Hotz T. Geometric Science of Information https://doi.org/10.1007/978-3-030-26980-7_15

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.