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.
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 .
@cite_8
2167137033
This paper introduces a novel algorithm to approximate the matrix with minimum nuclear norm among all matrices obeying a set of convex constraints. This problem may be understood as the convex relaxation of a rank minimization problem and arises in many important applications as in the task of recovering a large matrix from a small subset of its entries (the famous Netflix problem). Off-the-shelf algorithms such as interior point methods are not directly amenable to large problems of this kind with over a million unknown entries. This paper develops a simple first-order and easy-to-implement algorithm that is extremely efficient at addressing problems in which the optimal solution has low rank. The algorithm is iterative, produces a sequence of matrices @math , and at each step mainly performs a soft-thresholding operation on the singular values of the matrix @math . There are two remarkable features making this attractive for low-rank matrix completion problems. The first is that the soft-thresholding operation is applied to a sparse matrix; the second is that the rank of the iterates @math is empirically nondecreasing. Both these facts allow the algorithm to make use of very minimal storage space and keep the computational cost of each iteration low. On the theoretical side, we provide a convergence analysis showing that the sequence of iterates converges. On the practical side, we provide numerical examples in which @math matrices are recovered in less than a minute on a modest desktop computer. We also demonstrate that our approach is amenable to very large scale problems by recovering matrices of rank about 10 with nearly a billion unknowns from just about 0.4 of their sampled ent