Flexible and Sound Computational Harmonic Analysis Tools for Graphs and Networks

点击翻译按钮获取中文摘要

In recent years, the field of data analysis on graphs and networks is experiencing rapid growth due to a confluence of several trends in science and technology: the advent of new sensors and social network infrastructure, together with the availability of low-cost computing devices, has ignited an explosion in research and development activities in both academia and industry. It has become a pressing issue to develop more flexible yet mathematically sound tools for graph data analysis. The algorithms and software tools to be developed will make a positive impact in solving practical data analysis problems on graphs and networks in diverse fields, e.g., biology and medicine (analyzing data measured on neuronal networks); computer science (analyzing friendship relations in social networks); electrical engineering (monitoring and controlling sensor networks); geology (measuring stream flows in a ramified river network); and civil engineering (monitoring traffic flow on a road network), to name a few. Moreover, those algorithms and software tools will be highly useful for data in conventional formats such as usual digital signals and images. This is because those tools can treat the conventional data as graphs, consequently can extract signal features that are not readily accessible by conventional methods. Students engaged in this project will be trained to be the next generation of interdisciplinary scientists who have deep knowledge in one area yet have open mind to the other areas and try to actively seek collaborations with domain experts (such as neuroscientists or civil engineers). The proposed project will also bring in the insights gained by the experience of the PI in the different fields: image analysis; scientific computing; statistical signal processing; computational neuroscience; and harmonic analysis. These students will gain broad perspectives, which will be helpful for their future career, either in academia or in industry.The goal of this project is to develop flexible and sound computational harmonic analysis tools for analyzing data recorded on graphs and networks and demonstrate their usefulness on a variety of applications. The PI team has developed such a tool, called the Generalized Haar-Walsh Transform (GHWT), which completely lifted the conventional Haar-Walsh wavelet packet transform from the regular lattice setting to the much more general graph setting. Yet, that is not enough. The proposed project will extend the GHWT to make it more flexible and adaptive to graph data of interest. In particular, the PI team will develop the extended GHWT (eGHWT) and the associated best-basis selection algorithm for graphs that will significantly improve the previous GHWT with the similar computational cost, and apply it to important problems ranging from simultaneous image segmentation and compression to matrix data analysis. The PI team will also investigate what would be the natural dual domain of a given graph and how one could build a sound graph wavelet theory and generate smooth multiscale basis dictionaries on graphs. This part begins with the idea of defining a multiscale metric between any two eigenvectors of the graph Laplacian matrix of an input graph. Then, the project will construct the natural dual domain of the graph, i.e., a low dimensional Euclidean space where those eigenvectors are embedded using that metric (like the Fourier domain lattice for the regular spatial lattice case). Once this is done, it should be able to build natural and sound wavelets and multiscale basis dictionaries on that graph by appropriately grouping and clustering the eigenvectors in the dual domain in a similar manner to how the conventional Littlewood-Paley theory organizes the sinusoids in the regular lattice case.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.