Inexact Gradient Projection and Fast Data Driven Compressed Sensing
Inexact Gradient Projection and Fast Data Driven Compressed Sensing
复制标题
DOI：
10.1109/tit.2018.2841379
复制
发表时间：
2017-05
影响因子：
2.5
通讯作者：
Mohammad Golbabaee;M. Davies
中科院分区：
文献类型：
--
作者：
Mohammad Golbabaee;M. Davies
研究了任意(可能非凸)集的迭代投影梯度(IPG)算法在近似计算梯度和投影预言机时的收敛问题。我们考虑了不同的逼近概念，我们证明了渐进固定精度和$(1+\varepsilon)$-最优预言可以获得与精确IPG算法相同的精度。我们证明了在相同的嵌入假设下，前者也能够保持精确算法的(线性)收敛速度。相比之下，$(1+\varepsilon)$-近似预言需要更强的嵌入条件、适度的压缩比，并且它通常会减慢收敛速度。我们将我们的结果应用于加速求解一类数据驱动的压缩感知问题，其中我们用基于覆盖树数据结构的快速近似最近邻搜索策略来代替对大数据集的迭代穷举搜索。对于内禀维度较低的数据集，我们提出的算法实现了关于数据集总体的复杂性对数，而不是蛮力搜索的线性复杂性。通过几个数值实验，我们得出了与我们的理论分析所预测的类似的观测结果。
We study the convergence of the iterative projected gradient (IPG) algorithm for arbitrary (possibly non-convex) sets when both the gradient and projection oracles are computed approximately. We consider different notions of approximation of which we show that the progressive fixed precision and the $(1+ \varepsilon)$ -optimal oracles can achieve the same accuracy as for the exact IPG algorithm. We show that the former scheme is also able to maintain the (linear) rate of convergence of the exact algorithm under the same embedding assumption. In contrast, the $(1+ \varepsilon)$ -approximate oracle requires a stronger embedding condition, moderate compression ratios and it typically slows down the convergence. We apply our results to accelerate solving a class of data driven compressed sensing problems, where we replace iterative exhaustive searches over large data sets by fast approximate nearest neighbor search strategies based on the cover tree data structure. For data sets with low intrinsic dimensions, our proposed algorithm achieves a complexity logarithmic in terms of the data set population as opposed to the linear complexity of a brute force search. By running several numerical experiments, we conclude similar observations as predicted by our theoretical analysis.