Multi-block Bregman proximal alternating linearized minimization and its application to orthogonal nonnegative matrix factorization

Abstract

We introduce and analyze BPALM and A-BPALM, two multi-block proximal alternating linearized minimization algorithms using Bregman distances for solving structured nonconvex problems. The objective function is the sum of a multi-block relatively smooth function (i.e., relatively smooth by fixing all the blocks except one) and block separable (nonsmooth) nonconvex functions. It turns out that the sequences generated by our algorithms are subsequentially convergent to critical points of the objective function, while they are globally convergent under KL inequality assumption. Further, the rate of convergence is further analyzed for functions satisfying the Łojasiewicz's gradient inequality. We apply this framework to orthogonal nonnegative matrix factorization (ONMF) that satisfies all of our assumptions and the related subproblems are solved in closed forms, where some preliminary numerical results is reported.

References in corpus (15)

• Fast and Robust Recursive Algorithms for Separable Nonnegative Matrix Factorization
• The Why and How of Nonnegative Matrix Factorization
• Nonnegative Matrix Factorization for Signal and Data Analytics: Identifiability, Algorithms, and Applications
• Inertial Proximal Alternating Linearized Minimization (iPALM) for Nonconvex and Nonsmooth Problems
• Two Algorithms for Orthogonal Nonnegative Matrix Factorization with Application to Clustering
• Forward-backward envelope for the sum of two nonconvex functions: Further properties and nonmonotone line-search algorithms
• Accelerating the DC algorithm for smooth functions
• A Coordinate Descent Primal-Dual Algorithm with Large Step Size and Possibly Non Separable Functions
• A Bregman forward-backward linesearch algorithm for nonconvex composite optimization: superlinear convergence to nonisolated local minima
• Regularizing with Bregman-Moreau envelopes
• Accelerated Bregman Proximal Gradient Methods for Relatively Smooth Convex Optimization
• On the acceleration of forward-backward splitting via an inexact Newton method
• Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problems
• Provable Bregman-divergence based Methods for Nonconvex and Non-Lipschitz Problems
• Regularity Properties of Non-Negative Sparsity Sets

Cited by in corpus (5)

• Randomized Bregman Coordinate Descent Methods for Non-Lipschitz Optimization
• Structured Nonnegative Matrix Factorization for Traffic Flow Estimation of Large Cloud Networks
• An Inertial Block Majorization Minimization Framework for Nonsmooth Nonconvex Optimization
• Leveraging Two Reference Functions in Block Bregman Proximal Gradient Descent for Non-convex and Non-Lipschitz Problems
• Sampling-Based Methods for Multi-Block Optimization Problems over Transport Polytopes