Greedy Orthogonal Pivoting Algorithm for Non-Negative Matrix Factorization
Kai Zhang · Sheng Zhang · Jun Liu · Jun Wang · Jie Zhang

Thu Jun 13th 05:00 -- 05:05 PM @ Room 104

Non-negative matrix factorization is a powerful tool for learning useful representations in the data and has been widely applied in many problems such as data mining and signal processing. Orthogonal NMF, which can improve the locality of decomposition, has drawn considerable interest in solving clustering problems in recent years. However, imposing simultaneous non-negative and orthogonal structure can be quite difficult, and so existing algorithms can only solve it approximately. To address this challenge, we propose an innovative procedure called Greedy Orthogonal Pivoting Algorithm (GOPA). The GOPA algorithm fully exploits the sparsity of non-negative orthogonal solutions to break the global problem into a series of local optimizations, in which an adaptive subset of coordinates are updated in a greedy, closed-form manner. The biggest advantage of GOPA is that it promotes exact orthogonality and provides solid empirical evidence that stronger orthogonality does contribute favorably to better clustering performance. On the other hand, we further design randomized and parallel version of GOPA, which can further reduce the computational cost and improve accuracy, making it suitable for large data.

Author Information

Kai Zhang (East China Normal University)
Sheng Zhang (Temple University)
Jun Liu (Infinia ML Inc.)
Jun Wang (Alibaba)
Jie Zhang (Fudan University)

Related Events (a corresponding poster, oral, or spotlight)