A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements
We propose a simple, scalable, and fast gradient descent algorithm to optimize a nonconvex objective for the rank minimization problem and a closely related family of semidefinite programs. With O(r 3 κ 2 n log n) random measurements of a positive semidefinite n×n matrix of rank r and condition number κ, our method is guaranteed to converge linearly to the global optimum.
This paper proposes a gradient descent type algorithm for rank minimization in the space of symmetric positive semidefinite matrices with linear equality constraints. It was motivated by the recent work by Candes et al [5]. The basic algorithm as in [5] is based on the Wirtinger flow algorithm. Convergence analysis and sample complexity analysis are also provided for the proposed algorithm. The paper is well-written with consistent notations and a high level outline of the convergence analysis. These make this paper more accessible to readers. In addition, with a nice initialization strategy, it converges to the global optimum under some assumptions.This is a good paper. I was pleased to review this paper.My general comments and suggestion are the following.  L177 : Authors claim that the method generalizes Wirtinger's flow algorithm which I'm not sure is right because the proposed method is defined with only real values (NOT complex); z and ai's. Please clarify that.Please briefly explain about a "phase retrieval" for readers who are not familiar with the previous work by Candes et al [5].Assumption on the true rank:L183 : The paper assumes that the true rank is given prior to the algorithm. It might be a quite strong assumption in some sense and the nuclear norm method does not assume this. Discuss the effect of misspecification of rank with the proposed method.L253 : As authors suggested, if one wants to search for the proper rank by running the algorithm multiple times, is there a systematic way of choosing r after running the algorithm say n number of times and looking at the value f(Z) after each r?Eventually, the problem solved by the method is reduced to an optimization for a fixed (low) rank solution. In literature, it was addressed by multiple methods especially using manifold frameworks, which are not discussed in the paper. You may want to refer relevant works (R1-R3) for readers.R1. Journee, Michel, et al. "Low-rank optimization on the cone of positive semidefinite matrices." SIAM Journal on Optimization 20.5 (2010): 2327-2351. R2. Vandereycken, Bart, and Stefan Vandewalle. "A Riemannian optimization approach for computing low-rank solutions of Lyapunov equations." SIAM Journal on Matrix Analysis and Applications 31.5 (2010): 2553-2579. R3. Vandereycken, Bart. "Low-rank matrix completion by Riemannian optimization."SIAM Journal on Optimization 23.2 (2013): 1214-1236.