这是Chatterjee在IEEE TSP（2012）上的一篇文章，讲的是原子选择里的事情。bibtex信息如下：@article{chatterjee2012projection,title={Projection-Based and Look-Ahead Strategies for Atom Selection}， author={Chatterjee, S. and Sundman, D. and Vehkapera, M. and Skoglund, M.}, journal={Signal Processing, IEEE Transactions on}, volume={60}, number={2}, pages={634--647}, year={2012}, publisher={IEEE}}
摘要信息如下：In this paper, we improve iterative greedy search algorithms in which atoms are selected serially over iterations, i.e., one-by-one over iterations. For serialatom selection,we devise two new schemes to select an atom from a set of potential atoms in eachiteration. The two new schemes lead to two new algorithms. For both the algorithms, in each iteration, the set of potential atoms is found using a standard matched filter. In case of the first scheme, we propose an orthogonal projection strategy that selects an atom from the set of potential atoms. Then, for the second scheme, we propose a look-ahead strategy such that the selection of an atom in the current iteration has an effect on the future iterations. The use of look-ahead strategy requires a higher computational resource. To achieve a tradeoff between performance and complexity, we use the two new schemes in cascade and develop a third new algorithm. Through experimental evaluations, we compare the proposed algorithms with existing greedy search and convex relaxation algorithms.
首先回顾一些知识。在压缩感知或者稀疏恢复算法里面，迭代阈值算法(Iterative thresholding algorithm)和贪婪算法(greedy algorithm)是两大类比较重要也比较实际的算法。迭代阈值算法包括：迭代硬阈值(IHT以及变型NIHT,AIHT等)，迭代软阈值(IST)，迭代阈值追踪(TSP)，迭代阈值倒转(IST)等方法，迭代的每一步算法框架=梯度下降+稀疏算子+进一步化措施。这一类算法最大的好处就是，计算复杂度低，尤其是前两个，后两个因为其中涉及到最小二乘，计算复杂度增加；坏处是当字典或者观测矩阵相关度强的时候，这些算法恢复的效果（前两个）大打折扣。贪婪算法包括匹配追踪(MP)，正交匹配追踪(OMP以及变型ROMP，MOMP等)，压缩采样匹配追踪(CoSaMP)等，迭代的每一步主要框架为=选取原子和残差较大相关的下标并激活(可以理解为梯度分量最大，可能最小二乘优化选择)+新支集上观测值最小二乘法投影更新残差。在低维数情况下，这种贪婪算法效果极好。在高维数下，由于计算量的原因，不占优势。另一方面正交最小二乘法（OLS）讨论过OMP的一个弊端，就是当字典里存在相似原子时，OMP在无法考虑到当前步对之后的影响从而选错，而OMP的正交性质导致这个错误无法修正。
这篇文章提供了一种思路，就是Look Ahead，算是OMP和OLS的一种结合。文章首先说明了在贪婪算法里进行原子选择时候单用梯度（选残差相关最大下标）的好（字典正交的时候巨好），也说了单用梯度的坏（在字典相关时候就差一些），于是点出了最小二乘（投影projection）的好（一定程度）。同时针对OMP的问题，它摆出了一个能干活的诸葛亮（会预测未来look ahead），在选择新下标的时候，他不惜余力的把这一步的每一个方案对最终残差的影响进行了计算（实际上在每选一个原子时进行了一次完整的OMP或者类似的HTP，然后对这些结果进行比较评估，选最好的（使得残差最小）进来。这个事情是比较自然的，它的代价就是诸葛的劳累，计算复杂度太大。于是作者在最后提出了一些折中的办法，或者通过一些计算方面的技巧进行优化。
文章的一个问题是：缺乏收敛性分析。