Approximately Hadamard matrices and random frames

Abstract: An n by n matrix with plus-minus 1 entries which acts as a scaled isometry is called Hadamard. Such matrices exist in some, but not all dimensions. Combining number-theoretic and probabilistic tools we construct matrices with plus-minus 1 entries which act as approximate scaled isometries for all n. More precisely, the matrices we construct have condition numbers bounded by a constant independent of the dimension. We will also discuss an application in signal processing. A frame is an overcomplete set of vectors which allows a robust decomposition of any vector in the space as a linear combination of these vectors. Frames are used in signal processing since the loss of a fraction of coordinates does not prevent the recovery of the signal. We will discuss a question when a random frame contains a copy of a nice basis. Joint work with Xiaoyu Dong.

mathematical physicscombinatoricsprobabilitystatistics theory

Audience: researchers in the topic

Abu Dhabi Stochastics Seminar