自适应分片稀疏逼近算法的研究

Sparse approximation is a widely studied issue in the field of numerical approximation, computational geometry, image processing, machine learning and so on. Since the sparse structure of vector is not considered, the feasible conditions of the existing sparse approximation algorithms are strict. Piecewise sparsity is defined to study the sparse vectors whose nonzero entries appear in an scattered way. By the piecewise structure, the scope of successfully sparse recovery is enlarged. However, it is remained challenging on the adaptive selection of the optimal piecewise structure of piecewise sparse vector with no prior information. This project plans to complement the theoretical result of piecewise sparse approximation algorithms, by using mutual coherence and promoted conditions to analyze the convergence of algorithms with known piecewise structure. Based on this, research on adaptive piecewise sparse approximation algorithms to be carried out, including characterize the Gram matrix corresponding to the measurement matrix in order to define a function to describe piecewise sparsity, summarize the relation among the exact support recovery conditions under various piecewise structure, develop the piecewise structure optimization model, propose the adaptive piecewise sparse approximation algorithm by alternating iteration and continuation methods. The above research will generate some new piecewise sparse approximation theories and algorithms, which are of great significance for the in-depth study of sparse approximation.

稀疏逼近在数值逼近、计算几何、图像处理、机器学习等领域有广泛的应用。现有的很多稀疏逼近算法因没有考虑向量的稀疏结构，导致相应的算法性能保证条件较为苛刻。而分片稀疏描述的是稀疏向量中非零元素散乱分布的现象，通过对向量分片稀疏结构的分析，可以拓宽算法成功恢复的适用范围。但如何自适应寻找向量的最优分片稀疏结构，是待解决的难题。本项目采用矩阵互相干条件及其推广条件对已知分片结构的分片稀疏逼近算法收敛性进行分析，以完善分片稀疏逼近算法的理论结果，进而开展自适应分片稀疏逼近算法研究。包括：深入研究分片稀疏向量对应分块矩阵的Gram矩阵特性，定义刻画分片稀疏性的函数，并归纳总结不同分片结构下精确支集恢复条件之间的关系，建立分片结构优化模型；通过交替迭代等方法，结合分片结构优化模型和分片稀疏逼近算法，构建自适应分片稀疏逼近算法。上述研究将产生一些新的分片稀疏逼近理论和算法，对深入研究稀疏逼近具有重要意义。

本项目旨在解决建立自适应算法寻找向量的最优分片稀疏结构。本项目采用矩阵互相干条件及其推广条件对已知分片结构的分片稀疏逼近算法收敛性进行分析，以完善分片稀疏逼近算法的理论结果，进而开展自适应分片稀疏逼近算法的研究。 通过本项目研究，我们取得了如下成果：针对分片结构下的分片稀疏逼近算法，将分片稀疏性引入到Bregman逆尺度空间算法(ISS)中,提出一种自适应的分片逆尺度空间(aP_ISS)算法,处理散乱数据的曲面拟合问题;在已有的分片OMP算法的基础上，通过阈值的手段克服实现输入分片稀疏度的缺陷，提出不需要稀疏先验信息的阈值分片OMP(TP_OMP)算法; 通过利用近端算子，提出分片近端梯度下降算法(JPGA）。对于分片稀疏理论的研究中考虑已知分片结构下分片稀疏逼近算法的性能保证条件，从而缩小阈值以及删除准则中参数的范围；通过利用微分方程手段分析分片稀疏算法的收敛性，建立稀疏逼近和微分方程的联系；在曲面拟合、曲面优化上的数值实验再次验证了分片手段的重要性。. 本项目通过将分片稀疏性引入到传统逼近算法进行分析，提出一系列自适应分片稀疏逼近算法，并应用于求解计算几何中的前沿问题。通过“分片”手段从理论和算法上丰富并提升了现有稀疏算法的理论成果。在项目进行过程中，引申出基于最小二乘的稀疏逼近和非线性逼近（如：Relu逼近、相位恢复）的逼近性质分析，后续将深入探索，进一步丰富本项目成果。