Foundations and Trends® in Communications and Information Theory > Vol 18 > Issue 4

Asymptotic Frame Theory for Analog Coding

By Marina Haikin, Amazon, Israel, mkokotov@gmail.com | Matan Gavish, The Hebrew University of Jerusalem, Israel, gavish@cs.huji.ac.il | Dustin G. Mixon, The Ohio State University, USA, mixon.23@osu.edu | Ram Zamir, Tel Aviv University, Israel, zamir@eng.tau.ac.il

 
Suggested Citation
Marina Haikin, Matan Gavish, Dustin G. Mixon and Ram Zamir (2021), "Asymptotic Frame Theory for Analog Coding", Foundations and Trends® in Communications and Information Theory: Vol. 18: No. 4, pp 526-645. http://dx.doi.org/10.1561/0100000125

Publication Date: 18 Nov 2021
© 2021 M. Haikin, M. Gavish, D.G. Mixon and R. Zamir
 
Subjects
Coded modulation,  Coding theory and practice,  Data compression,  Information theory and statistics,  Modulation and signal design,  Multiuser detection,  Quantum information processing,  Rate-distortion theory,  Source coding,  Signal processing for communications,  Sparse representations,  Signal processing for communications,  Sampling,  Analog-to-digital conversion,  Coding and compression,  Signal reconstruction,  Digital-to-analog conversion,  Statistical/machine learning,  Statistical signal processing,  Sensors and sensing,  Filtering, estimation and identification,  Estimation methods,  Sensors and estimation,  Dimensionality reduction,  Independent component analysis,  Robustness,  Spectral methods,  Statistical learning theory
 
Keywords
harmonic analysissparse recoverycompressed sensingrestricted isometry propertyframe theorytight framesequiangular tight framescoherencerandom matrix theoryempirical spectral distributionlimit distribution in random matrix theoryconcentrationMarcenko Pastur distributionMANOVA distributionmethod of momentsuniversality in random matrix theoryanalog coding
 

Free Preview:

Download extract

Share

Download article
In this article:
1. Introduction
2. An information-theoretic toy example
3. Sub-frame performance measures
4. Frame theory
5. Random matrix theory
6. Empirical ETF-MANOVA relation
7. Moments of an ETF subset
8. Sub-frame inequalities
9. Applications
10. ETF optimality conjecture
11. Conclusion and discussion
Acknowledgements
Appendices
References

Abstract

Over-complete systems of vectors, or in short, frames, play the role of analog codes in many areas of communication and signal processing. To name a few, spreading sequences for code-division multiple access (CDMA), over-complete representations for multiple-description (MD) source coding, space-time codes, sensing matrices for compressed sensing (CS), and more recently, codes for unreliable distributed computation. In this survey paper we observe an informationtheoretic random-like behavior of frame subsets. Such subframes arise in setups involving erasures (communication), random user activity (multiple access), or sparsity (signal processing), in addition to channel or quantization noise. The goodness of a frame as an analog code is a function of the eigenvalues of a sub-frame, averaged over all subframes (e.g., harmonic mean of the eigenvalues relates to least-square estimation error, while geometric mean to the Shannon transform, and condition number to the restricted isometry property).

Within the highly symmetric class of Equiangular Tight Frames (ETF), as well as other “near ETF” families, we show a universal behavior of the empirical eigenvalue distribution (ESD) of a randomly-selected sub-frame: (i) the ESD is asymptotically indistinguishable from Wachter’s MANOVA distribution; and (ii) it exhibits a convergence rate to this limit that is indistinguishable from that of a matrix sequence drawn from MANOVA (Jacobi) ensembles of corresponding dimensions. Some of these results follow from careful statistical analysis of empirical evidence, and some are proved analytically using random matrix theory arguments of independent interest. The goodness measures of the MANOVA limit distribution are better, in a concrete formal sense, than those of the Marchenko–Pastur distribution at the same aspect ratio, implying that deterministic analog codes are better than random (i.i.d.) analog codes. We further give evidence that the ETF (and near ETF) family is in fact superior to any other frame family in terms of its typical sub-frame goodness.

DOI:10.1561/0100000125
ISBN: 978-1-68083-908-1
137 pp. $90.00
Buy book (pb)
 
ISBN: 978-1-68083-909-8
137 pp. $140.00
Buy E-book (.pdf)
Table of contents:
1. Introduction
2. An information-theoretic toy example
3. Sub-frame performance measures
4. Frame theory
5. Random matrix theory
6. Empirical ETF-MANOVA relation
7. Moments of an ETF subset
8. Sub-frame inequalities
9. Applications
10. ETF optimality conjecture
11. Conclusion and discussion
Acknowledgements
Appendices
References

Asymptotic Frame Theory for Analog Coding

Over the past 2 decades, Frames have become tool in designing signal processing and communication systems where redundancy is a requirement. To name just a few, spreading sequences for code-division multiple access, over-complete representations for multiple-description source coding, space-time codes, sensing matrices for compressed sensing, and more recently, codes for unreliable distributed computation.

In this book the authors develop an information-theoretic characterization for frame subsets. These subframes arise in setups involving erasures (communication), random user activity (multiple access), or sparsity (signal processing), in addition to channel or quantization noise. Working at the intersection of information theory and neighboring disciplines, the authors provide a comprehensive survey for this new development that can drastically improve the performance of codes used in such systems.

The authors begin with an introduction to the underlying mathematical theory, including performance measures, frame theory and random matrix theory. They then proceed with two very important highlights that connect frame theory with random matrix theory and demonstrate the possibility that Equiangular Tight Frames provide superior performance over other classes.

This book provides a concise and in-depth starting point for students, researchers and practitioners working on a variety of communication and signal processing problems.

 
CIT-125