Geometric constructions for sparse integer signal recovery

Lenny Fukshansky (Claremont McKenna College)

Jan 18. 2022, 15:00 — 15:40

We investigate the problem of constructing m x d integer matrices with small entries and d large comparing to m so that for all vectors x in Z^d with at most s ≤ m nonzero coordinates the image vector Ax is not 0. Such constructions allow for robust recovery of the original vector x from its image Ax. This problem is motivated by the compressed sensing paradigm and has numerous potential applications ranging from wireless communications to medical imaging. We discuss existence of such matrices for appropriate choices of d as a function of m and demonstrate a deterministic construction of a family of such matrices stemming from a certain geometric covering problem. We also discuss certain limitations of such constructions imposed by some results in the geometry of numbers. This talk is based on joint works with B. Sudakov and D. Needell, as well as with A. Hsu.

Further Information
ESI Boltzmann Lecture Hall
Associated Event:
Optimal Point Configurations on Manifolds (Workshop)
Christine Bachoc (U Bordeaux)
Henry Cohn (Microsoft, Redmond)
Peter Grabner (TU Graz)
Douglas Hardin (Vanderbilt U, Nashville)
Edward Saff (Vanderbilt U, Nashville)
Achill Schürmann (U of Rostock)
Robert Womersley (UNSW, Sydney)