Relax-and-split method for nonconvex inverse problems

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.