论文标题
约束线性反问题的快速算法
Fast Algorithm for Constrained Linear Inverse Problems
论文作者
论文摘要
我们考虑约束的线性反问题（LIP），其中特定原子范围（例如$ \ ell_1 $ norm）被最小化受二次约束。通常，这种成本功能是不可差异的，这使得它们不适合实践中存在的快速优化方法。我们提出了对约束唇部的两个等效重新进行的，并改善了凸的规律性：（i）平稳的凸最小化问题，以及（ii）强烈凸出的最小值问题。可以通过应用基于加速的凸优化方法来解决这些问题，这些方法提供了更好的$ o \ left（\ frac {1} {k^2} \ right）$理论收敛保证，从而提高了当前$ o \ left（\ frac {1}} {1} {k} {k} \ right）的最佳速率。我们还提供了一种新型算法，称为快速线性反问题求解器（FLIPS），该算法是为了最大程度地利用重新制定的结构而定制的。我们证明了对二进制选择，压缩感应和图像denoising的经典问题的翻转性能。我们还为这三个示例提供了一个开源套件，可以很容易地适应其他嘴唇。
We consider the constrained Linear Inverse Problem (LIP), where a certain atomic norm (like the $\ell_1 $ norm) is minimized subject to a quadratic constraint. Typically, such cost functions are non-differentiable, which makes them not amenable to the fast optimization methods existing in practice. We propose two equivalent reformulations of the constrained LIP with improved convex regularity: (i) a smooth convex minimization problem, and (ii) a strongly convex min-max problem. These problems could be solved by applying existing acceleration-based convex optimization methods which provide better $ O \left( \frac{1}{k^2} \right) $ theoretical convergence guarantee, improving upon the current best rate of $ O \left( \frac{1}{k} \right) $. We also provide a novel algorithm named the Fast Linear Inverse Problem Solver (FLIPS), which is tailored to maximally exploit the structure of the reformulations. We demonstrate the performance of FLIPS on the classical problems of Binary Selection, Compressed Sensing, and Image Denoising. We also provide an open-source package for these three examples, which can be easily adapted to other LIPs.
