分片稀疏逼近的理论及算法

Sparse approximation or sparse representation have many important applications in signal processing, numerical approximation and computational geometry. Sparse approximation is to find the optimal solution by adding the redundancy of the dictionary of the approximation space while possessing good accuracy. In many researches, the matrix of the dictionary has block structures, corresponding to the piecewise sparsity of the solution vector. In this project, we will study the theories and algorithms of approximation or recovery of piecewise sparse vectors, based on the block structure of the matrix. It mainly includes the following aspects. (1) Based on the block structure of the matrix, to improve the upper bound of the sparsity of the solution vector in the conditions of the uniqueness of the sparse recovery problem or the feasibility of various algorithms respectively, and to improve the stability conditions and error estimations of the algorithms. (2) Different from the block-sparsity of vectors, we focus on the approximation theories and algorithms based on the piecewise sparsity of vectors, and discuss the relations between the two kinds of sparsities. (3) Combine the theories and algorithms of piecewise sparse approximation with the multi-level spline spaces, we study the sparse approximation method based on the multi-level spline spaces. To solve the new problems in computational geometry by the new method of local refinable splines.

稀疏逼近或稀疏表示在信号处理，数值逼近、计算几何等领域有很多重要的应用。稀疏逼近通过增加逼近空间中字典的冗余性，在保持逼近精度的同时，寻找最优化的逼近表示。在很多研究中，字典形成的系数矩阵具有分块结构特征，对应解向量具有分片的稀疏性。本项目将利用矩阵的分块结构特征，开展分片稀疏向量的逼近或恢复问题的理论及算法研究。主要内容包括:（1）基于矩阵分块特征，改进稀疏恢复问题的解唯一性条件以及不同求解算法可行性条件中，关于解向量稀疏度的上界估计，以及改善算法的稳定性条件和误差估计。（2）区别于现有基于向量“块稀疏度”的稀疏恢复问题，研究基于向量“分片稀疏度”的稀疏恢复问题的理论和算法，以及两种不同稀疏性之间的联系。（3）将分片稀疏逼近的理论和算法与多层样条空间理论结合，研究基于多层样条空间的稀疏逼近方法，获得新的可局部加细样条逼近和表示方法，并应用于求解计算几何中的前沿问题。

本项目围绕分片稀疏逼近的理论和算法以及稀疏逼近与多元样条方法相结合在数值逼近以及有限元方法中的应用开展研究工作，取得一系列研究成果。.（1）分片稀疏恢复的理论及算法研究方面，分别对无噪音和有噪音的情况研究了分片稀疏恢复的理论可行性条件，获得了由分片信号特征与采样矩阵列相干条件刻画的可恢复信号的稀疏度上界；结合分片稀疏性对一些常用的稀疏恢复算法进行改进，包括分片正交匹配追踪（P_OMP）算法以及改进的自适应的分片稀疏逼近阈值分片OMP算法（记为TP_OMP），分片Bregman逆尺度空间（P_ISS）算法，以及自适应稀疏恢复匹配追踪算法的研究。.（2）稀疏逼近与多元样条方法相结合在数值逼近以及有限元方法中的应用方面，提出了散乱数据拟合的自适应分片逆尺度空间算法；基于分层T网格上的分片孔斯插值算法；基于分片稀疏逼近的散乱点曲面拟合算法；并利用稀疏逼近的想法开展了多元样条在有限元方法中的应用研究。.在项目执行期间，在Journal of Computational Mathematics，Int. J. Appl. Math. Comput. Sci.,，Comput. Methods Appl. Mech. Engrg.，Int J Numer Methods Eng.，Computational and Applied Mathematics，Computers and Mathematics with Applications，J. Math. Res. Exposition 等高水平期刊共发表14篇论文及1篇会议论文，其中SCI检索8篇，EI检索6篇。培养并已毕业3名博士研究生和5名硕士研究生，1名博士研究生在读。