Structured Random Matrices and Graphs in Signal Processing

University Of California-Los Angeles, Los Angeles CA

Investigators

Abstract

Recent advances in science and technology allow us to collect and require us to process large volumes of data of different types, ranging from routine user information collected by electronic devises, such as geotags, to more structurally complicated data obtained as a result of scientific experiments and biomedical imaging. Solving the associated signal processing problems requires an understanding of the underlying structure of data and finding its efficient representations. Frames proved to be a powerful tool in signal processing, providing redundant representations of signals that are useful for many applications. In return, signal processing problems motivate the study of frame properties. The primary objective of the project is to study connections between frame theory, with focus on time-frequency analysis, and signal processing problems, such as the phase retrieval problem, where a signal is reconstructed from intensity measurements with respect to a frame. More precisely, the investigator aims to study geometric properties of Gabor frames and their role in analysis of the phase retrieval problem with time-frequency structured measurements. Gabor frames naturally arise in such applications as speech recognition, so obtaining results on phase retrieval problem with time-frequency structured measurements would lead to advances in speech recognition technology and provable guarantees for existing ad hoc methods. In many signal processing applications, including social, transport, and epidemiology networks, data is naturally associated with the vertices of a weighted graph that represents the relations between data units. Processing of such data requires the development of different signal processing tools that would take the underlying graph structure into account. Another aim of the project is to extend classical discrete signal processing tools and concepts to signals defined on graphs. This would allow to solve classical signal processing problems in this generalized setting and advance in such important applications as weather and traffic prediction and brain imaging. The project is centered around three main objectives that are closely connected to each other, each addressing an important problem in the areas of random matrix theory, Gabor analysis, and signal processing. The first research direction is devoted to the study of geometric properties of frames. While properties of random Gaussian frames with independent vectors are sufficiently well-studied, very little is known about structured frames that are relevant for signal processing applications. This motivates the study of structured application relevant frames, such as Gabor frames. The investigator will focus on such properties of Gabor frames as optimal frame bounds and frame order statistics, with the ultimate goal of showing that Gabor frames have properties that are essentially optimal for applications. The study of the optimal frame bounds would allow to establish robustness of the signal reconstruction from its frame coefficients, justifying the use of the frame representation of a signal in practical applications. In the case of Gabor frames, the frame bounds depend not only on the cardinality of the frame set, but also on its structure. In the second research direction, the investigator aims to use studied properties of frames to analyze the phase retrieval problem. Even though there are many results on phase retrieval obtained for Gaussian measurements, the case of structured frames remains wide open. The main reason for this is that geometric properties of such frames are not yet fully understood. Getting new insights into the properties of Gabor frames would lead to a substantial progress in the development of the phase retrieval problem. In particular, obtaining uniform bounds on frame order statistics would imply invertibility and stability of the phase retrieval problem with Gabor frames. The third research direction of the project focuses on various aspects of time-frequency analysis for graph-based signals. The two main goals are to describe graphs for which Gabor frames have properties similar to the classical case, and to study properties of graph Gabor frames, depending on the underlying graph structure. To achieve the latter goal, the investigator aims to use random graph theory. The generalization of such cornerstone concepts as uncertainty principle and restricted isometry property would allow to develop Gabor analysis toolbox for graph-based signals and approach classical signal processing problems in this more general setting. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.