Random Subsets of Structured Deterministic Frames have MANOVA Spectra

MaRDI QIDQ4646186zbMATH OpenFDO

Authors Marina Haikin, Ram Zamir, Matan Gavish

Publication date 11 January 2019

Full work available at URL https://arxiv.org/abs/1701.01211

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Random matrices (probabilistic aspects) (60B20)

Abstract: We draw a random subset of $k$ rows from a frame with $n$ rows (vectors) and $m$ columns (dimensions), where $k$ and $m$ are proportional to $n$. For a variety of important deterministic equiangular tight frames (ETFs) and tight non-ETF frames, we consider the distribution of singular values of the $k$-subset matrix. We observe that for large $n$ they can be precisely described by a known probability distribution -- Wachter's MANOVA spectral distribution, a phenomenon that was previously known only for two types of random frames. In terms of convergence to this limit, the $k$-subset matrix from all these frames is shown to be empirically indistinguishable from the classical MANOVA (Jacobi) random matrix ensemble. Thus empirically the MANOVA ensemble offers a universal description of the spectra of randomly selected $k$-subframes, even those taken from deterministic frames. The same universality phenomena is shown to hold for notable random frames as well. This description enables exact calculations of properties of solutions for systems of linear equations based on a random choice of $k$ frame vectors out of $n$ possible vectors, and has a variety of implications for erasure coding, compressed sensing, and sparse recovery. When the aspect ratio $m/n$ is small, the MANOVA spectrum tends to the well known Marcenko-Pastur distribution of the singular values of a Gaussian matrix, in agreement with previous work on highly redundant frames. Our results are empirical, but they are exhaustive, precise and fully reproducible.

Recommendations

• Kesten-McKay law for random subensembles of Paley equiangular tight frames
• Randomized subspace actions and fusion frames
• Spectral theory for random closed sets and estimating the covariance via frequency space
• Randomized continuous frames in time-frequency analysis
• Random matrices and erasure robust frames
• Spectral decomposition of random fields defined over the generalized Cantor set
• Frame properties of low autocorrelation random sequences
• Random Menshov spectra
• A class of structured frames in finite dimensional Hilbert spaces
• The incidence structure of subspaces with well-scaled frames

Cited in

(5)

• Frame properties of low autocorrelation random sequences
• Derandomized compressed sensing with nonuniform guarantees for _1 recovery
• Kesten-McKay law for random subensembles of Paley equiangular tight frames
• Spectral Pseudorandomness and the Road to Improved Clique Number Bounds for Paley Graphs
• Asymptotic frame theory for analog coding

This page was built for publication: Random Subsets of Structured Deterministic Frames have MANOVA Spectra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4646186)