图上的小波框架：理论与应用

In numerous applications, data to be analyzed usually has complicated interconnections and irregular structures. Graphs provide a generic representation for such data. Classical wavelet transforms, which is a powerful tool for analyzing signals and images lying on Euclidean spaces, cannot be directly applied for processing data on graphs. This project will focus on the theory and applications of wavelet frames on graphs. We will give the notion of shift, convolution, up/down-sampling operators and other key ingredients of wavelet transforms. Based on these key ingredients, we discuss the spectral domain analysis, filter design and sampling theorem for bandlimited signals to develop signal processing on graphs. Besides, we will build up wavelet transforms on graphs with multiresolution analysis, and discuss their frame properties. In addition, we will consider potential signal processing applications of the proposed wavelet frames on graphs, especially denoising of graph signals and image denoising based on graphs. Regularization models and efficient algorithms will be designed for both types of denoising tasks. The problems involved in this project are of great importance in fields like signal processing and machine learning, which shall open a broad space in industry applications. The applicant has solid background in wavelet frame theory and image processing and is expected to achieve great progress in this area.

许多实际问题中，所要分析的数据具有复杂的内部关联，图为这种结构的数据提供一种通用表示。经典小波变换是分析欧式空间中信号和图像的有力工具，但不适宜直接应用于处理这类具有图结构的数据。在本项目中，我们将开展图上小波框架理论和应用的研究工作。我们将建立图的位移、卷积、上/下采样算子等与小波系统相关的关键概念，讨论图上的频谱域分析、滤波器设计、有限带宽信号采样定理等问题，建立图信号处理理论；我们将构建图上的具有多分辨率分析结构的小波系统，并研究其框架性质；我们将利用图上的小波框架，解决图信号处理的实际应用问题，特别地考虑图信号去噪和基于图的图像去噪，建立正则化模型和设计有效数值算法。这些问题的解决将为信号处理和机器学习等领域提供更有效的工具，具有广阔的工业应用前景。项目申请人在小波框架理论与图像处理方面有很好的基础，有望在所提出的问题上取得实质性的进展。

图结构数据在很多场景中广泛存在。本项目研究了图上小波框架的构造。根据图的空间特征和频谱域特征，定义了图信号处理的基本算子，如位移算子、卷积算子、上（下）采样算子等。将卷积定理、采样定理等推广到了图上，建立了图上信号处理理论。在此基础之上，定义了图上的下采样小波系统。但对于一般的图来说，即便是考虑单层下采样小波系统，仍然很难拥有支撑集较小的滤波器组满足框架构造所需的充要条件。同时，本项目定义了图上的平移不变小波系统，给出了使这类系统成为（紧）框架的充分条件。这一条件易于满足，简化了平移不变小波（紧）框架的构造。已构造的平移不变小波紧框架具有较好的时-频域局部性和多尺度性质，可对分片常值图信号提供具有重建鲁棒性的稀疏表示。将已构造小波框架应用于硬阈值图信号去噪方法，取得了较显著的降噪效果。本项目所提出的图上小波框架能为图信号分析与恢复等问题提供有力工具。此外，本项目研究了非凸正则化模型的求解算法及其收敛性分析。对于基于lp准范数的非凸正则化模型，提出了求解的加速算法并证明其收敛性。对于带有非Lipschitz各向异性复合正则化项的模型，建立了其下界理论和支集包含分析，并提出了有收敛性保证的求解算法。这些算法计算高效，不仅可用于解决与经典信号和图像相关的实际问题，也为更好地解决图信号处理问题打下了基础。