迭代式正交匹配追踪及稀疏解

Iterative Orthogonal Matching Pursuit and Sparse Solution

欠定线性方程组Ax=y的稀疏求解算法是稀疏表示与压缩感知中的研究热点,包括最小化L0拟范数与L1范数及迭代式阈值的方法.介绍一类最小化L0拟范数的方法,即迭代式正交匹配追踪,剖析并证明其基坐标迭代更新框架,介绍三种迭代式算法包括Hermite逆迭代,cholesky与QR迭代分解.迭代式算法的特点避免了逐步求逆运算,从而提高了计算速度.介绍正交匹配追踪获取稀疏解的性质.压缩感知实验表明迭代式正交匹配追踪可快速稳定地求取欠定系统的稀疏解.

The Algorithm for finding sparse solution of under-determined linear system is a hot topic in sparse representation and compressive sensing. It covers methods of minimizing L0 quasi-norm, L1 norm and iterative thresholding. A class of algorithm for minimizing L0 quasi-norm, namely iterative orthogonal matching pursuit（OMP） is introduced and its framework for iteratively updating base coordinates are analyzed and proved. Three iterative method are presented, including hermitian inverse update, cholesky and QR decomposition update. Iterative method avoid direct computing of matrix inverse at each step therefore improve the speed. Property of fast recovering sparse solution by OMP are introduced. Experiments on compressive sensing demonstrated that iterative OMP is stable and fast on finding sparse solution of under-determined linear system.