Relax-and-split method for nonconvex inverse problems. (2nd September 2020)

• Record Type: Journal Article
• Authors: Zheng, Peng; Aravkin, Aleksandr
• Is Part Of: Inverse problems. Volume 36:Number 9(2020)
• Publication Date: 2020-09-02
• Subjects: nonconvex optimization -- nonsmooth models -- splitting methods; Inverse problems (Differential equations) -- Periodicals; 515.357
• DOI: 10.1088/1361-6420/aba417
• Languages: English
• ISSNs: 0266-5611

Abstract

Abstract: We develop and analyze a new 'relax-and-split' (RS) approach for inverse problems modeled using nonsmooth nonconvex optimization formulations. RS uses a relaxation technique together with partial minimization, and brings classic techniques including direct factorization, matrix decompositions, and fast iterative methods to bear on nonsmooth nonconvex problems. We also extend the approach to robustify any such inverse problem through trimming, a mechanism that robustifies inverse problems to measurement outliers. We then show practical performance of RS and trimmed RS (TRS) on a diverse set of problems, including: (1) phase retrieval, (2) semi-supervised classification, (3) stochastic shortest path problems, and (4) nonconvex clustering. RS/TRS are easy to implement, competitive with existing methods, and show promising results on difficult inverse problems with nonsmooth and nonconvex features.