Global Optimality Bounds for ICA Algorithms

Independent Component Analysis is a popular statistical method for separating a multivariate signal into additive components. It has been shown that the signal separation problem can be reduced to the joint diagonalization of the matrix slices of some higher-order cumulants of the signal. In this approach, the unknown mixing matrix can be computed directly from the obtained joint diagonalizer. Various iterative algorithms for solving the non-convex joint diagonalization problem exist, but they usually lack global optimality guarantees. In this paper, we introduce a procedure for computing an optimality gap for local optimal solutions. The optimality gap is then used to obtain an empirical error bound for the estimated mixing matrix. Finally, a class of simultaneous matrix decomposition problems that admit such relaxation procedure is identified.