Study For Multi-stage Convex Relaxation Approach To Low-rank Optimization Problems

Low-rank matrix optimization problems have a very wide range of applications ina diverse set of fields such as statistics, control and system identification, signal andimage processing, finance, quantum computation, and so on. This dissertation is devoteditself to the design and study for multi-stage convex relaxation approach to general rankminimization problems and rank regularized minimization problems, by transformingthese optimization problems with a ceratin combinatorial property into equivalent locallyLipschitz continuous optimization models with quasi-bilinear structure, with the help ofthe variational characterization of rank function.Firstly, based on the variational characterization of rank function, the dissertationreformulates rank minimization problems and rank regularized minimization problems,respectively, as equivalent mathematical programming problems with generalized matrixcomplementarity constraints (MPGCC). To overcome their solution difculty due to thenonconvexity of generalized complementarity constraints, we study the exactness of thepenalty problems induced by adding generalized complementarity constraints to the ob-jective, i.e., shows that the global optimum set of penalty problems coincides with that ofthe MPGCC when the penalty parameter is over some threshold. Although the objectivefunctions of exact penalty problems are still nonconvex, they have quasi-bilinear struc-ture and locally Lipschitz continuity, thereby providing desirable nonsmooth optimizationmodels for designing convex relaxation approach to low-rank optimization problems.Secondly, by solving the equivalent locally Lipschitz continuous optimization modelsin an alternating way, the dissertation proposes a class of multi-stage convex relaxationapproaches to general rank minimization problems. This class of multi-stage convexrelaxation approaches is solving at each step a nuclear semi-norm minimization problem(a weighted trace norm minimization problem in the positive semidefinite case). For theproposed multi-stage convex relaxation approach, under a restricted eigenvalue conditionweaker than the well-known restricted isometry property, the dissertation establishes theFrobenius norm error bound and approximate rank bound for the optimal solution of eachstage, provides a quantitative characterization for the strict decrease of the error boundsand approximate rank bounds in the successive two stages, and shows that the obtainederror bounds are tighter than the one established in [53] for the reweighed trace normminimization method. The theoretical analysis results show that for those linear operatorswith worse restricted eigenvalue property, the two-stage convex relaxation approach based on an appropriate function reduces the error bound and approximate rank bound of thenuclear norm convex relaxation method at least50%, while for those linear operatorswith better restricted eigenvalue property, the two-stage convex relaxation approach basedon an appropriate function reduces the error bound and approximate rank bound of thenuclear-norm convex relaxation method about20%. Moreover, with the number of stagesincreasing, the reduction ratio of error bounds and approximate rank bounds will becomesmaller and then keep unchanged after the fifth stage. In addition, the dissertation alsoverifies the correctness of the obtained theoretical results via numerical experiments forseveral classes of randomly generated structured low-rank matrix recovery problems.Lastly, by solving the (approximate) equivalent locally Lipschitz continuous opti-mization models in an alternating way, the dissertation also proposes a class of multi-stageconvex relaxation approaches to general rank regularized minimization problems. Thisclass of multi-stage convex relaxation approaches is solving a nuclear semi-norm regular-ized minimization problem (the weighted trace norm regularized minimization problemin the positive semidefinite case). For the rank regularized minimization problems witha spectral norm ball constraint, under a mild restricted eigenvalue condition, the disser-tation establishes the Frobenius norm error bound and the approximate rank bound forthe optimal solution of each stage, and quantitatively characterizes the strict decrease ofthe error bound and approximate rank bound in successive two stages. The theoreticalanalysis results show that, for the linear operators with whether worse or better restrictedeigenvalue property, the two-stage convex relaxation approach based on an appropriatefunction reduces the error bound and the approximate rank bound of the nuclear normconvex relaxation method at least50%. Similarly, as the number of stages increases, thereduction range of the error and approximate rank bounds will become smaller and thenkeep unchanged after the fifth stage. In addition, the dissertation verifies the correctnessof the obtained theoretical results as well as the advantages in reducing the errors, vianumerical experiments for the randomly generated low-rank matrix recovery problems.To the best of our knowledge, for the non-positive semidefinite rank minimizationproblems and rank regularized minimization problems, the multi-stage convex relaxationapproach proposed in the dissertation with the help of their equivalent locally Lipschitzcontinuous optimization models is the first multi-stage convex relaxation approach thatboth has theoretical guarantees and reduces error bounds of the nuclear norm convexrelaxation method greatly; and for the positive semidefinite rank minimization problems,the obtained theoretical results strengthen and extend the results established in [53] forthe reweighted trace norm minimization method.