标题： 快速准确的重加权L1范数最小化算法 显示英文标题

标题： Fast and Accurate Algorithms for Re-Weighted L1-Norm Minimization

摘要： 为了从欠定系统中恢复稀疏信号，我们通常会求解一个约束的L1范数最小化问题。在许多情况下，通过用“加权”的L1范数替换L1范数，可以进一步提高信号的稀疏性和恢复性能。如果没有关于信号非零元素的先验信息，权重的选择过程本质上是迭代的。常见的方法是在每次迭代中使用上一次迭代的加权L1问题的解来更新权重。本文提出了两种基于同伦的算法，高效地解决重加权的L1问题。首先，我们提出了一种算法，能够快速更新加权L1问题的解，当权重发生变化时。由于随着权重的小幅变化，解的变化也较小，我们开发了一种同伦算法，在少量计算开销较小的步骤中替换旧的权重和新的权重。其次，我们提出了一种算法，在估计信号的同时自适应地选择权重。该算法通过改变权重来适应解及其支持的变化，沿同伦路径在每一步集成重新加权，从而通过求解单一的同伦问题实现高质量的信号重建。我们将这两种算法的重建精度和计算复杂度与最先进的求解器进行比较，并表明我们的方法具有更小的计算成本。此外，我们将展示在同伦内部自适应选择权重通常会产生更高质量的重建。 显示英文摘要

摘要： To recover a sparse signal from an underdetermined system, we often solve a constrained L1-norm minimization problem. In many cases, the signal sparsity and the recovery performance can be further improved by replacing the L1 norm with a "weighted" L1 norm. Without any prior information about nonzero elements of the signal, the procedure for selecting weights is iterative in nature. Common approaches update the weights at every iteration using the solution of a weighted L1 problem from the previous iteration. In this paper, we present two homotopy-based algorithms that efficiently solve reweighted L1 problems. First, we present an algorithm that quickly updates the solution of a weighted L1 problem as the weights change. Since the solution changes only slightly with small changes in the weights, we develop a homotopy algorithm that replaces the old weights with the new ones in a small number of computationally inexpensive steps. Second, we propose an algorithm that solves a weighted L1 problem by adaptively selecting the weights while estimating the signal. This algorithm integrates the reweighting into every step along the homotopy path by changing the weights according to the changes in the solution and its support, allowing us to achieve a high quality signal reconstruction by solving a single homotopy problem. We compare the performance of both algorithms, in terms of reconstruction accuracy and computational complexity, against state-of-the-art solvers and show that our methods have smaller computational cost. In addition, we will show that the adaptive selection of the weights inside the homotopy often yields reconstructions of higher quality.