On first-order algorithms forl1/nuclear norm minimization

In the past decade, problems related tol1/nuclear norm minimization have attracted much attention in the signal processing, machine learning and optimization communities. In this paper, devoted tol1/nuclear norm minimization as ‘optimization beasts’, we give a detailed description of two attractive first-order optimization techniques for solving problems of this type. The first one, aimed primarily at lasso-type problems, comprises fast gradient methods applied to composite minimization formulations. The second approach, aimed at Dantzig-selector-type problems, utilizes saddle-point first-order algorithms and reformulation of the problem of interest as ageneralized bilinear saddle-point problem. For both approaches, we give complete and detailed complexity analyses and discuss the application domains.