论文标题
通过贪婪的蒙特卡洛搜索重建稀疏信号
Reconstructing Sparse Signals via Greedy Monte-Carlo Search
论文作者
论文摘要
我们提出了一种基于蒙特 - 卡洛的方法，用于在高维环境中稀疏线性回归中重建稀疏信号。该算法的基本思想是明确选择变量或协变量来表示给定的数据向量或响应，并在且仅当能量或成本函数降低时接受该选择的随机更新。该算法称为贪婪的蒙特卡洛（GMC）搜索算法。通过数值实验对其性能进行了检查，这表明在无噪声的情况下，GMC可以在合理水平的底漆情况下实现完美的重建：它可以优于$ \ ell_1 $放松，但不能达到MC基于MC的算法限制的基于MC基于MC的限制。还检查了必要的计算时间，并将使用模拟退火与算法进行比较。此外，关于嘈杂情况的实验是在合成数据集和现实数据集上进行的，支持GMC的实用性。
We propose a Monte-Carlo-based method for reconstructing sparse signals in the formulation of sparse linear regression in a high-dimensional setting. The basic idea of this algorithm is to explicitly select variables or covariates to represent a given data vector or responses and accept randomly generated updates of that selection if and only if the energy or cost function decreases. This algorithm is called the greedy Monte-Carlo (GMC) search algorithm. Its performance is examined via numerical experiments, which suggests that in the noiseless case, GMC can achieve perfect reconstruction in undersampling situations of a reasonable level: it can outperform the $\ell_1$ relaxation but does not reach the algorithmic limit of MC-based methods theoretically clarified by an earlier analysis. The necessary computational time is also examined and compared with that of an algorithm using simulated annealing. Additionally, experiments on the noisy case are conducted on synthetic datasets and on a real-world dataset, supporting the practicality of GMC.
