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_1: We study a hybrid conditional gradient - smoothing algorithm (HCGS) for solving composite convex optimization problems which contain several terms over a bounded set. Examples of these include regularization problems with several norms as penalties and a norm constraint. HCGS extends conditional gradient methods to cases with multiple nonsmooth terms, in which standard conditional gradient methods may be difficult to apply. The HCGS algorithm borrows techniques from smoothing proximal methods and requires first-order computations (subgradients and proximity operations). Unlike proximal methods, HCGS benefits from the advantages of conditional gradient methods, which render it more efficient on certain large scale optimization problems. We demonstrate these advantages with simulations on two matrix optimization problems: regularization of matrices with combined @math and trace norm penalties; and a convex relaxation of sparse PCA.
  @cite_7: Given a convex optimization problem and its dual, there are many possible first-order algorithms. In this paper, we show the equivalence between mirror descent algorithms and algorithms generalizing the conditional gradient method. This is done through convex duality and implies notably that for certain problems, such as for supervised machine learning problems with nonsmooth losses or problems regularized by nonsmooth regularizers, the primal subgradient method and the dual conditional gradient method are formally equivalent. The dual interpretation leads to a form of line search for mirror descent, as well as guarantees of convergence for primal-dual certificates.
  @cite_17: Etude de nouvelles methodes de descente suivant le gradient pour la solution approchee du probleme de minimisation sans contrainte. Analyse de la convergence
summary: As an alternative to applying the FW algorithm to , we might instead consider applying a variation of the FW method directly to the gauge dual problem . Because the gauge dual objective is not differentiable and the feasible set is not compact if @math , some modification to the standard FW method is required. @cite_1 , @cite_7 , and @cite_17 propose variations of FW that involve smoothing the objective. These smoothing approaches are typically based on infimal convolution with a smooth kernel, which may lead to a function whose gradient is expensive to compute. For example, the soft-max'' smooth approximation of @math is the function @math . Forming the gradient of this smooth function requires computing all eigenvalues of an @math -by- @math Hermitian matrix.