L-CAMP: Extremely Local High-Performance Wavelet Representations in High Spatial Dimension

University Of Wisconsin-Madison, Madison WI

Investigators

Abstract

+The mathematical development of wavelet theory and the accompanied computational algorithms reached a mature, satisfactory, level in one dimension. The situation is far less satisfactory in higher dimensions. As a matter of fact, the current approaches for the construction of high-D wavelet representations scale poorly with the dimension. On the one hand, intrinsic constructions become hopelessly complicated already at relatively low dimensions. On the other hand, the simple approach of lifting univariate systems to higher dimensions becomes eventually immensely non-local. As a result, the construction of effective, efficient, wavelet representations in high dimensions remains a major challenge and an elusive target. The premise of this proposal is that the only way to meet this challenge is to fundamentally change the principles of wavelet constructions. The ambitious goal of this project is to develop representations that scale correctly with the spatial dimension: constants in the complexity estimates of the algorithms that are independent of the dimension; linear functionals that have limited, controlled, overlapping in their supports; and performance grade that does not degrade with the growth of the dimension. The project is expected to contribute in tangible ways to NSF's broad criteria. This is first and foremost due to the intrinsic importance of the research area, and the fact that the problem attacked in this project is a major hurdle in the relevant research area. In addition, the initiative offers a highly valuable training and education opportunity to mathematical science students, education in areas that are at the interface between mathematics on the one hand and science and technology on the other hand. Our era is marked by breathtaking improvement in sensor acquisition capabilities and an explosive increase in communication over wired and wireless channels. As a result of these and similar trends, the correct handling of massive datasets is, these days, at the core of almost every technology that deals with scientific data. The most fundamental issue in this regard is the fact that the size of the dataset is merely an artifact of the acquisition technology; it is not related to pertinent information that the data encode, nor to the actual applications that are sought for. Data representation is the scientific discipline that deals with challenges like the above. It resolves the above problem by transforming the data into a new format which allows an efficient and effective extraction of information, storage, transmission, and the like. There is probably no way to overstate the importance of research on data representation: Development of novel data representations is ranked among the top scientific priorities of our nation. Indeed, the innovators in this field are richly recognized for their contributions: even after restricting attention only to research on the mathematical and statistical aspects of data representation, one finds, in the last eight years alone, two Medal of Science awards, as well as five or more elections to the National Academy of Science. The wavelet representation is among the most important contributions of the data representation community to science. It was introduced in order to provide an answer to the main shortcoming of the Fourier representation, i.e., the fact that the latter never provides a sparse representation to transient events. The research community succeeded in constructing very good wavelet representations in 1D. Those systems are computed and inverted by fast algorithms and strike as good balance as can be between performance and localness. The same it not true in high spatial dimensions. Armed with that observation, the intent of this ambitious project is to develop novel classes of wavelet representations that are efficient and effective in high dimensions.