Search

Nonnegative matrix factorization (NMF) is a popular method in machine learning and signal processing to decompose a given nonnegative matrix into two nonnegative matrices. In this paper, to solve NMF, we propose new algorithms, called majorization-minimization Bregman proximal gradient algorithm (MMBPG) and MMBPG with extrapolation (MMBPGe). MMBPG and MMBPGe minimize an auxiliary function majorizing the Kullback--Leibler (KL) divergence loss by the existing Bregman proximal gradient algorithms. While existing KL-based NMF methods update each variable alternately, proposed algorithms update all variables simultaneously. The proposed MMBPG and MMBPGe are equipped with a separable Bregman distance that satisfies the smooth adaptable property and that makes its subproblem solvable in closed forms. We also proved that even though these algorithms are designed to minimize an auxiliary function, MMBPG and MMBPGe monotonically decrease the objective function and a potential function, respectively. Using this fact, we establish that a sequence generated by MMBPG(e) globally converges to a Karush--Kuhn--Tucker (KKT) point. In numerical experiments, we compared proposed algorithms with existing algorithms on synthetic data., Comment: 25 pages, 26 figures

In this paper, we propose the approximate Bregman proximal gradient algorithm (ABPG) for solving composite nonconvex optimization problems. ABPG employs a new distance that approximates the Bregman distance, making the subproblem of ABPG simpler to solve compared to existing Bregman-type algorithms. The subproblem of ABPG is often expressed in a closed form. Similarly to existing Bregman-type algorithms, ABPG does not require the global Lipschitz continuity for the gradient of the smooth part. Instead, assuming the smooth adaptable property, we establish the global subsequential convergence under standard assumptions. Additionally, assuming that the Kurdyka--{\L}ojasiewicz property holds, we prove the global convergence for a special case. Our numerical experiments on the $\ell_p$ regularized least squares problem, the $\ell_p$ loss problem, and the nonnegative linear system show that ABPG outperforms existing algorithms especially when the gradient of the smooth part is not globally Lipschitz or even local Lipschitz continuous., Comment: 31 pages, 20 figures

Blind deconvolution is a technique to recover an original signal without knowing a convolving filter. It is naturally formulated as a minimization of a quartic objective function under some assumption. Because its differentiable part does not have a Lipschitz continuous gradient, existing first-order methods are not theoretically supported. In this paper, we employ the Bregman-based proximal methods, whose convergence is theoretically guaranteed under the $L$-smooth adaptable ($L$-smad) property. We first reformulate the objective function as a difference of convex (DC) functions and apply the Bregman proximal DC algorithm (BPDCA). This DC decomposition satisfies the $L$-smad property. The method is extended to the BPDCA with extrapolation (BPDCAe) for faster convergence. When our regularizer has a sufficiently simple structure, each iteration is solved in a closed-form expression, and thus our algorithms solve large-scale problems efficiently. We also provide the stability analysis of the equilibrium and demonstrate the proposed methods through numerical experiments on image deblurring. The results show that BPDCAe successfully recovered the original image and outperformed other existing algorithms.

Difference of Convex (DC) optimization problems have objective functions that are differences between two convex functions. Representative ways of solving these problems are the proximal DC algorithms, which require that the convex part of the objective function have $L$-smoothness. In this article, we propose the Bregman Proximal DC Algorithm (BPDCA) for solving large-scale DC optimization problems that do not possess $L$-smoothness. Instead, it requires that the convex part of the objective function has the $L$-smooth adaptable property that is exploited in Bregman proximal gradient algorithms. In addition, we propose an accelerated version, the Bregman Proximal DC Algorithm with extrapolation (BPDCAe), with a new restart scheme. We show the global convergence of the iterates generated by BPDCA(e) to a limiting critical point under the assumption of the Kurdyka-{\L}ojasiewicz property or subanalyticity of the objective function and other weaker conditions than those of the existing methods. We applied our algorithms to phase retrieval, which can be described both as a nonconvex optimization problem and as a DC optimization problem. Numerical experiments showed that BPDCAe outperformed existing Bregman proximal-type algorithms because the DC formulation allows for larger admissible step sizes.