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

小波理论的数学发展及其伴随的计算算法在一维上达到了成熟的、令人满意的水平。事实上，目前构造高维小波表示的方法都不能很好地适应高维的情况。一方面，内在结构已经在相对较低的维度变得无可救药地复杂。另一方面，将单变量系统提升到更高维度的简单方法最终变得非常非局部性。因此，构造有效、高效的高维小波表示仍然是一个主要的挑战和难以实现的目标。这一提议的前提是，迎接这一挑战的唯一途径是从根本上改变小波构造的原理。这个项目雄心勃勃的目标是开发与空间维度正确缩放的表示：独立于维度的算法的复杂性估计中的常量；其支持度有限、可控、重叠的线性泛函；以及不随维度的增长而降级的性能等级。预计该项目将以切实的方式为NSF的广泛标准做出贡献。这首先是由于研究领域的内在重要性，以及该项目所攻击的问题是相关研究领域的主要障碍。此外，该倡议还为数学专业的学生提供了非常有价值的培训和教育机会，一方面是在数学和科学技术之间的领域，另一方面是在数学和科学技术之间的教育。我们这个时代的标志是传感器获取能力的惊人提高，以及有线和无线信道上的通信的爆炸性增长。由于这些和类似的趋势，这些天来，对海量数据集的正确处理成为几乎所有处理科学数据的技术的核心。在这方面，最根本的问题是，数据集的大小仅仅是采集技术的产物；它与数据编码的相关信息无关，也与所寻求的实际应用无关。数据表示是应对上述挑战的科学学科。它通过将数据转换成一种新的格式来解决上述问题，该新格式允许对信息、存储、传输等进行高效和有效的提取。很可能不能夸大数据表示的研究的重要性：开发新的数据表示被列为我国最重要的科学优先事项之一。事实上，这一领域的创新者因他们的贡献而备受认可：即使只将注意力限制在数据表示的数学和统计方面的研究之后，人们仍然发现，仅在过去八年里，就有两个科学奖章获得者，以及五次或更多的国家科学院选举。小波表示是数据表示界对科学最重要的贡献之一。它的引入是为了回答傅立叶表示法的主要缺点，即后者从未为瞬时事件提供稀疏表示这一事实。研究界成功地构建了非常好的一维小波表示。这些系统通过快速算法进行计算和转换，并尽可能在性能和局部性之间取得良好的平衡。同样，在高空间维度，情况并非如此。有了这一观察，这个雄心勃勃的项目的目的是开发在高维中高效和有效的新型小波表示法。

+The mathematical development of wavelet theory and the accompaniedcomputational algorithms reached a mature, satisfactory, level in onedimension. The situation is far less satisfactory in higher dimensions.As a matter of fact, the current approaches for the construction of high-Dwavelet representations scale poorly with the dimension. On the one hand,intrinsic constructions become hopelessly complicated already at relativelylow dimensions. On the other hand, the simple approach of liftingunivariate systems to higher dimensions becomes eventually immenselynon-local. As a result, the construction of effective, efficient, waveletrepresentations in high dimensions remains a major challenge and an elusivetarget. The premise of this proposal is that the only way to meet thischallenge is to fundamentally change the principles of waveletconstructions. The ambitious goal of this project is to developrepresentations that scale correctly with the spatial dimension: constantsin the complexity estimates of the algorithms that are independent of thedimension; linear functionals that have limited, controlled, overlapping intheir supports; and performance grade that does not degrade with the growthof the dimension. The project is expected to contribute in tangible ways toNSF's broad criteria. This is first and foremost due to the intrinsicimportance of the research area, and the fact that the problem attacked inthis project is a major hurdle in the relevant research area. In addition,the initiative offers a highly valuable training and education opportunityto mathematical science students, education in areas that are at theinterface between mathematics on the one hand and science and technology onthe other hand.Our era is marked by breathtaking improvement in sensor acquisitioncapabilities and an explosive increase in communication over wired andwireless channels. As a result of these and similar trends, the correcthandling of massive datasets is, these days, at the core of almost everytechnology that deals with scientific data. The most fundamental issue inthis regard is the fact that the size of the dataset is merely an artifactof the acquisition technology; it is not related to pertinent informationthat the data encode, nor to the actual applications that are sought for.Data representation is the scientific discipline that deals with challengeslike the above. It resolves the above problem by transforming the data intoa new format which allows an efficient and effective extraction ofinformation, storage, transmission, and the like. There is probably no wayto overstate the importance of research on data representation: Developmentof novel data representations is ranked among the top scientific prioritiesof our nation. Indeed, the innovators in this field are richly recognizedfor their contributions: even after restricting attention only to researchon the mathematical and statistical aspects of data representation, onefinds, in the last eight years alone, two Medal of Science awards, as wellas five or more elections to the National Academy of Science. The waveletrepresentation is among the most important contributions of the datarepresentation community to science. It was introduced in order to providean answer to the main shortcoming of the Fourier representation, i.e., thefact that the latter never provides a sparse representation to transientevents. The research community succeeded in constructing very good waveletrepresentations in 1D. Those systems are computed and inverted by fastalgorithms and strike as good balance as can be between performance andlocalness. The same it not true in high spatial dimensions. Armed withthat observation, the intent of this ambitious project is to develop novelclasses of wavelet representations that are efficient and effective in highdimensions.