Provable Alternating Gradient Descent for Non-negative Matrix Factorization with Strong Correlations
This addresses a common bottleneck in practical applications of non-negative matrix factorization, offering a provable solution for scenarios with strong correlations, though it is incremental in improving theoretical guarantees for an existing framework.
The paper tackles the problem of recovering the ground-truth feature matrix in non-negative matrix factorization when feature weights are highly correlated, and shows that a proposed alternating gradient descent algorithm provably recovers it with correlations as high as possible, demonstrating robustness to noise and empirical advantages over existing methods.
Non-negative matrix factorization is a basic tool for decomposing data into the feature and weight matrices under non-negativity constraints, and in practice is often solved in the alternating minimization framework. However, it is unclear whether such algorithms can recover the ground-truth feature matrix when the weights for different features are highly correlated, which is common in applications. This paper proposes a simple and natural alternating gradient descent based algorithm, and shows that with a mild initialization it provably recovers the ground-truth in the presence of strong correlations. In most interesting cases, the correlation can be in the same order as the highest possible. Our analysis also reveals its several favorable features including robustness to noise. We complement our theoretical results with empirical studies on semi-synthetic datasets, demonstrating its advantage over several popular methods in recovering the ground-truth.