Fast alternating volume maximization algorithm for blind separation of non-negative sources

We recently reported an iterative non-negative blind source separation (nBSS) method, called convex analysis of mixtures of nonnegative sources via alternating volume maximization (CAMNSAVM) [1], and demonstrated that it provides promising separation performance in image analysis. Nonetheless, the amount of data may be quite large in practical applications, and this may limit the real-time applicability of CAMNS-AVM. In this paper, we propose a fast CAMNS-AVM algorithm involving three complexity reduction methods, specifically problem equivalence, redundant constraints removal, and customized algorithm implementation. The problem equivalence provides sufficiency in solving one linear program (LP) for each partial volume maximization problem, rather than the two LPs required by the original CAMNS-AVM. Then, we remove redundant constraints of each LP involved in CAMNS-AVM by using Quickhull algorithm to enumerate all the extreme points of the constraint-set-constructed convex hull. Finally, we implement a customized primal-dual interior-point method (IPM) for LP. Some Monte Carlo simulation results demonstrate that the fast CAMNS-AVM algorithm is thirty times more computationally efficient than the original CAMNS-AVMalgorithm, without any performance loss.