text: Various applications in signal processing and machine learning give rise to highly structured spectral optimization problems characterized by low-rank solutions. Two important examples that motivate this work are optimization problems from phase retrieval and from blind deconvolution, which are designed to yield rank-1 solutions. An algorithm is described that is based on solving a certain constrained eigenvalue optimization problem that corresponds to the gauge dual which, unlike the more typical Lagrange dual, has an especially simple constraint. The dominant cost at each iteration is the computation of rightmost eigenpairs of a Hermitian operator. A range of numerical examples illustrate the scalability of the approach.
  @cite_8: A new nonmonotone line search algorithm is proposed and analyzed. In our scheme, we require that an average of the successive function values decreases, while the traditional nonmonotone approach of Grippo, Lampariello, and Lucidi [SIAM J. Numer. Anal., 23 (1986), pp. 707--716] requires that a maximum of recent function values decreases. We prove global convergence for nonconvex, smooth functions, and R-linear convergence for strongly convex functions. For the L-BFGS method and the unconstrained optimization problems in the CUTE library, the new nonmonotone line search algorithm used fewer function and gradient evaluations, on average, than either the monotone or the traditional nonmonotone scheme.
summary: There are at least two issues that need to be addressed when comparing the FW algorithm to the approach we take here. First, as @cite_8 make clear, even in cases where low-rank solutions are expected, it is not possible to anticipate the rank of early iterates @math generated by the FW method. In particular, they observe that the rank of @math quickly increases during early iterations, and only slowly starts to decrease as the solution is approached. This motivates their development of algorithmic devices that attenuate rank growth in intermediate iterates. Any implementation, however, must be prepared to increase storage for the factors of @math during intermediate iterates. In contrast, a subgradient method applied to the gauge dual problem can be implemented with constant storage. Second, although in principle there exists a parameter @math that causes the optimization problems and to share the same solution, this parameter is not generally known in advance. One way around this is to solve a sequence of problems for varying parameters @math using, for example, a level-set procedure described by * 2016arXiv160201506A .