First-order splitting algorithms for nonconvex matrix optimization problems

Abstract

In this thesis, we consider two classes of matrix optimization problems. One is the matrix decomposition problem (MDP), which aims to decompose a given data matrix into the sum of two matrices with different desirable structures. The other one is the matrix factorization problem (MFP), which aims to factorize a given data matrix into the product of two small factor matrices with different desirable structures. These two classes of problems cover many existing widely-studied models with many applications in areas such as machine learning and imaging sciences. To solve MDP and MFP, which are possibly nonconvex, nonsmooth and even non-Lipschitz, we develop two efficient first-order splitting algorithms for them, respectively. We first consider MDP. Specifically, we adapt the alternating direction method of multipliers (ADMM) with a general dual step-size to solve a reformulation of the original problem that contains three blocks of variables, and analyze its convergence. We show that for any dual step-size less than the golden ratio, there exists a computable threshold such that if the penalty parameter is chosen above such a threshold and the sequence thus generated by our ADMM is bounded, then the cluster point of the sequence gives a stationary point of the nonconvex optimization problem. We achieve this via a potential function specifically constructed for our ADMM. Moreover, we establish the global convergence of the whole sequence if, in addition, this special potential function is a Kurdyka-Lojasiewicz function. Furthermore, we present a simple strategy for initializing the ADMM to guarantee boundedness of the sequence. Finally, we perform numerical experiments comparing our ADMM with the proximal alternating linearized minimization proposed in [8] for the background/foreground extraction problem on real datasets. The numerical results show that our ADMM with a nontrivial dual step-size is efficient. We then consider MFP. To solve it, we develop a non-monotone alternating updating method based on a potential function. Our method essentially updates two blocks of variables in turn by inexactly minimizing this potential function, and updates another auxiliary block of variables using an explicit formula. The special structure of our potential function allows us to take advantage of efficient computational strategies for non-negative matrix factorization to perform the alternating minimization over two blocks of variables. A suitable line search criterion is also incorporated to improve the numerical performance of our method. Under some mild conditions, we show that our line search criterion is well defined, and establish that the sequence generated is bounded and any cluster point of the sequence is a stationary point of our problem. Moreover, we discuss the convergence rate for the function value if, in addition, the objective is a Kurdyka-Lojasiewicz function. Finally, we conduct some numerical experiments using real datasets to compare our method with some existing efficient methods for non-negative matrix factorization and matrix completion. The numerical results show that our method can outperform these methods for these specific applications.