Codes and Expansions (CodEx) Seminar

Ram Zamir (Tel Aviv University)
Asymptotic Frame Theory for Analog Coding

Over-complete bases (frames) play the role of analog codes for compression (compressed sensing) and redundant signaling (erasure correction). The spectrum (eigenvalue distribution) of a randomly selected subset of the frame vectors determines the robustness of the code to noisy observations. For the highly symmetric class of equiangular tight frames (ETF), we show that if we keep the frame aspect ratio Gamma and the selection probability P of a frame vector fixed, then the spectrum converges asymptotically to the MANOVA distribution, parametrized by Gamma and P. The asymptotic-probabilistic nature of this result is in sharp contrast to earlier worst-case analysis of frames. Furthermore, we show indications that MANOVA is the best possible subframe spectrum with respect to various performance measures, such as noise enhancement, Shannon capacity, and statistical restricted isometric property. This implies that ETF is the most robust analog code for noisy compressed sensing, non-orthogonal multiple access (NOMA), coded computing and more.

Joint work with Marina Haikin and Matan Gavish.