TL;DR
This paper introduces novel conic optimization formulations for Nonnegative Matrix Factorization (NMF), enabling the computation of high-quality solutions. By leveraging exponential and second-order cones, they develop an iterative algorithm that achieves a provable convergence rate to stationary points, a significant theoretical contribution to the NMF field.
What Problem Does This Paper Address?
Nonnegative Matrix Factorization (NMF) is a fundamental problem in data analysis, aiming to decompose a nonnegative matrix $V$ into two smaller nonnegative matrices $W$ and $H$ ($V \approx WH$). While widely used, finding exact factorizations ($V=WH$) is NP-hard, and existing methods often rely on iterative heuristics that only guarantee local optima. This paper tackles the challenge of developing algorithms that can reliably find exact NMFs or high-quality approximations with theoretical convergence guarantees, moving beyond traditional block coordinate descent methods. They specifically focus on finding exact NMFs, which is crucial for determining the nonnegative rank of a matrix and for applications where precise decomposition is critical.
Methods
The core of this work lies in reformulating the NMF problem using conic optimization. The authors propose two main approaches:
- Exponential Cone Formulation: NMF is reframed as maximizing a concave function over a product of convex cones. This formulation leads to under-approximations of $V$.
- Second-Order Cone Formulation: Similarly, NMF is reformulated using second-order cones, leading to over-approximations of $V$.
For both formulations, they develop an iterative algorithm based on successive linearizations of the objective function. This approach is shown to be a special case of the Frank-Wolfe (FW) algorithm. The subproblems generated at each iteration are convex conic programs, efficiently solvable using interior-point methods. A key theoretical contribution is the proof that this algorithm converges to a stationary point with a rate of $O(1/i)$, where $i$ is the iteration number, using the Frank-Wolfe gap as a measure of stationarity. For the specific case of rank-one factorization ($K=1$), the second-order cone formulation simplifies to a convex optimization problem, allowing for efficient computation of optimal rank-one approximations.
Datasets
The paper evaluates its algorithms on several classes of matrices:
- Randomly generated matrices: 10x10 matrices generated by multiplying two random rank-5 nonnegative matrices.
- Infinitesimally rigid factorizations: Four 5x5 matrices with nonnegative rank 4.
- Slack matrices: Four 5x5 matrices corresponding to nested hexagons, with varying nonnegative ranks.
These matrices are standard benchmarks in the NMF literature, allowing for direct comparison with existing methods. No new datasets were introduced.
Key Insights and Ideas
- Conic Reformulation for NMF: The paper demonstrates that NMF, a notoriously difficult problem, can be effectively reformulated using established conic optimization tools (exponential and second-order cones). This opens up new avenues for algorithmic development.
- Provable Convergence Rate: The theoretical analysis provides a convergence rate of $O(1/i)$ to stationary points for the proposed algorithm. This is a significant theoretical advancement, as provable convergence rates for NMF algorithms are scarce, especially for non-convex objectives.
- Frank-Wolfe Connection: Identifying the algorithm as a variant of the Frank-Wolfe algorithm provides a strong theoretical foundation and allows leveraging existing FW analysis for convergence guarantees.
- Rank-One Optimization: The simplification of the second-order cone formulation to a convex problem for rank-one NMF is a notable finding, offering an efficient way to compute optimal rank-one approximations.
- Under- and Over-Approximations: The two formulations naturally provide under- and over-approximations, which can be useful in their own right and offer flexibility in how the NMF problem is tackled.
Key Results
- The proposed Algorithm 1, using both conic formulations, successfully computes exact NMFs for a variety of tested matrices, often competing favorably with state-of-the-art methods.
- For some challenging matrices (e.g., nested hexagons), Algorithm 1 with the second-order cone formulation (Algorithm 1 with (9)) showed a higher success rate (up to 100%) compared to other methods.
- The theoretical analysis proves a convergence rate of $O(1/i)$ for the minimum Frank-Wolfe gap, indicating convergence to stationary points.
- Numerical experiments validate the theoretical convergence rate, showing the FW gap decreasing as predicted.
- The second-order cone formulation (Algorithm 1 with (9)) generally performed slightly better than the exponential cone formulation (Algorithm 1 with (5)) in terms of success rate.
Limitations and Future Work
- Computational Cost: The paper acknowledges that the current algorithm relies on interior-point methods, which do not scale as well as first-order methods for very large datasets. This limits its applicability to smaller matrices compared to some state-of-the-art NMF algorithms.
- Initialization Strategies: While random initialization is used, the paper suggests that more advanced initialization strategies could further improve performance, as demonstrated by a rank-one NMO-based initialization.
- Scalability: Improving the scalability of the conic optimization approach is a key direction for future research, potentially by exploring faster solvers or alternative algorithmic frameworks.
- Non-Uniqueness of NMF: The paper mentions the non-uniqueness of NMF solutions and plans to develop formulations that address this issue, such as removing permutation and scaling ambiguities.
- Upper-Approximations: Exploring more accurate upper-approximations than linearizations for concave functions is also suggested for future work.
- Approximate NMF: While the focus is on exact NMF, the formulations can be used for approximate NMF, and further investigation into their performance for approximate factorization on larger datasets is warranted.
Summary updated