Fast Algorithm for Constrained Linear Inverse Problems
M.R. Sheriff (TU Delft - Team Peyman Mohajerin Esfahani)
Floor Fenne Redel (Student TU Delft)
P. Mohajerin Esfahani (TU Delft - Team Peyman Mohajerin Esfahani)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
We consider the constrained Linear Inverse Problem (LIP), where a certain atomic norm (like the `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 Op1{k2q theoretical convergence guarantee, improving upon the current best rate of Op1{kq. 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 open source MATLAB and PYTHON package for these three examples, which can be easily adapted to other LIPs.
help_outline