Conic optimization-based algorithms for nonnegative matrix factorization

References

• H. Abbaszadehpeivasti, E. de Klerk, and M. Zamani, On the Rate of Convergence of the Difference-of-Convex Algorithm (DCA). J. Optim. Theory Appl. (2023). https://doi.org/10.1007/s10957-023-02199-z.
   Google Scholar
• S. Arora, R. Ge, R. Kannan, and A. Moitra, Computing a nonnegative matrix factorization—provably, SIAM J. Comput. 45 (2016), pp. 1582–1611.
   Web of Science ®Google Scholar
• S. Basu, R. Pollack, and M.F. Roy, On the combinatorial and algebraic complexity of quantifier elimination, J. ACM. 43 (1996), pp. 1002–1045.
   Web of Science ®Google Scholar
• A. Berman and N. Shaked-Monderer, Completely Positive Matrices, World Scientific, 2003.
   Google Scholar
• A. Cichocki, R. Zdunek, A.H. Phan, and S.i. Amari, Nonnegative Matrix and Tensor Factorizations: Applications to Exploratory Multi-way Data Analysis and Blind Source Separation, John Wiley & Sons, 2009.
   Google Scholar
• K.L. Clarkson, Coresets, sparse greedy approximation, and the Frank–Wolfe algorithm, ACM Trans. Algorithms. 6 (2010), pp. 1–30.
   Web of Science ®Google Scholar
• J.E. Cohen and U.G. Rothblum, Nonnegative ranks, decompositions, and factorizations of nonnegative matrices, Linear. Algebra. Appl. 190 (1993), pp. 149–168.
   Web of Science ®Google Scholar
• J. Dewez, Computational approaches for lower bounds on the nonnegative rank, Ph.D. diss., UCLouvain, 2022.
   Google Scholar
• J. Dewez, N. Gillis, and F. Glineur, A geometric lower bound on the extension complexity of polytopes based on the f-vector, Discrete Appl Math. 303 (2021), pp. 22–38.
   Web of Science ®Google Scholar
• M. Frank and P. Wolfe, An algorithm for quadratic programming, Nav. Res. Logist. Q. 3 (1956), pp. 95–110.
   Google Scholar
• X. Fu, K. Huang, N.D. Sidiropoulos, and W.K. Ma, Nonnegative matrix factorization for signal and data analytics: identifiability, algorithms, and applications, IEEE Signal Process. Mag. 36 (2019), pp. 59–80.
   Google Scholar
• N. Gillis, Approximation et sous-approximation de matrices par factorisation positive : algorithmes, complexité et applications, Master's thesis, Universite Catholique de Louvain, 2007.
   Google Scholar
• N. Gillis, Nonnegative Matrix Factorization, SIAM, Philadelphia, 2020.
   Google Scholar
• N. Gillis and F. Glineur, Accelerated multiplicative updates and hierarchical ALS algorithms for nonnegative matrix factorization, Neural. Comput. 24 (2012), pp. 1085–1105.
   PubMed Web of Science ®Google Scholar
• N. Gillis, Nonnegative matrix factorization: Complexity, algorithms and applications. Unpublished doctoral dissertation, Université catholique de Louvain. Louvain-La-Neuve: CORE. 2011.
   Google Scholar
• N. Gillis and F. Glineur, Using underapproximations for sparse nonnegative matrix factorization, Pattern. Recognit. 43 (2010), pp. 1676–1687.
   Web of Science ®Google Scholar
• M. Jaggi, Sparse convex optimization methods for machine learning, Ph.D. diss., ETH Zurich, 2011.
   Google Scholar
• M. Jaggi, Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization, in Proceedings of the 30th International Conference on Machine Learning, Proceedings of Machine Learning Research Vol. 28, 17–19 Jun, Atlanta, Georgia, USA. PMLR, 2013, pp. 427–435.
   Google Scholar
• J. Kim and H. Park, Fast nonnegative matrix factorization: an active-set-like method and comparisons, SIAM J. Sci. Comput. 33 (2011), pp. 3261–3281.
   Web of Science ®Google Scholar
• R. Krone and K. Kubjas, Uniqueness of nonnegative matrix factorizations by rigidity theory, SIAM J. Matrix. Anal. Appl. 42 (2021), pp. 134–164.
   Web of Science ®Google Scholar
• D. Kuang, C. Ding, and H. Park, Symmetric Nonnegative Matrix Factorization for Graph Clustering, in Proceedings of the 2012 SIAM International Conference on Data Mining. pp. 106–117.
   Google Scholar
• S. Lacoste-Julien, Convergence rate of Frank–Wolfe for non-convex objectives, Preprint (2016). Available at arXiv, 1607.00345.
   Google Scholar
• H.A. Le Thi and T. Pham Dinh, DC programming and DCA: thirty years of developments, Math. Program. 169 (2018), pp. 5–68.
   Web of Science ®Google Scholar
• A. Moitra, An Almost Optimal Algorithm for Computing Nonnegative Rank, in Proc. of the 24th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA '13), 2013, pp. 1454–1464.
   Google Scholar
• Mosek APS, Optimization software. available at https://www.mosek.com/.
   Google Scholar
• R. Sharma and K. Sharma, A new dual based procedure for the transportation problem, Eur. J. Oper. Res. 122 (2000), pp. 611–624.
   Web of Science ®Google Scholar
• Y. Shitov, The nonnegative rank of a matrix: hard problems, easy solutions, SIAM Rev. 59 (2017), pp. 794–800.
   Web of Science ®Google Scholar
• M. Tepper and G. Sapiro, Nonnegative matrix underapproximation for robust multiple model fitting, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2017, pp. 2059–2067.
   Google Scholar
• A. Vandaele, N. Gillis, F. Glineur, and D. Tuyttens, Heuristics for exact nonnegative matrix factorization, J. Glob. Optim. 65 (2016), pp. 369–400.
   Web of Science ®Google Scholar
• S.A. Vavasis, On the complexity of nonnegative matrix factorization, SIAM J. Optim. 20 (2010), pp. 1364–1377.
   Web of Science ®Google Scholar